C#集合 -- Lists，Queues， Stacks 和 Sets

List<T>和ArrayList

Generic的List和非Generic的ArrayList类支持可变化大小的对象数组，它们也是最常见的集合类。ArrayList实现了IList接口，而List<T>实现了IList<T>和IList接口（以及新增的IReadonlyList<T>）。与数组不同，所有的接口实现都是公开的，并且Add和Remove方法也对外公开；它们会按照你的希望执行。

在List<T>和ArrayList内部，维护了一个内部的数组对象，当这个内部数组对象的大小超过时，创建一个新的数组来替代原数组。附加元素效率很高（因为通常有一个空闲插槽结尾），但插入的元素可能会很慢（因为有插入点之后的所有元素将位移以产生一个空闲插槽）。对于数组而言，如果集合如果是排好序的，那么执行BinarySearch方法非常高效，但从另一个方面而言，这又不高效，因为在执行BinarySearch之前，需要检查每个元素（以排序）。

对于值类型，List<T>的比ArrayList快几倍，这是因为List<T>避免了装箱和拆箱的开销。

List<T>和ArrayList都提供了构造器方法，以接收元素集合；构造器方法遍历集合的元素到新的List<T>或ArrayList对象中。List<T>的定义大致如下：

public class List<T> : IList<T>, IReadOnlyList<T>
{
public List ();
public List (IEnumerable<T> collection);

public List (int capacity);
// Add+Insert
public void Add (T item);
public void AddRange (IEnumerable<T> collection);
public void Insert (int index, T item);
public void InsertRange (int index, IEnumerable<T> collection);
// Remove
public bool Remove (T item);
public void RemoveAt (int index);
public void RemoveRange (int index, int count);
public int RemoveAll (Predicate<T> match);
// Indexing
public T this [int index] { get; set; }
public List<T> GetRange (int index, int count);
public Enumerator<T> GetEnumerator();

// Exporting, copying and converting:
public T[] ToArray();
public void CopyTo (T[] array);
public void CopyTo (T[] array, int arrayIndex);
public void CopyTo (int index, T[] array, int arrayIndex, int count);
public ReadOnlyCollection<T> AsReadOnly();
public List<TOutput> ConvertAll<TOutput> (Converter <T,TOutput>
converter);
// Other:
public void Reverse(); // Reverses order of elements in list.
public int Capacity { get;set; } // Forces expansion of internal array.
public void TrimExcess(); // Trims internal array back to size.
public void Clear(); // Removes all elements, so Count=0.
}

除了上述方法之外，List<T>还提供了与Array类一样的搜索和排序的实例方法。下面的例子演示了List的属相和方法：

static void Main(string[] args)
{
    List<string> words = new List<string>();
    words.Add("melon");
    words.Add("avocado");
    words.AddRange(new[] { "banana", "plum" });
    words.Insert(0, "lemon");
    words.InsertRange(0, new[] { "peach", "nashi" });

    words.Remove("melon");
    words.RemoveAt(3);
    words.RemoveRange(0, 2);
    words.RemoveAll(s => s.StartsWith("n"));

    Console.WriteLine(words[0]);
    Console.WriteLine(words[words.Count - 1]);
    foreach (string s in words)
        Console.WriteLine(s);

    string[] wordsArray = words.ToArray();

    string[] existing = new string[1000];
    words.CopyTo(0, existing, 998, 2);

    List<string> upperCastwords = words.ConvertAll(s => s.ToUpper());
    List<int> lenghts = words.ConvertAll(s => s.Length);
    
    Console.ReadLine();
}

而非generic的ArrayList主要用于和Framework1.x的代码兼容，因为其要求一个类型转换，比如下面的代码

ArrayList al = new ArrayList();
al.Add ("hello");
string first = (string) al [0];
string[] strArr = (string[]) al.ToArray (typeof (string));

而这样的转换不能被编译器验证，因此下面的代码可以通过编译，但是在运行时却会报错

