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).

Answer 2

A tree structure could be constructed to access items by index or report the index of an existing item in lgN time, requiring very slight extra time for inserts and deletes. One way to do this would be to keep track of how many items are in the left and right branches of each node (on an insert or delete, change the node count of parent nodes when changing the count of the children). If a tree-based structure does not offer such a facility, though, I know of no easy way to retrofit it.