Add to SortedSet and its complexity

问题:

MSDN states the following SortedSet(T).Add Method :

If Count is less than the capacity of the internal array, this method is an O(1) operation.

Could someone please explain "how so"? I mean when adding new value we need to find a correct place to add a value (comparing it with another values) and internal implementation looks like a "Red-Black tree" with O (log N) insertion complexity.

回答1:

The comment is simply wrong. Yes, it is a red-black tree, O(log(n)) for inserts. Taking a look with Reflector bears this out, the private AddIfNotPresent() method contains a while() loop to find the insertion point, using normal red-black node traversal.

This doc bug has already been submitted by you-know-who.