自动排序列表

• 下载源代码和测试文件 - 5.33 Kb

引言

基本上，我想要一个**动态**数组，无论用户做什么，其中的所有元素都**始终保持排序**，尤其是在添加新元素时。然后，考虑到列表知道自己是否处于排序状态，它可以更有效地执行操作。例如，通过透明的二分搜索可以优化查找元素的过程。

这样的集合也必须像其他列表一样可以通过索引访问，并且它必须提供与 ArrayList 类相同的服务。

当然，.NET 框架在 System.Collections 组件中提供了 SortedList 类。尽管如此，它并没有让我满意。事实上，它是一个按键排序的键值对集合。因此，它内部维护了两个数组：一个用于值，一个用于键。所以这对于常见需求来说有点笨重，而且不太方便使用。毕竟，在大多数情况下，您希望元素根据其自身的 IComparable 实现或指定的 IComparer 进行排序。这很有意义。

因此，我创建了这个 SortableList，其主要属性是：

• bool IsSorted {get}--> 表示列表是否已排序。
• bool KeepSorted {get/set}--> 如果为 true，则新添加的元素将放置在使其列表保持排序的位置。如果为 false，则它们将被简单地追加，列表将表现得像一个未排序的数组。如果列表未排序，则不能将此属性设置为 true，否则会抛出异常。请注意，KeepSorted==true 意味着 IsSorted==true。
• bool AddDuplicates {get/set}--> 接受或拒绝重复元素。如果为 false，当列表中已存在相同值的对象时，该对象将不会被添加。

使用代码

默认情况下，KeepSorted 设置为 true，并且列表将永久保持排序，取决于：

• 通过适当的构造函数提供的 IComparer 接口。
• 或者（默认情况下）包含对象的 IComparable 实现。

如果您决定将 KeepSorted 设置为 false 并在该模式下执行一些无序操作，那么除非您调用方法：void Sort()，否则列表将不会再次排序。

默认情况下，AddDuplicates 设置为 true。但当它为 false 时，列表保证，只要列表中已存在相同值，就不会添加该对象。自然，相等性根据 Object.Equals(object O) 方法来识别。此外，还提供了两个函数来检索列表中的所有重复项，甚至保留指定值的特定数量的元素。它们是：

• public void LimitNbOccurrences(object Value, int NbValuesToKeep) --> 限制特定值的出现次数。
• public void RemoveDuplicates() --> 扫描列表以仅保留每个值的一个代表对象。重复项将被删除。

请注意，SortableList 重写了 Object.ToString() 以将其显示为字符串。为此，将对列表中的每个元素调用相同的函数。

字符串类型对象的示例

