c# - 在 SortedDictionary 中找到第一个未使用的键的快速方法？

Question

如果我有一个 SortedDictionary<int, object> , 找到当前未使用的最低键的最快方法是什么？显然，我们可以从 0-> int.MaxValue 迭代一个计数器 i如果 !Keys.Contains(i) 则转义，但这会非常慢，除非我们很幸运并且第一个备用 key 恰好在 key 序列的早期。也许甚至不同的 .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;
    }
}

我添加了一些检查以确保先决条件有效。