程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> .NET網頁編程 >> 關於.NET >> .net源碼分析 – List<T>

.net源碼分析 – List<T>

編輯:關於.NET

通過分析源碼可以更好理解List<T>的工作方式,幫助我們寫出更穩定的代碼。

List<T>源碼地址: https://github.com/dotnet/corefx/blob/master/src/System.Collections/src/System/Collections/Generic/List.cs。

接口

List<T>實現的接口:IList<T>, IList, IReadOnlyList<T>

其實.net framework經過多代發展,List的接口確實是有點多了,添加新功能時為了兼容老功能,一些舊的接口又不能丟掉,所以看上去有點復雜。先把這些接口捋一下:

IEnumerator是枚舉器接口,擁有枚舉元素的功能,成員有Current, MoveNext, Reset,這三個函數可以使集合支持遍歷。

IEnumerable是支持枚舉接口,實現這接口表示支持遍歷,成員就是上面的IEnumerator。

ICollection是集合接口,支持著集合的Count屬性和CopyTo操作,另外還有同步的屬性IsSynchronized(判斷是否線程安全)和SyncRoot(lock的對象)。

IList是集合的操作接口,支持索引器,Add, Remove, Insert, Contains等操作。

泛型部分基本是上面這些接口的泛型實現,不過IList<T>的一些操作放到ICollection<T>裡了,可能微軟也覺得對於集合的一些操作放到ICollection更合理吧。

IReadOnlyCollection<T>是.net 4.5加進來的,可以認為是IList<T>的只讀版。

變量

 private const int _defaultCapacity = 4;
 
 private T[] _items;
 
 private int _size;
 
 private int _version;
 
 private Object _syncRoot;
 
 static readonly T[] _emptyArray = new T[0];

_defaultCapacity意思是new List<T>時默認大小是4。

_items就是存List<T>元素的數組了,List<T>也是基於數組實現的。

_size指元素個數。

_version看字面意思是版本,具體用處下面看,與遍歷集合時經常碰到的集合被修改異常有關。

_syncRoot上面有說到,內置的用於lock的對象,如果在多線程時只是操作這個集合就可以lock這個來保證線程安全,當然一般來說這個是內部用的,雖然對List<T>本身來說沒什麼用,這個不取的話是不會把對象new出來的,對於鎖我們更常用的是在外面new一個readonly的object。

emptyArray這是個靜態只讀的空數組,所有沒有元素的List<T>都是用這個,所以兩個List<int>的_items其實是一樣的,都是這個_emptyArray。

構造函數

有三個構造函數

 public List()
 {
     _items = _emptyArray;
 }

最常用的,_items直接指向靜態空數組。

 public List(int capacity)
 {
     if (capacity < 0) throw new ArgumentOutOfRangeException(nameof(capacity), capacity, SR.ArgumentOutOfRange_NeedNonNegNum);
     Contract.EndContractBlock();
 
     if (capacity == 0)
         _items = _emptyArray;
     else
         _items = new T[capacity];
 }

可以通過capacity指定大小

 public List(IEnumerable<T> collection)
 {
     if (collection == null)
         throw new ArgumentNullException(nameof(collection));
     Contract.EndContractBlock();
 
     ICollection<T> c = collection as ICollection<T>;
     if (c != null)
     {
         int count = c.Count;
         if (count == 0)
         {
             _items = _emptyArray;
         }
         else
         {
             _items = new T[count];
             c.CopyTo(_items, 0);
             _size = count;
         }
     }
     else
     {
         _size = 0;
         _items = _emptyArray;
         // This enumerable could be empty.  Let Add allocate a new array, if needed.
         // Note it will also go to _defaultCapacity first, not 1, then 2, etc.
 
         using (IEnumerator<T> en = collection.GetEnumerator())
         {
             while (en.MoveNext())
             {
                 Add(en.Current);
             }
         }
     }
 }

初始添加一個集合, 先看是否是ICollection,看上面知道這個接口有Copy的功能,copy到_items裡。如果不是ICollection,不過由於是IEnumerable,所以可以遍歷,一個一個加到_items裡。

屬性

Count 返回的是_size,這個是元素的實際個數,不是數組大小。

IsSynchronized是false,表示並非用SyncRoot 來實現同步。List<T>不是線程安全,需要我們自己用鎖搞定,

IsReadOnly也是false, 那為什麼要繼承IReadOnlyList<T>呢,是為了提供一個轉換成只讀List的機會,比如有的方法不希望傳進來的List可以修改,就可以把參數設成IReadOnlyList。

 Object System.Collections.ICollection.SyncRoot
 {
     get
     {
         if (_syncRoot == null)
         {
             System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null);
         }
         return _syncRoot;
     }
 }

