Effective C# 原则40：根据需求选择集合

“哪种集合是最好的？”答案是：“视情况而定。” 不同的集合有不同的性能，而且在不同的行为上有不同的优化。.Net框架支持很多类似的集合：链表，数组，队列，栈，以及其它的一些集合。C#支持多维的数组，它的性能与一维的数组和锯齿数组都有所不同。.Net框架同样包含了很多特殊的集合，在你创建你自己的集合类之前，请仔细参阅这些集合。你可以发现很多集合很快，因为所有的集合都实现了ICollection接口。在说明文档中列出了所有实现了ICollection接口的集合，你将近有20多个集合类可用。

为了选择适合你使用的集合，你须要考虑在该集合上使用的操作。为了创建一个有伸缩性的程序，你须要使用一些实现了接口的集合类，这样当你发现某个假设的集合不正确时，你可以用其它不同的集合来代替它(参见原则19)。

.Net框架有三种不同类型的集合：数组，类似数组的集合，以及基于散列值的集合。数组是最简单的也是一般情况下最快的集合，因此我们就从它开始。这也是你经常要使用到的集合类。

你的第一选择应该经常是System.Array类，确切的说，应该是一个数组类型的类。 选择数组类的首要原因，也是最重要的原因是数组是类型安全的。所有其它集合都是存储的System.Object引用，直到C#2.0才引入了范型(参见原则49)。当你申明一个数组时，编译器为你的类型创建一个特殊的System.Array派生类。例如：这样创建了申明并创建了一个整型的数组：

private int [] _numbers = new int[100];

这个数组存储的是整型，而不是System.object的引用。这很重要，因为你在一个数组上添加，访问，删除值类型时，可以避免装箱与拆箱操作的性能损失(参见原则17)。上面的初始化操作创建了一个一维的数组，里面存放了100个整数。所有被数组占用的内存都被清0了。值类型数组都是0，而引用数组都是null。所有在数组里的元素可以用索引访问：

int j = _numbers[ 50 ];

另外，访问数组时还可以用foreach迭代，或者使用枚举器：

foreach (int i in _numbers)
  Console.WriteLine(i.ToString());

// or:
IEnumerator it = _numbers.GetEnumerator();
while(it.MoveNext())
{
  int i = (int) it.Current;
  Console.WriteLine(i.ToString());
}

如果准备存储单一次序的对象，你应该使用数组。但实际上你的数据结构往往比这复杂的多。这很快诱使我们回到了C风格上的锯齿数组，那就是一个数组里存储另一个数组。有些时候这确实是你想要的，每个外层元素都是内层的一个数组：

public class MyClass
{
  // Declare a jagged array:
  private int[] [] _jagged;

  public MyClass()
  {
    // Create the outer array:
    _jagged = new int[5][];

    // Create each inner array:
    _jagged[0] = new int[5];
    _jagged[1] = new int[10];
    _jagged[2] = new int[12];
    _jagged[3] = new int[7];
    _jagged[4] = new int[23];
  }
}

每个内层的一维数组可以有同不的大小。在需要不同大小的数组时可以使用锯齿数据。使用锯齿数组的缺点是在列方面上的访问是底效的。检查一个每行上有三个列的锯齿数组时，每次访问都要做两个检测 。在行0列3上的元素和在行1列3的元素没有任何关系。只有多维数组才可在以列方面上的访问有一定的效率。过去，C和C++程序使用二维或多维数组时是把它们映射到一个一维数组上。对于老式的C和C++程序员，这样的标记应该很清楚：

double num = MyArray[ i * rowLength + j ];

这个世界上的其它人可能更喜欢这样：

double num = MyArray[i, j];

但，C和C++其实并不支持多维数组。C#可以，而且对于多维数组的语法：当你创建一个真实的多维数组时，对于编译器和你来说意义都是很清楚的。创建多维数组时只用在熟悉的一维数组标记上扩展一下就行了：

private int[,] _multi = new int[10, 10];

前面的申明创建了一个二维数组，而且是10X10的100个元素。在多维数组上的每一维的长度总是一致的。编译器利用这一特性，可以创建更高效的代码。初始化锯齿数组时须要多次使用初始语句。而在我前面的例子里(译注：指这里：private int[] [] _jagged;)，你须要5个语句。更大的数组或者更多维的数组须要更多的初始代码，而且你要手动编写。然而 ，多维数组在初始化时只要指定多少维就行了。此外，多维数组在初始化元素时更有效。以于值类型数组在初始化时是直接在有效的数组索引上包含该值，所有的内容就是0。而引用类型的数组则是null。数组的数组在内层上都包含null引用。

访问多维数组时比访问锯齿数组要快得多，特殊是在列或者对角线上访问时。编译器在数组的每个维上是使用的指针算法。锯齿数组则要为每个一维数组查找正确的(指针引用)值。

