为什么SortedList <TKey,TValue>不使用指针值？

Question

所以我正在通过执行SortedList<TKey, TValue>和实现Add(Insert下面显示的调用)真的让我感到惊讶.

该Add方法进行明显的二元搜索以确定KVP应该进入的索引,但Insert 似乎可以显着改进(尽管在更大的范围内):

private void Insert(int index, TKey key, TValue value)
{
  if (this._size == this.keys.Length)
    this.EnsureCapacity(this._size + 1);
  if (index < this._size)
  {
    Array.Copy((Array) this.keys, index, (Array) this.keys, index + 1, this._size - index);
    Array.Copy((Array) this.values, index, (Array) this.values, index + 1, this._size - index);
  }
  this.keys[index] = key;
  this.values[index] = value;
  ++this._size;
  ++this.version;
}

如果我正确地阅读这个,并且我保留在任何时候都是错的权利,这是一个O(2n)操作.

在我看来,值应该用指针实现.像那种一LinkedList相对于从键的值,而不是挂在它不支持随机访问.更重要的是,关键只是与其价值挂钩.该GET操作也不会有任何慢,亦不会删除,因为我们有指针,但添加操作将是O(n)现在来代替.

有人可以说明为什么这个决定可能会走向这个方向吗？

Answer 1

这不应该让你感到惊讶,它在SortdList的MSDN文章中有详细记载:

对于未排序的数据,SortedDictionary具有更快的插入和删除操作,O(logn)而不是SortedList的O(n).

SortedDictionary使用红黑树(即"指针"),SortedList是一个数组.您可以根据对集合的处理方式在两者之间进行选择.两者都是用于查找的O(logn),但是如果你经常迭代这个集合,那么你可以在SortedList上取得很大进展.它更有效地使用cpu缓存.在现代机器上有很大的不同.

另请注意,向集合添加项目的效率在很大程度上取决于项目的排序方式.SortedDictionary 真的很喜欢随机数据,给它更好的几率,不必重新平衡树.对它进行排序会给出最坏情况的O(n)行为.SortedList 非常喜欢排序的项目,使得添加O(1).