我需要一个通用容器来保持其元素排序,并且可以询问它将在何处(在哪个位置)插入新元素,而不实际插入它。

.NET 库中是否存在这样的容器?
最好的说明是一个例子(容器按 ASCII 值对字符进行排序,假设 unicode 不存在):

sortedContainer.Add('d');
sortedContainer.Add('b');
sortedContainer.Add('g');

//container contains elements ordered like 'b' 'd' 'g'
//index  -------------------------------->  0   1   2

sortedContainer.GetSortedIndex('a'); //returns 0
sortedContainer.GetSortedIndex('b'); //returns 0

sortedContainer.GetSortedIndex('c'); //returns 1
sortedContainer.GetSortedIndex('d'); //returns 1

sortedContainer.GetSortedIndex('e'); //returns 2
sortedContainer.GetSortedIndex('f'); //returns 2
sortedContainer.GetSortedIndex('g'); //returns 2

sortedContainer.GetSortedIndex('h'); //returns 3
[...]

位置的搜索应该利用元素已排序的事实。

最佳答案

如果您对 List<T> 进行排序,然后使用 List<T>.BinarySearch ,它将为您提供条目的索引(如果它存在),或者如果您插入然后排序,它将为插入位置的索引的按位补码。由此,您应该能够轻松构建您的方法。

与您的示例匹配的示例代码,但不是结果 - 如果您查看您的示例,您只有 3 个条目,因此“h”返回 4 或“g”返回 3 是没有意义的。我希望那是您的示例,它略有偏差,而不是我误解了问题:) 请注意,排序不是自动的 - 您必须在调用 GetSortedIndex 之前对列表进行显式排序。

using System;
using System.Collections.Generic;

static class Test
{
    static int GetSortedIndex<T>(this List<T> list, T entry)
    {
        int index = list.BinarySearch(entry);
        return index >= 0 ? index : ~index;
    }

    static void Main()
    {
        List<char> container = new List<char> { 'b', 'd', 'g' };
        Console.WriteLine(container.GetSortedIndex('a'));
        Console.WriteLine(container.GetSortedIndex('b'));
        Console.WriteLine(container.GetSortedIndex('c'));
        Console.WriteLine(container.GetSortedIndex('d'));
        Console.WriteLine(container.GetSortedIndex('e'));
        Console.WriteLine(container.GetSortedIndex('f'));
        Console.WriteLine(container.GetSortedIndex('g'));
        Console.WriteLine(container.GetSortedIndex('h'));
    }
}

关于C#:可以返回新添加对象的排序位置的通用排序容器?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/450820/

10-14 16:36
查看更多