public class TestSortableList
{
    public static void Main()
    {
        Console.WriteLine("You create a new SortableList." );
        SortableList SL = new SortableList();

        Console.Write(@"You set KeepSorted property 
           to false add the strings X, B, A and D: " );
        SL.KeepSorted = false;
        SL.Add("X");
        SL.Add("B");
        SL.Add("A");
        SL.Add("D");
        Console.WriteLine(SL);

        Console.Write(@"You can insert or set elements where you want 
           since KeepSorted==false.\nLet's set 'C' instead of 'D': ");
        SL[3] = "C";
        Console.WriteLine(SL);

        Console.Write("You decide to sort the list: ");
        SL.Sort();
        Console.WriteLine(SL);

        Console.Write(@"You now set the KeepSorted property to true 
           and add some new strings:\n");
        SL.KeepSorted = true;
        SL.Add("J");
        SL.Add("E");
        SL.Add("E");
        SL.Add("B");
        SL.Add("X");
        SL.Add("E");
        SL.Add("E");
        Console.WriteLine(SL);

        Console.WriteLine("'E' is found at index " + 
                             SL.IndexOf("E").ToString());
        Console.WriteLine("Does the list contain 'X' ?: " + 
                             SL.Contains("X").ToString());
        Console.WriteLine("Does the list contain 'M' ?: " + 
                             SL.Contains("M").ToString());

        Console.Write("You limit the number 
                           of occurrences of 'E' to 2: ");
        SL.LimitNbOccurrences("E", 2);
        Console.WriteLine(SL);

        Console.Write("After all you do not 
                                  want any duplicates: ");
        SL.RemoveDuplicates();
        Console.WriteLine(SL);

        Console.Write(@"You set AddDuplicates to false 
                         and try to add J and E again.\n
                         They are not actually added: ");
        SL.AddDuplicates = false;
        SL.Add("J");
        SL.Add("E");
        Console.WriteLine(SL);

        Console.Write(@"Now you create another SortableList 
                        but this time you give 
                        it an IComparer \nclass which is 
                        the anti-alphabetical order.");
        SL = new SortableList( new AntiAlphabeticalComparer() );

        Console.Write(@"You fill the list by adding a 
                        range of vowels in alphabetical order. 
                        But the resulting list is: " );
        string[] Vowels = new string[] {"A", "E", "I", "O", "U"};
        SL.AddRange( Vowels );
        Console.WriteLine(SL);
        Console.ReadLine();
    }
    
    class AntiAlphabeticalComparer: IComparer
    {
        public int Compare(object O1, object O2)
        {
            string S1 = O1.ToString();
            string S2 = O2.ToString();
            return -String.Compare(S1, S2);
        }
    }
}

输出

You create a new SortableList.
You set the KeepSorted property to false and 
       add the strings X, B, A, D: {X; B; A; D}
You can insert or set elements where you want since KeepSorted==false.
Let's set 'C' to index 4: {X; B; A; C}
You decide to sort the list: {A; B; C; X}
You now set the KeepSorted property to true and add some new strings:
{A; B; B; C; E; E; E; E; J; X; X}
'E' is found at index 4
Does the list contain 'X' ?: True
Does the list contain 'M' ?: False
You limit the number of occurrences of 'E' to 2: {A; B; B; C; E; E; J; X; X}
After all you do not want any duplicates: {A; B; C; E; J; X}
You set the AddDuplicates property to false and try to add J and E again.
They are not actually added: {A; B; C; E; J; X}
Now you create another SortableList but this time you give it an IComparer
class which is the anti-alphabetical order.
You fill the list by adding a range of vowels in alphabetic order.
But the resulting list is: {U; O; I; E; A}

关注点

首先，在设计类时，我面临了一个爱情与责任的冲突。的确，这里有两种选择：

1. 让 SortableList 继承自 ArrayList。一方面，好处是 ArrayList 中已经定义了许多方法，您无需重写它们。但另一方面，基类的一些其他方法不适用于排序列表。因此，必须私有重写它们，以防止用户使用它们。要控制用户如何操作列表并不容易。例如，如果他将 SortableList 实例强制转换为 ArrayList 怎么办？那么列表就无法知道它是否已排序。
2. 让 SortableList 包含 ArrayList 作为类成员。这是我最终的选择。好处是您可以控制用户对列表的所有操作，因为这些操作完全由您实现。唯一令人恼火的是，您必须定义许多只是调用 ArrayList 成员上的相同方法的方法。没关系。

然后，SortableList 应实现以下接口所需的所有方法：IList（因此 ICollection 和 IEnumerable）和 ICloneable。关于新的和特定的函数，我建议您查看源代码。您会看到，出于性能原因，RemoveDuplicates - 与 IndexOf 等其他方法不同 - 在列表排序和未排序时有不同的处理方式。这里的逻辑是 IComparer.Compare(Obj1,Obj2)==0（或 IComparable.CompareTo(Obj2)==0）必须等同于 Obj1.Equals(Obj2)。

public int IndexOf(object O)
{
    int Result = -1;
    if ( _IsSorted )
    {
        Result = _ArrayList.BinarySearch(O, _Comparer);
        while ( Result>0 && _ArrayList[Result-1].Equals(O) )
          Result--; // Move backward to point at the FIRST occurence
    }
    else Result = _ArrayList.IndexOf(O);
    return Result;
}

最后，我必须控制禁止的操作。通常，您不能执行以下操作。所有这些操作都会触发 InvalidOperationException 或 ArgumentException。

• 将 KeepSorted 属性设置为 true，而 IsSorted 等于 false。
• 使用 Insert 方法之一或设置操作（[]=）。当 KeepSorted 等于 true 时，只有 Add 方法允许将新元素添加到列表中。
• 在构造时没有为列表提供 IComparer 接口，并且用户添加（Add、Insert、[]= 等）的对象不实现 IComparable。

历史

• 2003 年 4 月 18 日 - 初始版本。非常感谢 Lauren K.
• 2003 年 4 月 22 日 - 添加了新功能
  • public int IndexOfMin();
  • public int IndexOfMax();
  • public int IndexOf(object O, EqualityDelegate AreEqual);