为什么SortedDictionary <K,V> .GetEnumerator O(log n)但SortedSet <T> .GetEnumerator O(1)？

Question

从SortedSet<T>.GetEnumerator文档:

该方法是O(1)操作

从SortedDictionary<K, V>.GetEnumerator文档:

此方法是O(log n)操作,其中n是count.

这两个陈述都可以是真的,考虑到SortedDictionary<K, V>内部实现为SortedSet<KeyValuePair<K, V>？我检查了类的GetEnumerator代码SortedDictionary- 它直接使用了SortedSet枚举器.我注意到了SortedSet枚举器的实现,在我看来它确实有O(log n)特性(这里是代码):

public SortedSet<T>.Enumerator GetEnumerator()
{
  return new SortedSet<T>.Enumerator(this);
}

//which calls this constructor:
internal Enumerator(SortedSet<T> set)
{
  this.tree = set;
  this.tree.VersionCheck();
  this.version = this.tree.version;
  this.stack = new Stack<SortedSet<T>.Node>(2 * SortedSet<T>.log2(set.Count + 1));
  this.current = (SortedSet<T>.Node) null;
  this.reverse = false;
  this.siInfo = (SerializationInfo) null;
  this.Intialize();
}

private void Intialize()
{
  this.current = (SortedSet<T>.Node) null;
  SortedSet<T>.Node node1 = this.tree.root;
  while (node1 != null)
  {
    SortedSet<T>.Node node2 = this.reverse ? node1.Right : node1.Left;
    SortedSet<T>.Node node3 = this.reverse ? node1.Left : node1.Right;
    if (this.tree.IsWithinRange(node1.Item))
    {
      this.stack.Push(node1);
      node1 = node2;
    }
    else
      node1 = node2 == null || !this.tree.IsWithinRange(node2.Item) ? node3 : node2;
  }
}

这是不是意味着文档是错误的并且SortedSet<T>.GetEnumerator是O(log n)？没有太多关于GetEnumerator电话的表现,只是确保我理解正确.

Answer 1

我完全同意你的看法。

内部使用保证平衡的红黑树SortedSet结构（维基百科；红黑树，R. Sedgewick，普林斯顿大学）。因此高度受到 的限制。甚至SortedSet.cs中的代码注释也指出了这一点，并且枚举器堆栈的大小也是相应设置的。
2 * log2(n + 1)

在初始化和继续 ( ) 枚举器时while，准备堆栈的循环都是O (log n) 。MoveNext

对引用此讨论的MSDN 文档的反馈已提交。

更新：

到今天微软终于更新了文档。对于 4.0 版本，它仍然声明它是一个 O(1) 操作。虽然我对此表示怀疑，但我可以就此打住。