十六章：构建自定义集合（Part 1）

 IList<T> 和 IDictionary<TKey, TValue>

IList<T> 和 IDictionary<TKey, TValue> 都继承了ICollection<T>泛型接口。IList 是 IDictionary的一种特例，IList的key总是一个整数，key set 总是从0开始的非负整数(non-negative integers)的连续集合。

区别：IList用索引(Index)来取值, IDictionary用键值(key)来取值。所以虽然两个接口都实现索引器，但是实现索引器的方法是不同的。

IComparable<T>

这个接口对于集合来说非常重要，因为每个集合类都有一个Sort()方法。如果你需要采用某种方法对集合中的元素进行排序，有两种方法。

 1、 使用元素的IComparable<T>接口来实现。该接口只有一个方法，int CompareTo(T other)，指出传递的元素是大于、小于还是等于当前元素。

 2、 使用自定义排序。向Sort()方法中传递实现了IComparer<T>接口的参数。该接口也只有一个方法，int Compare(T x, T y);。

ICollection<T>

该接口是从IEnumerable<T>派生的。并包含多个成员：

 1、Count属性，返回集合中的元素。如果我们要使用for循环返回集合中的元素，那么集合必须支持按照索引来获取值，ICollection不包括这个功能。但是IList包括。

 2、CopyTo(T[] array, int arrayIndex), index用于指定在目标数组的什么位置插入元素。但是应该注意的是目标数组要足够大。

 3、Add(T item). 该方法用于实现 collection initializers (集合初始化器)。 集合初始化器要编译成功，有两种方法，一种是该集合继承了ICollection<T>接口，一种是放宽的版本。继承了IEnumerable<T> 并且提供了一个或者多个Add()方法。

索引运算符（index operator）

T this[PairName name]{get;set;}。索引的参数可以是任何类型，也可以是多个参数，也可以重载。

索引器（[]）的CIL属性名称默认为Item。但是可以使用[System.Runtime.CompilerServices.IndexerName("Entry")]这个Attribute来修改。

也可以定义变参的索引运算符。

主要集合类

1、列表集合 List<T>

　　列表和数组类似属性，关键的区别就是随着元素数量的增大，列表类会自动扩展。

　　每个元素都可以按照索引来访问，这个个数组是一样的。

　　根据索引来获取元素的时候，不会造成一次遍历操作，只会直接跳到一个内存位置。

　　如果需要对添加的元素进行排序，那么需要调用Sort（）方法，并且保证元素继承了ICompareable接口。

　　Contains(T item), IndexOf(T item), LastIndexOf(T item)都会遍历列表，所以执行时间和发现匹配项之前的实际搜索的元素数量成正比。

　　BinarySearch()采用的是二分搜索算法，它要求元素已经排好顺序。最大的特点是，如果元素没有找到，会返回一个负数，该值按位取反（~）后的结果是“大于被查找元素的下一个元素”的索引。如果没有更大的值，则是元素总和。这样的好处是可以在列表中特定位置方便的插入新值，并且保持已排序的状态。即二分插入。

　　List<T> FindAll(Predicate<T> match): 调用该方法时，传递委托实例。public static bool Method1(int value). 每次返回true时，相应的项就被添加到一个新的list<T>实例中，最后该实例会返回。

2、字典集合 Dictionary<TKey, TValue>

　　虽然字典比列表复杂，但是利用键来查询的效率非常高，因为键存储在一个散列表中。键可以为任意数据类型。

　　如果用了相同的键值，那么第二次赋值会覆盖第一次赋值。

　　移除一个元素，采用Remove(TKey)方法。

　　字典类没有特定的排序。元素也是用散列码存储在一个散列表中，这样可以实现快速检索，调用GetHashCode(),并向他传递键值，即可获取散列码。用foreach遍历Dictionary时，返回的数据类型是KeyValuePair<TKey, TValue>. 如果想单独处理key或者value，则可以用属性Keys和Values.它们的返回值分别是Dictionary<TKey, TValue>.KeyCollection和Dictionary<TKey, TValue>.ValueCollection。

3、栈集合 Stack<T>

　　后入先出的集合（LIFO)。

　　Push()将元素送入集合，元素不用唯一。

　　Pop()按照与添加时相反的顺序获取并删除元素。

　　Peek()返回Pop()将获取的元素，但是不删除该元素。

　　Contains()判断元素是否存在。

　　用foreach不会删除栈中元素。

4、队列集合 Queue<T>

　　先入先出的集合(FIFO)。元素不必唯一。

　　Enqueue(), Dequeue()分别和栈中的Push(),Pop()对应。

　　队列会自动增大。不再需要数据时，使用TrimToSize()恢复以前的容量。

5、链表 LinkedList<T>

　　允许正反向遍历。没有和它对应的非泛型类型。

　　AddAfter(LinkedListNode<T> node, LinkedListNode<T> new node); AddBefor(); AddFirst();AddLast(); Find(T);FindLast();Remove();RemoveFirst();RemoveLast();