Most Efficient way to find the index of an item in a SortedDictionary

Question

I am using a sorted dictionary to maintain a list of items, of which I regularly need to monitor the state of the top x items. Every time I update an item, I'd like a quick way of figuring out what index the item I'm referring to is using. I understand I can enumerate the entire list and count out my position, but I am looking for something with O(log n) time or better, after all the sorted dictionary is on a RedBlack tree. Each node should be able to keep track of its children, and this should be a quick calculation.

Answer 1

You can simply change your SortedDictionary<TKey, TValue> into a SortedList<TKey, TValue> and then use IndexOfKey(key):

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

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

IndexOfKey internally uses Array.BinarySearch<TKey>(), so it will be O(log n), which is faster than O(n) (which it would be if you searched from front to back by iterating through it).