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

Question

If I have a SortedDictionary<int, object>, what is the fastest way to find the lowest key that is not currently being used? Obviously, we could iterate a counter i from 0->int.MaxValue and escape if !Keys.Contains(i), but that would be very slow unless we were lucky and the first spare key happened to be early on in the sequence of keys. Maybe even a different .NET class does this for us already?

Answer 1

So, If I understand you correctly, the keys can be anywhere from 0 to int.MaxValue. In that case, you have to find the first "hole" in the sequence of keys.

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 ensure the preconditions are valid.