C# SortedList 和 SortedDictionary 有什么区别？

What's the difference between SortedList and SortedDictionary?

提问by Shaul Behr

Is there any real practical difference between a SortedList<TKey,TValue>and a SortedDictionary<TKey,TValue>? Are there any circumstances where you would specifically use one and not the other?

aSortedList<TKey,TValue>和 a之间有什么真正的实际区别SortedDictionary<TKey,TValue>吗？在任何情况下，您会专门使用一种而不是另一种吗？

采纳答案by Jon Skeet

Yes - their performance characteristics differ significantly. It would probably be better to call them SortedListand SortedTreeas that reflects the implementation more closely.

是的 - 它们的性能特征显着不同。调用它们可能会更好SortedList，SortedTree因为这更紧密地反映了实现。

Look at the MSDN docs for each of them (SortedList, SortedDictionary) for details of the performance for different operations in different situtations. Here's a nice summary (from the SortedDictionarydocs):

查看每个 ( SortedList, SortedDictionary)的 MSDN 文档，了解不同情况下不同操作的性能详细信息。这是一个很好的总结（来自SortedDictionary文档）：

The SortedDictionary<TKey, TValue>generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this, it is similar to the SortedList<TKey, TValue>generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal:

• SortedList<TKey, TValue>uses less memory than SortedDictionary<TKey, TValue>.

• SortedDictionary<TKey, TValue>has faster insertion and removal operations for unsorted data, O(log n) as opposed to O(n) for SortedList<TKey, TValue>.

• If the list is populated all at once from sorted data, SortedList<TKey, TValue>is faster than SortedDictionary<TKey, TValue>.

的SortedDictionary<TKey, TValue>通用类是O（log n）的检索，其中n是字典中的元件的数目的二进制搜索树。在这方面，它类似于 SortedList<TKey, TValue>泛型类。这两个类具有相似的对象模型，并且都有 O(log n) 检索。这两个类的不同之处在于内存使用以及插入和删除的速度：

• SortedList<TKey, TValue>使用的内存少于SortedDictionary<TKey, TValue>.

• SortedDictionary<TKey, TValue>对未排序的数据有更快的插入和删除操作，O(log n) 而不是 O(n) SortedList<TKey, TValue>。

• 如果列表从排序的数据中一次性全部填充，SortedList<TKey, TValue>则比 SortedDictionary<TKey, TValue>.

(SortedListactually maintains a sorted array, rather than using a tree. It still uses binary search to find elements.)

（SortedList实际上维护了一个排序数组，而不是使用树。它仍然使用二分查找来查找元素。）

回答by Stephan

Check out the MSDN page for SortedList:

查看SortedList的MSDN 页面：

From Remarks section:

来自备注部分：

The SortedList<(Of <(TKey, TValue>)>)generic class is a binary search tree with O(log n)retrieval, where nis the number of elements in the dictionary. In this, it is similar to the SortedDictionary<(Of <(TKey, TValue>)>)generic class. The two classes have similar object models, and both have O(log n)retrieval. Where the two classes differ is in memory use and speed of insertion and removal:

• SortedList<(Of <(TKey, TValue>)>)uses less memory than SortedDictionary<(Of <(TKey, TValue>)>).

• SortedDictionary<(Of <(TKey, TValue>)>)has faster insertion and removal operations for unsorted data, O(log n)as opposed to O(n)for SortedList<(Of <(TKey, TValue>)>).

• If the list is populated all at once from sorted data, SortedList<(Of <(TKey, TValue>)>)is faster than SortedDictionary<(Of <(TKey, TValue>)>).

该SortedList<(Of <(TKey, TValue>)>)泛型类是用二叉搜索树O(log n)的检索，其中n在字典中元素的个数。在这方面，它类似于SortedDictionary<(Of <(TKey, TValue>)>)泛型类。这两个类具有相似的对象模型，并且都具有O(log n)检索功能。这两个类的不同之处在于内存使用以及插入和删除的速度：

• SortedList<(Of <(TKey, TValue>)>)使用的内存少于SortedDictionary<(Of <(TKey, TValue>)>).

• SortedDictionary<(Of <(TKey, TValue>)>)与 forO(log n)相比，O(n)对未排序数据具有更快的插入和删除操作SortedList<(Of <(TKey, TValue>)>)。

• 如果列表从排序的数据中一次性全部填充，SortedList<(Of <(TKey, TValue>)>)则比SortedDictionary<(Of <(TKey, TValue>)>).

回答by Daniel Imms

I cracked open Reflector to have a look at this as there seems to be a bit of confusion about SortedList. It is in fact not a binary search tree, it is a sorted (by key) array of key-value pairs. There is also a TKey[] keysvariable which is sorted in sync with the key-value pairs and used to binary search.

我打开 Reflector 来看看这个，因为似乎对SortedList. 它实际上不是二叉搜索树，它是键值对的排序（按键）数组。还有一个TKey[] keys与键值对同步排序并用于二分查找的变量。

Here is some source (targeting .NET 4.5) to backup my claims.

这是一些源（针对 .NET 4.5）来备份我的声明。

Private members

私人会员

