.net - 为什么 SortedDictionary.GetEnumerator O(log n) 但 SortedSet.GetEnumerator O(1)？

Question

来自 SortedSet<T>.GetEnumerator 文档:

This method is an O(1) operation

来自 SortedDictionary<K, V>.GetEnumerator 文档:

This method is an O(log n) operation, where n is 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内部采用红黑树结构，保证平衡( Wikipedia ; Red-Black Trees, R. Sedgewick, Princeton University )，因此高度受限于 2 * log2(n + 1) .甚至一个 code comment在 SortedSet.cs 中指出了这一点，并相应地设置了枚举器堆栈的大小。while准备堆栈的循环是 O(log n) 在初始化和处理 ( MoveNext ) 枚举器中。
意见反馈 MSDN documentation引用提交的这个讨论。
更新:
到今天微软终于更新了文档。对于 4.0 版本，它仍然声明它是一个 O(1) 操作。虽然我对此表示怀疑，但我可以就此放弃。