int first = (int) al [0];

ArrayList和List<Object>类似。两者在处理混合类型的集合时非常有用。有一种场景特别适合使用ArrayList，那么就是处理反射时。

如果你引用了System.Linq命名空间，那么你就使用LINQ的Cast方法把一个ArrayList转换成一个Generic的List

ArrayList al = new ArrayList();
al.AddRange(new[] { 1, 5, 9 });
List<int> list = al.Cast<int>().ToList();

Cast和ToList方法时System.Linq.Enumerable类的扩展方法。Cast方法首先尝试直接把ArrayList转换成List，如果转换不成功，那么遍历ArrayList，转换每个元素，并返回IEnumerable<T>。而ToList()方法则是直接调用List<T>的构造函数public List (IEnumerable<T> collection)；从而实现IEnumerable<T>转换成List<T>。

List<T>接收值为null的引用类型；此外List<T>还允许重复的元素。

List<T>既适用相等性比较器，也使用排序比较器。当调用Contains, IndexOf, LastIndeoxOf, Remove等方式时，会使用相等性比较器。List<T>会使用T类型的默认相等比较器。如果T类型实现了IEquatable<T>接口，那么调用该接口的Equals(T)方法；否则调用Object.Equals(Object)方法进行相等性比较。List<T>的BinarySearch、Sort方法使用排序比较器。同相等性比较器一样，List<T>会使用T类型的默认排序比较器，如果T类型实现了IComparable<T>接口，那么调用该接口的CompareTo(T)方法，否则使用非Generic接口IComparable的CompareTo(Object)方法。

List<T>的静态成员是线程安全的，而实例成员不能确保类型安全。多线程读取IList<T>是线程安全的，但是如果在读的过程中被修改了，那么就会引发问题，比如下面的代码：

class Program
{
    static List<int> numbers = new List<int>();

    static void Main(string[] args)
    {
        numbers.Add(0);

        Thread t1 = new Thread(GetNum);
        t1.Start();
        Thread t2 = new Thread(SetNum);
        t2.Start();

        Console.ReadLine();
    }

    static void GetNum()
    {
        Console.WriteLine("t1->" + numbers[0]);  // -> 0
        Thread.Sleep(1000);
        Console.WriteLine("t1->" + numbers[0]); // -> 2
    }
    static void SetNum()
    {
        numbers[0] = 2;
        Console.WriteLine("t2->" + numbers[0]); // ->2
    }

}

在GetNum方法中，两次读取List<Int>的第一个元素时，值发生变化。因此，我们需要手动实现线程同步。一般常用的方式时使用lock锁住List<T>对象

class Program
{
    static List<int> numbers = new List<int>();
    static object locker = new object();

    static void Main(string[] args)
    {
        numbers.Add(0);

        Thread t1 = new Thread(GetNum);
        t1.Start();
        Thread t2 = new Thread(SetNum);
        t2.Start();

        Console.ReadLine();
    }

    static void GetNum()
    {
        lock (locker)
        {
            Console.WriteLine("t1->" + numbers[0]);  // -> 
            Thread.Sleep(1000);
            Console.WriteLine("t1->" + numbers[0]); // -> 0
        }
    }
    static void SetNum()
    {
        lock (locker)
        {
            numbers[0] = 2;
            Console.WriteLine("t2->" + numbers[0]); // ->2
        }
    }

}

另外，微软在System.Collection.Concurrent命名空间下，提供了几个用于并发的集合类

LinkedList<T>

LinkedList<T>是双向链表列表。所谓双向链表列表就是这样节点链条，每个节点都包含前一个节点引用，后一个节点引用，以及自己的引用。它最大的益处就是可以高效地插入元素到列表的任意位置，因为它值需要创建一个新的节点，然后更新相关引用（前一个节点的引用和后一个节点的引用）。然后向链表列表的第一个位置插入新的节点可能会很慢，这是因为在链表内部没有内在的索引机制，因此每次节点都需要遍历，而且也不能使用二进制印章（binary-chop）搜索。下图是LinkedList<T>示意图