// Fields
private const int _defaultCapacity = 4;
private int _size;
[NonSerialized]
private object _syncRoot;
private IComparer<TKey> comparer;
private static TKey[] emptyKeys;
private static TValue[] emptyValues;
private KeyList<TKey, TValue> keyList;
private TKey[] keys;
private const int MaxArrayLength = 0x7fefffff;
private ValueList<TKey, TValue> valueList;
private TValue[] values;
private int version;

SortedList.ctor(IDictionary, IComparer)

SortedList.ctor(IDictionary, IComparer)

public SortedList(IDictionary<TKey, TValue> dictionary, IComparer<TKey> comparer) : this((dictionary != null) ? dictionary.Count : 0, comparer)
{
    if (dictionary == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary);
    }
    dictionary.Keys.CopyTo(this.keys, 0);
    dictionary.Values.CopyTo(this.values, 0);
    Array.Sort<TKey, TValue>(this.keys, this.values, comparer);
    this._size = dictionary.Count;
}

SortedList.Add(TKey, TValue) : void

SortedList.Add(TKey, TValue) : 无效

public void Add(TKey key, TValue value)
{
    if (key == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }
    int num = Array.BinarySearch<TKey>(this.keys, 0, this._size, key, this.comparer);
    if (num >= 0)
    {
        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
    }
    this.Insert(~num, key, value);
}

SortedList.RemoveAt(int) : void

SortedList.RemoveAt(int) : 无效

public void RemoveAt(int index)
{
    if ((index < 0) || (index >= this._size))
    {
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
    }
    this._size--;
    if (index < this._size)
    {
        Array.Copy(this.keys, index + 1, this.keys, index, this._size - index);
        Array.Copy(this.values, index + 1, this.values, index, this._size - index);
    }
    this.keys[this._size] = default(TKey);
    this.values[this._size] = default(TValue);
    this.version++;
}

回答by nawfal

Here is a tabular view if it helps...

如果有帮助，这是一个表格视图...

From a performanceperspective:

从性能上看：

+------------------+---------+----------+--------+----------+----------+---------+
| Collection       | Indexed | Keyed    | Value  | Addition |  Removal | Memory  |
|                  | lookup  | lookup   | lookup |          |          |         |
+------------------+---------+----------+--------+----------+----------+---------+
| SortedList       | O(1)    | O(log n) | O(n)   | O(n)*    | O(n)     | Lesser  |
| SortedDictionary | n/a     | O(log n) | O(n)   | O(log n) | O(log n) | Greater |
+------------------+---------+----------+--------+----------+----------+---------+

* Insertion is O(1) for data that are already in sort order, so that each 
  element is added to the end of the list (assuming no resize is required).

From an implementationperspective:

从实现的角度来看：

+------------+---------------+----------+------------+------------+------------------+
| Underlying | Lookup        | Ordering | Contiguous | Data       | Exposes Key &    |
| structure  | strategy      |          | storage    | access     | Value collection |
+------------+---------------+----------+------------+------------+------------------+
| 2 arrays   | Binary search | Sorted   | Yes        | Key, Index | Yes              |
| BST        | Binary search | Sorted   | No         | Key        | Yes              |
+------------+---------------+----------+------------+------------+------------------+

To roughlyparaphrase, if you require raw performance SortedDictionarycould be a better choice. If you require lesser memory overhead and indexed retrieval SortedListfits better. See this question for more on when to use which.

要大致复述，如果您需要原始性能SortedDictionary可能是一个更好的选择。如果您需要较少的内存开销并且索引检索SortedList更适合。有关何时使用 which 的更多信息，请参阅此问题。

You can read more here, here, here, hereand here.

您可以在此处、此处、此处、此处和此处阅读更多信息。

回答by Lev

This is visual representation of how performances compare to each other.

这是性能如何相互比较的直观表示。

回答by Guy

Index access (mentioned here) is the practical difference. If you need to access the successor or predecessor, you need SortedList. SortedDictionary cannot do that so you are fairly limited with how you can use the sorting (first / foreach).

索引访问（这里提到）是实际的区别。如果需要访问后继者或前驱者，则需要 SortedList。SortedDictionary 不能这样做，因此您对如何使用排序（first / foreach）相当有限。

回答by Prakash Tripathi

Enough is said already on the topic, however to keep it simple, here's my take.

关于这个话题已经说得够多了，但为了简单起见，这是我的看法。

Sorted dictionaryshould be used when-

排序字典应在以下情况下使用-

• More inserts and delete operations are required.
• Data in un-ordered.
• Key access is enough and index access is not required.
• Memory is not a bottleneck.

• 需要更多的插入和删除操作。
• 数据无序。
• 密钥访问就足够了，不需要索引访问。
• 内存不是瓶颈。

On the other side, Sorted Listshould be used when-

另一方面，排序列表应在以下情况下使用-

• More lookups and less inserts and delete operations are required.
• Data is already sorted (if not all, most).
• Index access is required.
• Memory is an overhead.

• 需要更多的查找和更少的插入和删除操作。
• 数据已经排序（如果不是全部，大多数）。
• 需要索引访问。
• 内存是一种开销。

Hope this helps!!

希望这可以帮助！！