1

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

Community
  • 1
  • 1
Kevin C
  • 324
  • 1
  • 14
  • 2
    You may want to look at http://stackoverflow.com/questions/4720674/how-do-i-get-previous-key-from-sorteddictionary – Florian Jan 04 '17 at 16:31
  • dictionary already has collection of keys. so you just iterate over the keys. `foreach (var key in dict.Keys)` – M.kazem Akhgary Jan 04 '17 at 16:32
  • I would suggest if a singular data type like SortedDictionary or SortedList doesn't help, it may be optimal to store the data in two separate structures, and interchangably use either depending on the optimal strategy. This would increase the cost of keeping both up to date, though. @M.kazemAkhgary I believe he means optimizing for entering a function with just `int 2` rather than doing full collection loops. – Katana314 Jan 04 '17 at 16:32
  • you may want to try `.Skip(1)` to get the next item in the `IEnumerable`. – CodeMonkey1313 Jan 04 '17 at 16:36
  • @Katana314 if `1,2,4,50` are the only items inside dictionary then you just iterate over them. there is no `3,5,6,...`. but if user wants to specify orders himself he can either have separate ordered collection of keys. and just iterate over that. – M.kazem Akhgary Jan 04 '17 at 16:50
  • @M.kazemAkhgary If the numbers go up to 3,729, 4,012, 5,623, and higher, then he's going to be doing a lot of iterations over possibly-absent numbers to find the point of insertion he's interested in (eg, 3500 - and the three collected numbers just above it). Dictionaries are not really optimized for that sort of sequential iteration, so this would have a very high complexity. – Katana314 Jan 04 '17 at 16:53

3 Answers3

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

Community
  • 1
  • 1
Tomasz Juszczak
  • 2,276
  • 15
  • 25
0

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.

Carra
  • 17,808
  • 7
  • 62
  • 75
  • it would be better to have `int?` for next and previous ids. because then you know where it ends. other wise `0` can be mistaken by another id. – M.kazem Akhgary Jan 04 '17 at 16:59
-1

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]);
user2560178
  • 31
  • 5