Quick way to find the first unused key in a SortedDictionary?

Question

If I have SortedDictionary<int, object>, what is the fastest way to find the lowest key that is not currently in use? Obviously, we could iterate over the counter I from 0 → int.MaxValueand run away if !Keys.Contains(i), but it would be very slow if we had no luck, and the first spare key was at an early stage in the sequence of keys. Maybe even another .NET class does this for us already?

Answer 1

So, if I understand you correctly, the keys can be from 0to int.MaxValue. In this case, you need to find the first "hole" in the key sequence.

This should do the job efficiently:

public static int GetFirstUnusedKey<TValue>(SortedDictionary<int, TValue> dict)
{
    if (dict.Comparer != Comparer<int>.Default)
        throw new NotSupportedException("Unsupported comparer");

    using (var enumerator = dict.GetEnumerator())
    {
        if (!enumerator.MoveNext())
            return 0;

        var nextKeyInSequence = enumerator.Current.Key + 1;

        if (nextKeyInSequence < 1)
            throw new InvalidOperationException("The dictionary contains keys less than 0");

        if (nextKeyInSequence != 1)
            return 0;

        while (enumerator.MoveNext())
        {
            var key = enumerator.Current.Key;
            if (key > nextKeyInSequence)
                return nextKeyInSequence;

            ++nextKeyInSequence;
        }

        return nextKeyInSequence;
    }
}

I added a couple of checks to make sure the assumptions are valid.

Answer 2

Why not binary key search?

You can use the ElementAt () method to determine the key value in an index. If the key value is greater than the index, then search the left dictionary or select the right one and continue this way until you find the index in which you see the first difference between the index and the value in the index.

Answer 3

- , , :

var sd = new SortedDictionary<int, object>();

sd.Add(1, 1);
sd.Add(2, 1);
sd.Add(4, 1);
sd.Add(5, 1);

var e = Enumerable.Range(1, 5).Except(sd.Keys).First();

e = 3 , . , .

Answer 4

, 0.

Instead, use iterations used , starting from the lowest (they are sorted).

Either the first, or> 0, then 0 is your lowest unused.

or is there a gap between the two keys, then the bottom + 1 is what you were looking for.