.NET Framework源码研究系列之---马甲List

.NET Framework源码研究系列之---马甲List2012-05-13 博客园倪大虾在上一篇随笔<.NET Framework源码研究系列之---Delegate>中我们一起研究了.NET 中是如何实现委托的.今天我们一起研究一下.NET中我们用的最多的一个集合类之一List.

大家都知道,在.NET集合类中List如Array一样都是一个顺序一维数组,与Array不同的是,我们可以更方便的操作List类型的集合,比如插入数据,删除数据,排序等等,那么.NET源码中List 是如何实现的呢？我们在使用List相对Array的优点时会不会有其他方面的代价呢？从List的源码中我们又能学到什么呢？带着这些问题,让我们开始今天的.NET源码研究之旅吧.

研究一开始,首先我们看一下List的类型定义.通过对象浏览器,我们很容易知道List继承了 IList,IEnumerator,ICollection等接口..NET中是这么实现的:

public class List<T> : IList<T>, System.Collections.IList

这里与对象浏览器里看到的不一样,是因为IList接口同样继承自IEnumerator,ICollection 接口.

接下来我们看List包含的字段和构造函数:

然后我们看下List的几个字段.由private const int _defaultCapacity = 4;我们可以看出 List默认最少可以包含4个元素._size字段顾名思义是List当前的长度.通过访问List.Capacity 属性我们可以获取 List当前可以包含多少个元素.通过访问List.Count属性可以获得List当前包含的元素数.那么他们有什么不同呢？经过仔细研究发现,原来 List自增长的实现是这样子的. 每当添加元素的时候,List会先判断_size与_items的长度,如果相等,则size扩展到_size+1到 _items.Length*2.详情请看如下源码:

仔细看上面的代码,我们会发现当复制数组时List并没有自己做,而是调用了Array.Copy这个方法.遍历整个List的实现代码,我们发现List几乎所有的数据操作,如插入,删除,查询,排序,检索等等都是通过Array中相应的静态方法实现的.由此可知上面我说的"List是对Array的一层包装"是正确的.

我们知道List继承了ICollection接口,看对它的实现,我们发现 ICollection.IsSynchronized属性直接返回了false.由此可知List不是线程安全的（用多线程的同学要注意咯,这点与Queue不同）.

在.NET中,遍历一个数组我们可以用两种方法,一个for循环,二是foreach.这两个的区别是一个是顺序遍历,另外一个跟顺序没什么关系..NET中凡是Array和List都支持这两种遍历.学习过设计模式中迭代模式的人这时候看到"与顺序无关的遍历"是不是觉得很熟啊.设计模式中对迭代模式的定义为:

提供一种方法遍历访问一个聚合对象中各个元素，而又不需暴露该对象的内部表示。

没错！List就是一个.NET自带的一个迭代器.严格来说,是因为List实现了IEnumerator接口. 也就是说.NET中凡是实现了IEnumerator接口的都是迭代器.大家在工作中无意识的就拥到的设计模式,是不是觉得很开心呢？！:）

代码看到最后,发现List也提供了Reverse（）方法用于倒排存储的所有元素,该方法的实现居然完全照搬Array.Reverse,至此不得不感慨微软对代码的复用简直做到了极致.也发现了以往居然把这么强大的东西（Array）丢掉了.

最后我们看两个List都有的方法（没有抄袭Array,不容易啊）:

public void TrimExcess（）{
       int threshold = （int）（（（double）_items.Length） * 0.9）;
       if （_size < threshold）{
         Capacity = _size;
       }
     }
     public bool TrueForAll（Predicate<T> match）{
       if （match == null）{
         ThrowHelper.ThrowArgumentNullException （ExceptionArgument.match）;
       }
       for （int i = 0; i < _size; i++）{
         if （！match（_items[i]））{
           return false;
         }
       }
       return true;
     }