LinkedList<T>实现了IEnumerable<T>接口和ICollection<T>接口，但没有实现IList<T>接口，所以其不支持索引。

LinkedListNode的代码大致如下：

public sealed class LinkedListNode<T> {
    internal LinkedList<T> list;
    internal LinkedListNode<T> next;
    internal LinkedListNode<T> prev;
    internal T item;
    
    public LinkedListNode( T value) {
        this.item = value;
    }

    internal LinkedListNode(LinkedList<T> list, T value) {
        this.list = list;
        this.item = value;
    }

    public LinkedList<T> List {
        get { return list;}
    }

    public LinkedListNode<T> Next {
        get { return next == null || next == list.head? null: next;}
    }

    public LinkedListNode<T> Previous {
        get { return prev == null || this == list.head? null: prev;}
    }

    public T Value {
        get { return item;}
        set { item = value;}
    }

    internal void Invalidate() {
        list = null;
        next = null;
        prev = null;
    }           
}

当向LinkedList<T>添加一个节点时，你可以致命节点的位置，或者相对于另一个节点的位置，或者列表的开始/结束位置。LinkedList<T>提供了下面的方法添加节点

public void AddFirst(LinkedListNode<T> node);
public LinkedListNode<T> AddFirst (T value);
public void AddLast (LinkedListNode<T> node);
public LinkedListNode<T> AddLast (T value);
public void AddAfter (LinkedListNode<T> node, LinkedListNode<T> newNode);
public LinkedListNode<T> AddAfter (LinkedListNode<T> node, T value);
public void AddBefore (LinkedListNode<T> node, LinkedListNode<T> newNode);
public LinkedListNode<T> AddBefore (LinkedListNode<T> node, T value);

与之对应，提供了删除节点的方法

public void Clear();
public void RemoveFirst();
public void RemoveLast();
public bool Remove (T value);
public void Remove (LinkedListNode<T> node);

LinkedList<T>内部有字段用于追踪列表中元素的数量，首节点和尾节点：

public int Count { get; } 
public LinkedListNode<T> First { get; } 
public LinkedListNode<T> Last { get; }

LinkedList还支持下面的搜索方法

public bool Contains (T value);
public LinkedListNode<T> Find (T value);
public LinkedListNode<T> FindLast (T value);

最后，LinkedList<T>支持支持从数组复制元素，并提供了列举器以支持foreach语法

public void CopyTo (T[] array, int index);
public Enumerator<T> GetEnumerator();

下面的示例演示了如果使用LinkedList<T>

static void Main(string[] args)
{
    var tune = new LinkedList<string>();
    tune.AddFirst("do"); // do
    tune.AddLast("so"); // do - so
    tune.AddAfter(tune.First, "re"); // do - re- so
    tune.AddAfter(tune.First.Next, "mi"); // do - re - mi- so
    tune.AddBefore(tune.Last, "fa"); // do - re - mi - fa- so
    tune.RemoveFirst(); // re - mi - fa - so
    tune.RemoveLast(); // re - mi - fa
    LinkedListNode<string> miNode = tune.Find("mi");
    tune.Remove(miNode); // re - fa
    tune.AddFirst(miNode); // mi- re - fa
    foreach (string s in tune) Console.WriteLine(s);

    Console.ReadLine();
}

Queue<T>和Queue

Queue<T>和Queue是先进先出(FIFO)的数据结构，通过Enqueue和Dequeue方法实现添加元素到队列的尾部和从队列的头部移除元素。Peek方法从队列的头部获取一个元素（不移除该元素），Count属性用来统计队列中元素的个数（在执行出列操作时检查元素是否存在非常有用）。

尽管队列是可遍历的，但是它们并没有实现IList<T>接口和IList接口，因此也不能通过索引来访问队列中的元素。虽然也提供了ToArray方法，但是在复制元素时是从队列中随机读取的。