SyncRoot通過原子操作得到一個對象,對於List<T>來說並沒有用,對於某些集合比較有用,比如SyncHashtable,就是通過syncRoot來實現線程安全。

比較重要的Capacity:

 public int Capacity
 {
     get
     {
         Contract.Ensures(Contract.Result<int>() >= 0);
         return _items.Length;
     }
     set
     {
         if (value < _size)
         {
             throw new ArgumentOutOfRangeException(nameof(value), value, SR.ArgumentOutOfRange_SmallCapacity);
         }
         Contract.EndContractBlock();
 
         if (value != _items.Length)
         {
             if (value > 0)
             {
                 var items = new T[value];
                 Array.Copy(_items, 0, items, 0, _size);
                 _items = items;
             }
             else
             {
                 _items = _emptyArray;
             }
         }
     }
 }

Capacity取的就是數組的長度,另外我們可以通過Capacity給List設置大小,即使這個List裡面已經有元素,會先new一個目標大小的數組,然後通過Array.Copy把現有元素復制到新數組裡。但一般情況下這些不用我們設置Capacity,添加新元素時發現長度不夠會自動擴大數組。Capacity是int型,說明最大是int.MaxValue,大約2G個,如果我們直接給List設置int.MaxValue就要看你的內存夠不夠2G*4也就是8G了,不夠的話會報OutofMemory Exception。其實個人覺得這裡Capacity用uint是不是更好。

用100M個,內存占用400M多

同樣100M個,由於是long,內存占了800M多

方法

看幾個重要的方法:

 public void Add(T item)
 {
     if (_size == _items.Length) EnsureCapacity(_size + 1);
     _items[_size++] = item;
     _version++;
 }

當前數組大小和元素個數相等時表明再Add的話大小不夠了,需要先通過EnsureCapacity擴容, _size+1指明了一個最小的擴容目標。

 private void EnsureCapacity(int min)
 {
     if (_items.Length < min)
     {
         int newCapacity = _items.Length == 0 ? _defaultCapacity : _items.Length * 2;
         // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
         // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
         //if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
         if (newCapacity < min) newCapacity = min;
         Capacity = newCapacity;
     }
 }

擴容方法,如果數組長度是0的話則用_defaultCapacity也就是4來做為數組長度,否則則以當前元素個數的2倍去擴大。如果新得到的長度比傳進來的min小的話則就用min,也就是選大的,這種情況在InsertRange時有可能發生,因為insert的list很可能比當前list的元素個數多。

Add函數裡還有個_version++,這個_version可以在很多方法裡看到,如remove, insert, sort等,但凡要修改集合都需要_version++。那這個_version有什麼用呢?

 public void ForEach(Action<T> action)
 {
     if (action == null)
     {
         throw new ArgumentNullException(nameof(action));
     }
 
     int version = _version;
 
     for (int i = 0; i < _size; i++)
     {
         if (version != _version)
         {
             break;
         }
         action(_items[i]);
     }
 
     if (version != _version)
         throw new InvalidOperationException(SR.InvalidOperation_EnumFailedVersion);
 }

在遍歷時如果發現_version變了立即退出並拋出遍歷過程集合被修改異常,比如在foreach裡remove或add元素就會導致這個異常。更常見的是出現在多線程時一個線程遍歷集合,另一個線程修改集合的時候,相信很多人吃過苦頭。

如果一個線程時想在遍歷時修改集合,比如刪除,可以用原始的for(int i=list.Count-1;i>=0;i--)方式。

另外用到version還有枚舉器Enumerator,MoveNext過程中同樣會檢測這個。

其他大部分方法都是通過Array的靜態函數實現,不多說,需要注意的是List<T>繼承自IList,所以可以轉成IList,轉之後泛型就沒了,如果是List<int>,轉成IList的話和IList<object>沒什麼兩樣,裝拆箱帶來的性能損失也值得注意。

總結

List<T>初始大小是4,自動擴容是以當前數組元素的兩倍或InsertRange目標list的元素個數來擴容(哪個大選哪個)。如果有比較確定的大小可以考慮提前設置,因為每次自動擴容需要重新分配數組和copy元素,性能損耗不小。

List<T>通過version來跟蹤集合是否發生改變,如果在foreach遍歷時發生改變則拋出異常。

List<T>並非線程安全,任何使用的時候都要考慮當前環境是否可能有多線程存在,是否需要用鎖來保證集合線程安全。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved