在字典或相关集合中查找"下一个可用"键

Question

我想写一个linq扩展(或自定义词典,排序列表或任何最佳解决方案),这将允许我为一个集合添加一个值,其键是"下一个可用".

例如:

int CreatedKey = IncrementDictionary.AddNext(myCustomer);

如果当前存在的密钥如下:

1
2
8
4
3

然后它会将myCustomer添加到字典中,键为5,它将返回该键.

你怎么看？

Answer 1

public static int AddNext(this Dictionary<int, string> dict)
{
    int min = dict.Keys.Min();
    int max = dict.Keys.Max();

    return Enumerable.Range(min, max-min).Except(dict.Keys).First();   
}

用它作为

int result = new Dictionary<int, string>(){ {1, "a"}, {2, "a"}, 
                                            {8, "a"}, {4, "a"}, 
                                                      {3, "a"}}.AddNext();

这result是5.

Answer 2

您可以使用SortedList和扩展方法来添加到下一个自动检索的键。

假设数据结构是任何对象，带有数字键，

以下是 SortedList 的扩展方法

public static class SortedListExtensions
{
    ///Add item to sortedList (numeric key) to next available key item, and return key
    public static int AddNext<T>(this SortedList<int, T> sortedList, T item)
    {
        int key = 1; // Make it 0 to start from Zero based index
        int count = sortedList.Count;

        int counter=0;
        do
        {
            if (count == 0) break;
            int nextKeyInList = sortedList.Keys[counter++];

            if (key != nextKeyInList) break;

            key = nextKeyInList +1;

            if (count == 1 || counter == count  ) break;


            if (key != sortedList.Keys[counter])
                break;

        } while (true);

        sortedList.Add(key, item);
        return key;
    }

}

可以像下面这样使用

  SortedList<int, string> x = new SortedList<int, string>();

        x.Add(4, "BCD");
        x.Add(6, "BCD");

        x.AddNext("a");
        x.AddNext("b");
        x.AddNext("c");
        x.AddNext("d");
        x.AddNext("e");

        foreach (var item in x)
            Console.WriteLine(item.Key + " " + item.Value);

输出是

        1 a
        2 b
        3 c
        4 BCD
        5 d
        6 BCD
        7 e

您可以使用字典或任何其他数据结构。在这种情况下，将需要双循环。对于 SortedList，在搜索键时会节省一个循环。该循环由SortedList.Add使用 BinarySearch 算法的函数内部使用。

二分查找比循环所有元素更快（对于较大尺寸的数据）。