Queue的定义大致如下：

public class Queue<T> : IEnumerable<T>, ICollection, IEnumerable
{
public Queue();
public Queue (IEnumerable<T> collection); // Copies existing elements
public Queue (int capacity); // To lessen auto-resizing
public void Clear();
public bool Contains (T item);
public void CopyTo (T[] array, int arrayIndex);
public int Count { get; }
public T Dequeue();
public void Enqueue (T item);
public Enumerator<T> GetEnumerator(); // To support foreach
public T Peek();
public T[] ToArray();
public void TrimExcess();
}

下面的示例演示了如何使用Queue<T>

var q = new Queue<int>();
q.Enqueue (10);
q.Enqueue (20);
int[] data = q.ToArray(); // Exports to an array
Console.WriteLine (q.Count); // "2"
Console.WriteLine (q.Peek()); // "10"
Console.WriteLine (q.Dequeue()); // "10"
Console.WriteLine (q.Dequeue()); // "20"
Console.WriteLine (q.Dequeue()); // throws an exception (queue empty)

Queue内部使用一个按需更改大小的数组来实现，这与List<T>类似。Queue使用索引指向队列的头部和尾部元素；因此，入列和出列操作都非常快速。

Stack<T>和Stack

Stack<T>和Stack则是后进先出的数据结构，通过Push和Pop法实现添加元素到队列的顶部和从队列的顶部移除元素。同样也提供了Peek方法、Count属性和ToArray方法。其定义大致如下：

public class Stack<T> : IEnumerable<T>, ICollection, IEnumerable
{
public Stack();
public Stack (IEnumerable<T> collection); // Copies existing elements
public Stack (int capacity); // Lessens auto-resizing
public void Clear();
public bool Contains (T item);
public void CopyTo (T[] array, int arrayIndex);
public int Count { get; }
public Enumerator<T> GetEnumerator(); // To support foreach
public T Peek();
public T Pop();
public void Push (T item);
public T[] ToArray();
public void TrimExcess();
}

下面的示例演示了如何使用Queue<T>

var s = new Stack<int>();
s.Push (1); // Stack = 1
s.Push (2); // Stack = 1,2
s.Push (3); // Stack = 1,2,3
Console.WriteLine (s.Count); // Prints 3
Console.WriteLine (s.Peek()); // Prints 3, Stack = 1,2,3
Console.WriteLine (s.Pop()); // Prints 3, Stack = 1,2
Console.WriteLine (s.Pop()); // Prints 2, Stack = 1
Console.WriteLine (s.Pop()); // Prints 1, Stack = <empty>
Console.WriteLine (s.Pop()); // throws exception

与Queue<T>和List<T>一样，Stacks内部使用一个按需更改大小的数组来实现。

BitArray

BitArray是一个都bool值组成的、大小可动态变化的集合。它比bool[]或List<bool>有更多的内存效率，这是因为每个元素都值占用一bit的内存空间，而bool类型则占用1byte空间（1byte=8bit）。通过索引器可以读取和更改BitArray元素的值。

var bits = new BitArray(2);
bits[1] = true;

BitArray提供了四个位运算（Add, Or, Xor和Not）。最后最后一个方法之外，其他的三个方法接收另外一个BitArray

bits.Xor (bits); // Bitwise exclusive-OR bits with itself
Console.WriteLine (bits[1]); // False

这三个方法很简单，下面的代码展示了如何使用它们

