C＃SortedList如何在內部工作？

Question

我在想，SortedList是如何工作的。 我知道一個普通的List是基於一個動態數組，但SortedList基於什麼？

它使用什麼排序算法？

由於

Answer 1

從排序列表文件：「排序列表被實現爲鍵/值對的陣列，由密鑰進行排序。」
http://msdn.microsoft.com/en-us/library/e7a8xew6%28v=vs.110%29.aspx

如果使用默認的構造函數（無參數）：「初始化SortedList的類，它是空的新實例，具有默認的初始容量，並進行排序根據添加的每個密鑰實現的IComparable接口到SortedList對象「。
http://msdn.microsoft.com/en-us/library/cxb97few%28v=vs.110%29.aspx

或者您也可以通過自定義比較：

初始化SortedList的類，它是空的新實例，具有默認的初始容量，並根據指定的Icomparable接口分類。 http://msdn.microsoft.com/en-us/library/e7a8xew6%28v=vs.110%29.aspx

其它構造選項： http://msdn.microsoft.com/en-us/library/System.Collections.SortedList.SortedList%28v=vs.110%29.aspx

如何使用的IComparer接口：http://msdn.microsoft.com/en-us/library/system.collections.icomparer%28v=vs.110%29.aspx

Answer 2

如果你有興趣它是如何工作的內部，讓自己的任何像樣的反編譯器，如.NET反射器。

快速查看顯示，在內部，SortedList通過始終保持內部數組排序來維護它的排序狀態。使用添加方法添加項目時，它會使用關鍵字的二進制搜索來標識插入新項目的正確索引。

Answer 3

A SortedList是維護兩個數組以存儲列表的元素的對象。

一個陣列商店的Key和另一個陣列商店的關聯values。

SortedList中的元素根據創建SortedList時指定的特定IComparer實現或根據密鑰本身提供的IComparable實現進行排序。它們不能包含重複的鍵。

無論何時添加或刪除任何元素，都會相應地調整索引，結果與SortedList相關的操作更慢。

Answer 4

SortedList類的源代碼可以找到here。

根據該源，SortedList保持數據的鍵和值的兩個滑動數組：

private TKey[] keys; 
private TValue[] values; 

排序順序被保持鍵的陣列上。當添加新項目（鍵/值對）時，SortedList首先在已排序的鍵陣列中找到合適的索引（使用Array.BinarySearch），然後移動的部分內容鍵和值數組（使用Array.Copy）從此索引開始向上以創建插入關鍵字和值的差距。同樣，當一個項目被其關鍵字刪除時，SortedList將在關鍵字數組中搜索該項目的索引，然後從這個索引向下移動兩個數組的部分內容以縮小差距。

因此，有一點需要記住的是，當添加或刪除大SortedList時，可能會移動大量數據。積極的一面是，無論列表大小如何，通過索引檢索項目總是很快。