Next key in C# Dictionary

Question

How to get an Enumerator to an item in a -Sorted- dictionary using key?

Note:GetEnumerator() gets an Enumerator to first element..

But I need to get an Enumerator to the element with a given key in order to gain access to next elements using MoveNext() for example...

Edit: Or a way to access next elements...

Edit: I prefer a const time method...

Thanks

Retrieval

Answer 1

var enumerator = dictionary.Keys.SkipWhile(k => k != myKey)

Where myKey is the key you're looking for. And you can use the OrderBy extension method if you want to have the keys sorted.

Edit: You can't do it in constant with Dictionary/SortedDictionary. Why not implement your own binary search tree (like SortedDictionary is) and you will have O(log n) time lookup and O(1) time .next()?

Caryncaryo

Answer 2

Maybe this is useful to somebody:

public Dictionary<string, int> myDictionary = new Dictionary<string, int>();
public string myCurrentKey = "some key 5";
for (int i = 1; i <= 10; i++) {
    myDictionary.Add(string.Format("some key {0}", i), i);
}

private void MoveIndex(int dir) { // param "dir" can be 1 or -1 to move index forward or backward
    List<string> keys = new List<string>(myDictionary.Keys);
    int newIndex = keys.IndexOf(myCurrentKey) - dir;
    if (newIndex < 0) {
        newIndex = myDictionary.Count - 1;
    } else if (newIndex > myDictionary.Count - 1) {
        newIndex = 0;
    }

    myCurrentKey = keys[newIndex];
}

Debug.Log(string.Format("Current value: {0}", myDictionary[myCurrentKey])); // prints 5
MoveIndex(1);
Debug.Log(string.Format("Current value: {0}", myDictionary[myCurrentKey])); // prints 6
MoveIndex(-1);
MoveIndex(-1);
Debug.Log(string.Format("Current value: {0}", myDictionary[myCurrentKey])); // prints 4

Kosaka

Answer 3

You can't do that with Dictionary. You can accomplish that having possibility of accessing by index, so you can use SortedList instead of Dictionary. Also you can have a look at SkipWhile.

Although you can have some workaround like this :

Dictionary<int, int> dictionary = new Dictionary<int, int>();
foreach (KeyValuePair<int, int> pair in dictionary)
{ 
   // you can check the key you need and assume that the next one will be what you need.
}

But of course this is not the best idea.

Allheal

Answer 4

If you have Framework >=3.5 installed use SkipWhile Janus Tondering and LukeH suggested. For lower framework versions you have to do it for yourself(f.e. fill a second dictionary with the keyvaluepairs from your key to the end).

Backcourt

Answer 5

var query = yourDictionary.SkipWhile(kvp => kvp.Key != keyToFind);
foreach (var result in query)
{
    // ...
}

Attachment

Answer 6

The easiest option is to use a SortedList and then add an extension method to it that returns an IEnumerable whose elements are greater than or equal to the given key. The complexity of the GetElementsGreaterThanOrEqual method below is O(log(n)) to get the first element and then each iteration after that is O(1).

public static class SortedListExtension
{
    public static IEnumerable<KeyValuePair<TKey, TValue>> GetElementsGreaterThanOrEqual<TKey, TValue>(this SortedList<TKey, TValue> instance, TKey target) where TKey : IComparable<TKey>
    {
        int index = instance.BinarySearch(target);
        if (index < 0)
        {
            index = ~index;
        }
        for (int i = index; i < instance.Count; i++)
        {
            yield return new KeyValuePair<TKey, TValue>(instance.Keys[i], instance.Values[i]);
        }
    }

    public static int BinarySearch<TKey, TValue>(this SortedList<TKey, TValue> instance, TKey target) where TKey : IComparable<TKey>
    {
        int lo = 0;
        int hi = instance.Count - 1;
        while (lo <= hi)
        {
            int index = lo + ((hi - lo) >> 1);
            int compare = instance.Keys[index].CompareTo(target);
            if (compare == 0)
            {
                return index;
            }
            else
            {
                if (compare < 0)
                {
                    lo = index + 1;
                }
                else
                {
                    hi = index - 1;
                }
            }
        }
        return ~lo;
    }
}

Inosculate

How would this method be used/called? – Imparadise