static void Main(string[] args)
{
    BitArray array1 = new BitArray(new[]{true, false, false, true, true});
    BitArray array2 = new BitArray(new[] { true, false, true, false, false });
    
    Console.WriteLine("--Or--");
    foreach (bool b in array1.Or(array2))
        Console.WriteLine(b);

    array1 = new BitArray(new[] { true, false, false, true, true });
    array2 = new BitArray(new[] { true, false, true, false, false });

    Console.WriteLine("
--And--");
    foreach (bool b in array1.And(array2))
        Console.WriteLine(b);

    array1 = new BitArray(new[] { true, false, false, true, true });
    array2 = new BitArray(new[] { true, false, true, false, false });

    Console.WriteLine("
--Xor--");
    foreach (bool b in array1.Xor(array2))
        Console.WriteLine(b);

    Console.ReadLine();
}

HasSet<T>和SortedSet<T>

HashSet<T>在Framework3.5才新增的，而SortedSet<T>是Framework4.0新增的。两者都有下面的特性

• 基于哈希的查询使得Contains执行非常快速
• 两个集合都不存储重复的元素，如果试图添加重复元素会自动忽略
• 不能通过位置（索引）获取元素

SortedSet<T>的元素是排过序的，而HashSet<T>的元素未排序。

HashSet<T>通过一个存贮键值的哈希表来实现；SortedSet<T>是通过红黑树实现。

两个集合都实现了ICollection<T>接口，因为都提供了Contains，Add和Remove方法；此外，还有一个移除元素的方法RemoveWhere。

下面的代码演示了构建一个HashSet<Char>集合，然后测试Contains方法，最后通过遍历输出集合元素

var letters = new HashSet<char> ("the quick brown fox");
Console.WriteLine (letters.Contains ('t')); // true
Console.WriteLine (letters.Contains ('j')); // false
foreach (char c in letters) Console.Write (c); // the quickbrownfx

这两个集合类还包含了下面的几个有意思的方法：对集合进行操作，并修改原集合

public void UnionWith (IEnumerable<T> other); // Adds
public void IntersectWith (IEnumerable<T> other); // Removes
public void ExceptWith (IEnumerable<T> other); // Removes
public void SymmetricExceptWith (IEnumerable<T> other); // Removes

而下面的方法简单的查询集合，因此它们不会更改原集合：

public bool IsSubsetOf (IEnumerable<T> other);
public bool IsProperSubsetOf (IEnumerable<T> other);
public bool IsSupersetOf (IEnumerable<T> other);
public bool IsProperSupersetOf (IEnumerable<T> other);
public bool Overlaps (IEnumerable<T> other);
public bool SetEquals (IEnumerable<T> other);

UnionWith方法把第二个集合中的元素添加到原集合中（重复的元素自动排除）。而InsersectWith方法移除在两个集合中都不存在的元素（是两个集合取交集）。

var letters = new HashSet<char> ("the quick brown fox");
letters.IntersectWith ("aeiou");
foreach (char c in letters) Console.Write (c); // euio

而ExceptWith则表示从原集合中删除指定的元素（两个集合相减）。

var letters = new HashSet<char> ("the quick brown fox");
letters.ExceptWith ("aeiou");
foreach (char c in letters) Console.Write (c); // th qckbrwnfx

SymmetricExceptWith方法删除既属于集合A和集合B交集之外的那些元素

var letters = new HashSet<char> ("the quick brown fox");
letters.SymmetricExceptWith ("the lazy brown fox");
foreach (char c in letters) Console.Write (c); // quicklazy

请注意，HashSet<T>和SortedSet<T>都实现了IEnumerable<T>，因此你在使用它们的集合操作方法时，可以把另一个集合当作该集合操作的参数。比如，你在使用HashSet<T>的集合操作，可以传一个SortedSet<T>。

SortedSet<T>比HashSet<T>还多了下面的几个方法

public virtual SortedSet<T> GetViewBetween (T lowerValue, T upperValue)
public IEnumerable<T> Reverse()
public T Min { get; }
public T Max { get; }

SortSet<T>的构造函数还接收IComparer<T>参数。

下面的例子演示了如何使用SortedSet<T>：

var letters = new SortedSet<char> ("the quick brown fox");
foreach (char c in letters) Console.Write (c); // bcefhiknoqrtuwx

参考链接：

http://stackoverflow.com/questions/2980283/thread-safe-collections-in-net

http://en.wikipedia.org/wiki/Red_black_tree