Быстрый способ найти первый неиспользованный ключ в SortedDictionary?

Question

Если у меня есть SortedDictionary<int, object>Какой самый быстрый способ найти самый низкий ключ, который в настоящее время не используется? Очевидно, мы могли бы перебрать счетчик i из 0->int.MaxValue и сбежать, если !Keys.Contains(i), но это было бы очень медленно, если бы нам не повезло, и первый запасной ключ оказался в начале последовательности ключей. Может быть, даже другой класс.NET уже делает это для нас?

Answer 1

Так что, если я вас правильно понимаю, ключи могут быть где угодно 0 в int.MaxValue, В этом случае вы должны найти первую "дыру" в последовательности клавиш.

Это должно сделать работу эффективно:

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;
    }
}

Я добавил пару проверок, чтобы убедиться, что предварительные условия верны.

Answer 2

Почему не бинарный поиск по ключам?

Вы можете использовать метод ElementAt() для определения значения ключа в индексе. Если значение ключа больше индекса, выполните поиск в левом под-словаре или выберите правое и продолжайте в том же духе, пока не найдете индекс, по которому вы наблюдаете первое различие между индексом и значением в индексе.

Answer 3

Не ищите неиспользованный ключ, начинающийся с 0.

Вместо этого итерируйте используемые ключи, начиная с самого низкого (они отсортированы).

Либо первый>0, затем 0 - ваш самый низкий неиспользованный.

или между двумя клавишами есть пробел, тогда +1 - это то, что вы искали.

Answer 4

Я не претендую на какую-либо награду за производительность для этого подхода, но я думаю, что он каким-то образом способствует достижению вашей цели:

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();

е = 3 в этом случае, как и предполагалось. Я ожидаю, что есть лучшие решения, хотя.