多维数组可以当成数组在很多情况下使用。假设你创建一个棋盘游戏，你可能须要在一个格子上创建一个64个方格的棋盘：

private Square[ , ] _theBoard = new Square[ 8, 8 ];

这个初始化创建了数组来存储方格，假设这些方格是引用类型，这些方格自己还没有创建，而且每个元素还是null。为了初始化每个元素，你还要检测数组上的每一维元素：

for(int i = 0; i < _theBoard.GetLength( 0 ); i++)
  for(int j = 0; j < _theBoard.GetLength( 1 ); j++)
    _theBoard[ i, j ] = new Square();

你你还有更灵活的方法来访问多维数组，你可以给定个别的元素索引来访问该元素：

Square sq = _theBoard[ 4, 4 ];

如果你要迭代整个集合，你还可以使用迭代器：

foreach(Square sq in _theBoard )
  sq.PaintSquare();

与锯齿数组相比，你可能要这样写：

foreach(Square[] row in _theBoard)
  foreach(Square sq in row)
    sq.PaintSquare();

锯齿数组里的每一个新的维引用了另一个foreach语句。然而，对于一个多维数组，每一个foreach语句都要产生代码来检测数组每个维上的界线。foreach语句在每个维上生成特殊的代码来迭代数组。foreach循环生成的代码与你这样手写是一样的：

for (int i = _theBoard.GetLowerBound(0);
  i <= _theBoard.GetUpperBound(0); i++)
  for(int j = _theBoard.GetLowerBound(1);
    j <= _theBoard.GetUpperBound(1); j++)
    _theBoard[i, j].PaintSquare();

考虑在内层循环上所有对GetLowerBound 和GetUpperBound 的调用，这看上去是认低效的，但这确实是很高效的结构。JIT编译器对数组类是很了解的，它们会缓存数组界线，而且可以识别内层的迭代界线从而省略它们(参见原则11)。

数组类的两个主要的不利因素可能会让你考虑使用.Net框架里的其它集合类。第一个影响就是改变数组的大小：数组不能动态的改变大小。如果你须要修改任意数组及任意维数的大小，你必须创建一个新的数组，然后拷贝所有已经存在的元素到新的数组里。改变大小要花时间：因为新的数组要分配，而且所有的元素要拷贝到新的数组里。尽管拷贝和移动在托管堆上并不是像使用C和C++的年代那样开销昂贵，但还是很花时间。更重要的是，它会让数据使用陈旧。考虑下面的代码：

private string [] _cities = new string[100];

public void SetDataSources()
{
  myListBox.DataSource = _cities;
}

public void AddCity(string CityName)
{
  String[] tmp = new string[_cities.Length + 1];
  _cities.CopyTo(tmp, 0);
  tmp[_cities.Length] = CityName;

  _cities = tmp; // swap the storage.
}

即使在调用AddCity 之后，列表框的数据源还是使用拷贝前的旧数据。你新添加的城市根本没有在列表框中显示。

ArrayList类是在数组上的一个高度抽象类。ArrayList集合混合了一维数组和链表的语义。你可以在ArrayList使用迭代，而且你可以调整它的大小。ArrayList基本上把所有责任都委托给了它所包含了数组上，这就是说ArrayList类与数组类在性能上很接近。它的最大好处就是在你不清楚你的集合具体要多大时，ArrayList类要比数组类好用得多。ArrayList可以随时扩展和收缩。但你还是要在移动和拷贝元素上有性能损失，但这些算法的代码已经写好了而且经过了测试。因为内部存储的数组已经封装在ArrayList对象内，因此陈旧数据的情况就不存在了：用户的指针是指向ArrayList对象而不是内部的数组。.Net框架里的ArrayList集合有点类似C++中标准库里的向量类。

队列和栈类在System.Array类上提供了特殊的接口。这些特殊的接口是自定义的先进先出的队列接口和后进先出的栈接口。时刻记住，这些集合的内部存储都是基于数组的。在修改集合的大小时同样会得到性能的损失。
(译注：对于这样的一些集合，在初始化时都有一个大小的参数，应该尽可能的给定集合的容量大小，这里的大小并不是一次性申明和使用的，而是集合中的元素小于这个大小时，不会有移动和拷贝元素的性能损失。因此合理的选择这些集合的容量大小是很关键的。队列的默认大小是32，而栈的默认大小是10，ArrayList默认是0。而它们的构造函数都有一个重载版本可以指定容量。)

.Net中的集合没有包含链表(linked list)结构。垃圾回收器的高效使得列表(list)结构在实际使用是占用时间最小，因此也让它成为了最佳选择。如果你确实须要链表的行为，你有两个选择。如果你因为希望经常添加和删除里面的元素而选择了列表，那么使用null引用的字典类。简单的存储关键字，你就可以使用ListDictionary 类了，而且它用键/值对应方式实现了单向链表。或者你可以选择HybridDictionary类，这是一个为小集合使用了ListDictionary的类，而且对于大集合会转化到HashTable上来。这些集合以及很多其它内容都在 System.Collections.Specialized 名字空间里。然而，如果因为用户想控制次序而你想使用列表结构，你可以使用ArrayList 集合。ArrayList 可以在任何位置上执行插入操作，即使它的内部是使用的数组存储方式。

另外两个类支持基于字典的集合：SortedList 和Hashtable。它们都是包含键/值对应的。SortedList以键进行排序，而Hashtable则没有。Hashtable在给定的键上进行查找时更快，但SortedList提供了基于键的有序迭代。Hashtable 通过键的散列值进行查找。如果散列值是高效的，它的查找时间是一个常量，O(1)。有序列表是使用的折半查找算法来查找关键值。这中一个对数的算法操作 ：O(ln n)。

最后，就是BitArray类。正如它的名字所说的，它存储位数值。BitArray是以整数的数组来存储数据的。每个整型存储一个32位的二进制值。这让BitArray类是压缩的，但它还是会降低性能。BitArray 上的每个get和set操作要在存储的整数上完成位操作，这要查找另外的31个位。BitArray 包含的一些方法在很多值类型上实现了立即的Boolean操作：OR, XOR, AND, 和NOT。这些方法用BitArray做为参数，而且BitArray可以用于快速的多位mask操作，BitArray 是一个为位操作进行优化了的容器；经常使用mask操作时，要存储这些位标记的数据时应该使用它。但不要用它灰替换一般用图和Boolean值数组。

对于数组类的概念而言，在C#的1.x发布版中，没有一个集合类是强类型的。它们都是存储的对象引用。C#的范型将会在所有这些拓扑上包含新的版本。这会是一个最好的方法来创建类型安全的集合。同时，目前的System.Collections 名字空间中包含了抽象的基类，利用这些基类，你可以在类型不安全的集合上创建你自己的类型安全的接口：CollectionBase 和ReadOnlyCollectionBase 提供了列表和向量结构的基类。DictionaryBase 提供了键/值对应的基类。DictionaryBase类是建立在Hashtable上的，它的性能与Hashtable是一致的。

译注：在C#1.x中，我们其实可以合建类型安全的集合，当然这只是利用编译器一些特性，例如：

 public class MyObject
 {
 }

 public class MyObjectCollection : ArrayList
 {
  [ObsoleteAttribute("Please use specify object.",true)]
  public override int Add(object value)
  {
   return base.Add (value);
  }

  public int Add(MyObject value)
  {
   return base.Add (value);
  }

  new public MyObject this[int index]
  {
   get
   {
    return base[index] as MyObject;
   }
   set
   {
    base[index] = value;
   }
  }
 }

这样就可以简单的验证集合的类型了，当然，本质上还是类型不安全的，这只是一个折衷的办法。

任何时候，你的类型包含集合时，你可能想要把这些集合在你的类上暴露给你的用户。你有两个方法：使用索引或者使用IEnumerable接口。记住，在这一原则的一开始，我就说明过，你可以直接使用[]标记来访问一个数组里的元素，而且你可以用foreach来迭代数组里的任何元素。

你可以为你的类创建多维的索引，以C++里你可能须要重载[]操作。而在C#里，你可以创建多维索引：

public int this [int x, int y]
{
  get
  {
    return ComputeValue(x, y);
  }
}

添加对索引器的支持就是说你的类型包含一个集合。这也就是说你应该支持IEnumerable 接口。IEnumerable 提供了标准的机制来迭代所有的集合元素：

public interface IEnumerable
{
  IEnumerator GetEnumerator( );
}

GetEnumerator 方法返回一个实现了IEnumerator 接口的对象。IEnumerator 接口支持集合的历遍：

public interface IEnumerator
{
  object Current{ get; }

  bool MoveNext();

  void Reset();
}

另外，在使用IEnumerable 接口时，如果你的类型模型是数组，你应该考虑IList 和ICollection 接口。如果你的类型模型是字典，你应该考虑实现IDictionary 接口。你可以自己创建对这些功能强大的接口的实现，而且你可能要花上更多的几页代码来解释如何实现。但这里有一个简单的解决方案：在你创建自己的特殊集合类时从CollectionBase 或者DictionaryBase 派生你的类。

让我们回顾一下今天的内容，最好的集合取决于你对操作的实现，以及应用程序对空间和时间的目标要求。在大多数情况下，数组提供了最高效的容器。C#里扩展的多维数组，可以简单的实现多维的结构，而且没有性能的损失。当我们的应用程序须要对元素进行更灵活的添加和移动操作时，使用众多集合中更活越的一个就行了。最后，当你创建自己的集合模型类时，不论什么时候都实现索引器和IEnumerable接口。