SortedList和SortedDictionary之间的区别是什么?

SortedList<TKey,TValue>和SortedDictionary<TKey,TValue>之间有什么实际的区别吗?在某些情况下，你会特别使用其中一种而不是另一种吗?

113383 次浏览
小开
最佳答案

是的，它们的表现特征有很大不同。可能更好的方法是称它们为SortedList和SortedTree，因为这样能更准确地反映实现。

查看它们各自的MSDN文档(SortedList， SortedDictionary)，了解不同情况下不同操作的性能细节。下面是一个很好的总结(来自SortedDictionary文档):

SortedDictionary<TKey, TValue>泛型 类的二叉搜索树 O(log n)的检索，其中n是 字典中的元素个数。 在这一点上，它与 SortedList<TKey, TValue>通用 类。这两个类有相似之处 对象模型，都是O(log n) 检索。这两个类 不同的是内存的使用和速度 插入和删除:

  • SortedList<TKey, TValue>使用较少 内存比SortedDictionary< TValue> < /代码> . < / p > < /李> <李> < p > SortedDictionary<TKey, TValue> 更快的插入和移除 对无序数据的运算，O(log n) 而不是O(n 李SortedList<TKey, TValue> . < / p > < / >

  • 如果列表是一次性填充的 from sorted data， SortedList< 比 李SortedDictionary<TKey, TValue> . < / p > < / >

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

小开

查看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>)>)快。

小开

我打开Reflector来看看这个，因为似乎有一些关于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。男星(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

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

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

如果有用的话，这里有一个表格视图。

从性能的角度来看:

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


* Insertion is O(log n) for data that are already in sort order, so that each
element is added to the end of the list. If a resize is required, that element
takes O(n) time, but inserting n elements is still amortized O(n log n).
list.
** Available through enumeration, e.g. Enumerable.ElementAt.

从实现的角度来看:

+------------+---------------+----------+------------+------------+------------------+
| 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更适合。关于何时使用哪个，请参阅这个问题。

你可以阅读更多在这里， 在这里， 在这里， 在这里和在这里。

小开

这是性能之间相互比较的可视化表示。

.

小开

索引访问(这里提到)是实际的区别。 如果需要访问后继对象或前任对象，则需要SortedList。SortedDictionary不能这样做，所以你在如何使用排序(first / foreach)方面受到相当的限制

小开

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

分类词典应该在-时使用

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

另一方面，排序的列表应该在-时使用

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

希望这能有所帮助!!


提交答案