查找SortedDictionary中项目索引的最有效方法

Question

我使用排序字典来维护项目列表,我经常需要监视前x项的状态.每次我更新一个项目时,我都想快速找出我所指的项目使用的索引.我知道我可以列举整个列表并计算我的位置,但是我正在寻找O(log n)时间或更好的东西,所有排序的字典都在RedBlack树上.每个节点都应该能够跟踪其子节点,这应该是一个快速计算.

Answer 1

你可以简单地将你SortedDictionary<TKey, TValue>改成a SortedList<TKey, TValue>然后使用IndexOfKey(key):

var s = new SortedList<string, string>
    { { "a", "Ay" }, { "b", "Bee" }, { "c", "Cee" } };

// Outputs 1
Console.WriteLine(s.IndexOfKey("b"));

IndexOfKey在内部使用Array.BinarySearch<TKey>(),所以它将是O(log n),它比O(n)更快(如果你通过迭代搜索从前到后搜索它).