為什麼 SortedDictionary<K, V>.GetEnumerator O(log n) 而 SortedSet<T>.GetEnumerator O(1)？

從SortedSet<T>.GetEnumerator文件中：

此方法是 O(1) 操作

從SortedDictionary<K, V>.GetEnumerator文件中：

此方法是 O(log n) 操作，其中 n 是計數。

這兩個陳述都可以是真的嗎，考慮到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，只是確保我理解正確。

我完全同意你的看法。

內部SortedSet使用保證平衡的紅黑樹結構（維基百科；紅黑樹，R. Sedgewick，普林斯頓大學）。
因此高度受限於2 * log2(n + 1)。甚至SortedSet.cs中的程式碼註釋也指出了這一點，並且相應地設置了列舉器堆棧的大小。

準備堆棧的while循環在初始化和處理 ( ) 列舉器時都是O(log n) 。MoveNext

送出的有關此討論的MSDN 文件的回饋。

更新：

到今天，微軟終於更新了文件。對於 4.0 版本，它仍然聲明它是 O(1) 操作。儘管我對此表示懷疑，但我可以把它留在那裡。

引用自：https://stackoverflow.com/questions/24781153