在 .NET 4.0+ 中，一个类SortedSet<T>有一个方法叫做GetViewBetween(l, r)，它返回树部分的接口视图，其中包含指定的两个值之间的所有值。鉴于SortedSet<T>被实现为红黑树，我自然希望它能够运行在O(log N)时间。 C++中类似的方法是std::set::lower_bound/upper_bound，在 Java 中是TreeSet.headSet/tailSet，并且它们是对数的。

然而，事实并非如此。以下代码运行时间为 32 秒，而等效代码O(log N)的版本GetViewBetween将使此代码在 1-2 秒内运行。

var s = new SortedSet<int>();
int n = 100000;
var rand = new Random(1000000007);
int sum = 0;
for (int i = 0; i < n; ++i) {
    s.Add(rand.Next());
    if (rand.Next() % 2 == 0) {
        int l = rand.Next(int.MaxValue / 2 - 10);
        int r = l + rand.Next(int.MaxValue / 2 - 10);
        var t = s.GetViewBetween(l, r);
        sum += t.Min;
    }
}
Console.WriteLine(sum);

我使用反编译System.dlldotPeek这就是我得到的：

public TreeSubSet(SortedSet<T> Underlying, T Min, T Max, bool lowerBoundActive, bool upperBoundActive)
    : base(Underlying.Comparer)
{
    this.underlying = Underlying;
    this.min = Min;
    this.max = Max;
    this.lBoundActive = lowerBoundActive;
    this.uBoundActive = upperBoundActive;
    this.root = this.underlying.FindRange(this.min, this.max, this.lBoundActive, this.uBoundActive);
    this.count = 0;
    this.version = -1;
    this.VersionCheckImpl();
}

internal SortedSet<T>.Node FindRange(T from, T to, bool lowerBoundActive, bool upperBoundActive)
{
  SortedSet<T>.Node node = this.root;
  while (node != null)
  {
    if (lowerBoundActive && this.comparer.Compare(from, node.Item) > 0)
    {
      node = node.Right;
    }
    else
    {
      if (!upperBoundActive || this.comparer.Compare(to, node.Item) >= 0)
        return node;
      node = node.Left;
    }
  }
  return (SortedSet<T>.Node) null;
}

private void VersionCheckImpl()
{
    if (this.version == this.underlying.version)
      return;
    this.root = this.underlying.FindRange(this.min, this.max, this.lBoundActive, this.uBoundActive);
    this.version = this.underlying.version;
    this.count = 0;
    base.InOrderTreeWalk((TreeWalkPredicate<T>) (n =>
    {
      SortedSet<T>.TreeSubSet temp_31 = this;
      int temp_34 = temp_31.count + 1;
      temp_31.count = temp_34;
      return true;
    }));
}

So, FindRange显然是O(log N)，但之后我们调用VersionCheckImpl...它对找到的子树进行线性时间遍历，只是为了重新计算其节点！

1. 为什么你需要一直进行这种遍历？
2. 为什么 .NET 不包含O(log N)基于键分割树的方法，如 C++ 或 Java？这是really在很多情况下都有帮助。

有关version field

UPDATE1:

在我的记忆中，BCL 中的很多（也许是全部？）集合都有该字段version.

首先，关于foreach:

根据这个msdn链接

foreach 语句为数组或对象集合中的每个元素重复一组嵌入语句。 foreach 语句用于迭代集合以获取所需的信息，但不应用于更改集合的内容，以避免不可预测的副作用。

在许多其他收藏中，version受保护，数据在期间不被修改foreach

例如，HashTable's MoveNext():

public virtual bool MoveNext()
{
    if (this.version != this.hashtable.version)
    {
        throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumFailedVersion"));
    }
    //..........
}

但在SortedSet<T>'s MoveNext() method:

public bool MoveNext()
{
    this.tree.VersionCheck();
    if (this.version != this.tree.version)
    {
        ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
    }       
    //....
}

UPDATE2：

但 O(N) 循环可能不仅仅适用于version也为了Count财产。

因为GetViewBetween 的 MSDN said:

此方法返回介于 lowerValue 和 upperValue 之间的元素范围的视图，如比较器...所定义。您可以在视图和基础 SortedSet(Of T) 中进行更改.

因此对于每次更新都应该同步count字段（键和值已经相同）。为了确保Count是正确的

有两项政策可以实现这一目标：

1. 微软的
2. Mono's

首先，MS 在他们的代码中牺牲了GetViewBetween()的表现并赢得Count财产的表现。

VersionCheckImpl()是同步的一种方法Count财产。

第二，莫诺。在mono的代码中，GetViewBetween()速度更快，但在他们的GetCount()method:

internal override int GetCount ()
{
    int count = 0;
    using (var e = set.tree.GetSuffixEnumerator (lower)) {
        while (e.MoveNext () && set.helper.Compare (upper, e.Current) >= 0)
            ++count;
    }
    return count;
}

它始终是一个 O(N) 操作！