SortedList 和 SortedDictionary 有什么区别？

Question

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

Answer 1

是的 - 它们的性能特征显着不同。打电话给他们可能会更好 SortedList 和 SortedTree 因为这更密切地反映了实施情况。

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

这 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>.

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

Answer 2

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

来自一个 表现 看法：

+------------------+---------+----------+--------+----------+----------+---------+
| 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).

来自一个 执行 看法：

+------------+---------------+----------+------------+------------+------------------+
| 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              |
+------------+---------------+----------+------------+------------+------------------+

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

您可以阅读更多内容 这里, 这里, 这里, 这里 和 这里.

Answer 3

我裂了开反射来看看本作似乎有一些关于SortedList混乱。事实上，它是不是一个二分搜索树，的它是键 - 值对的排序（通过键）阵列。还有，其在与该键 - 值对同步排序并用于二进制搜索一个TKey[] keys变量。

下面是一些源（靶向.NET 4.5）来备份我的权利要求中。

<强>私有成员信息

// 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的）

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）：无效

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）：无效

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++;
}

Answer 4

查看 SortedList 的 MSDN 页面:

来自备注部分：

这 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>)>) 对未排序的数据具有更快的插入和删除操作， O(log n) 相对于 O(n) 为了 SortedList<(Of <(TKey, TValue>)>).

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

Answer 5

这是表演如何相互比较视觉表示。

Answer 6

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

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

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

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

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

希望这可以帮助！！

Answer 7

索引访问（这里提到）是实际的差别。 如果您需要访问的继任者或前任，你需要排序列表。 SortedDictionary不能做到这一点，所以你是你如何使用排序（第一/的foreach）相当有限。