A sorted dictionary where it is easy to move to the next key

Question

I have an ordered set of key-value pairs, for example with the following entries:

1 "one"
2 "two"
4 "four"
50 "fifty"

I would like to have a quick lookup (so given an int key, I want to find the value for that key), but also ideally have a quick way of finding the next key in the dictionary from a current key - so that given the key 2, find that the next key is 4, and then 50.

I know that a Dictionary does the first one quickly, and something like a linked-list for the second part too (but it's difficult to 'jump in' to start at a specific key).

I've had a look here, and it seems like some of this might be possible with a sorted dictionary? I wondered if there is a good data structure in C# to do both of these things (lookup by key and moving to the next key)?

I don't need the number of items to be very large (maybe in the thousands), but if possible, I would like to do a large number of lookups and move forward between keys quickly (without checking wheter 5, 6, 7... are present in the dictionary).

Answer 1

What you are looking for is OrderedDictionary in System.Collections.Specialized

In this collection you can get Key, and you can take item at next index next to already to found one, but out of the box implementation from Microsoft won't work, since its missing all required by you methods like TryGetValue or IndexOf.

Have a look at those pages:

MSDN

Custom ordered dictionary

Answer 2

You could put the info in your Value:

public class MyValue
{
  string Value;
  int NextId;
  int PreviousId;
}

public Dictionary<int, MyValue>();

It's then trivial to get your previous or next id. It's then trivial to get your next or previous value.

Of course, the insert logic requires you to update the previous & next each time you add something.

Answer 3

SortedList is suitable for this.

SortedList<int, string> sortedList = new SortedList<int,string>();

sortedList.Add(1, "one");
sortedList.Add(2, "two");
sortedList.Add(4, "four");
sortedList.Add(50, "fifty");

int currentIndex = sortedList.Keys.IndexOf(2);

Console.WriteLine(sortedList.Keys[currentIndex+1]);
Console.WriteLine(sortedList.Values[currentIndex+1]);