C＃：可以返回新添加对象的排序位置的通用排序容器？

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

这样的容器是否存在于.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 [...] 

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

Answer 1

如果你对List排序然后使用List.BinarySearch ，它将为你提供条目的索引（如果它存在），或者如果你插入然后排序它将被插入的位置的索引的按位补码。 从那以后，你应该能够轻松地构建你的方法。

示例代码与您的示例匹配，但不符合结果 – 如果您查看示例，则只有3个条目，因此“h”返回4或“g”返回3没有意义。我希望这是你的例子稍微偏离，而不是我误解了问题:)注意排序不是自动的 – 你必须在调用GetSortedIndex之前显式排序列表。

 using System; using System.Collections.Generic; static class Test { static int GetSortedIndex(this List list, T entry) { int index = list.BinarySearch(entry); return index >= 0 ? index : ~index; } static void Main() { List container = new List { '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')); } } 

Answer 2

您正在寻找的最接近的类是SortedList 。 该类将维护排序列表顺序。

但是，没有方法可以获得要添加新值的索引。 但是，您可以编写一个扩展方法来为您提供新索引

 public int GetSortedIndex(this SortedList list, TKey key) { var comp = list.Comparer; for ( var i = 0; i < list.Count; i++ ) { if ( comp.Compare(key, list.GetKey(i)) < 0 ) { return i; } } return list.Count; } 

Answer 3

听起来像一个有趣的测试，所以我试了一下。 可能不是最优雅，也不是最有效，但这应该工作：

  public class SortedContainer : IList where T : IComparable { private List internalList = new List(); public int IndexOf(T item) { return internalList.IndexOf(item); } public void Insert(int index, T item) { internalList.Insert(index, item); } public void RemoveAt(int index) { internalList.RemoveAt(index); } public T this[int index] { get { return internalList[index]; } set { internalList[index] = value; } } public void Add(T item) { internalList.Add(item); this.Sort(); } public void Clear() { internalList.Clear(); } public bool Contains(T item) { return internalList.Contains(item); } public void CopyTo(T[] array, int arrayIndex) { internalList.CopyTo(array, arrayIndex); } public int Count { get { return internalList.Count; } } public bool IsReadOnly { get { return false; } } public bool Remove(T item) { bool result = internalList.Remove(item); this.Sort(); return result; } public IEnumerator GetEnumerator() { return internalList.GetEnumerator(); } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return internalList.GetEnumerator(); } private void Sort() { internalList.Sort(); } private List GetCopy() { return internalList.ToList(); } public int GetSortedIndex(T item) { List copy = GetCopy(); copy.Add(item); copy.Sort(); return copy.IndexOf(item); } } 

基本上，实现IList，并保留一个internatl List。 每次调用Add方法时，都会在内部列表上调用sort。 然后，当您想要获取已排序的索引而不实际添加时，它会创建该列表的副本，将该项插入到副本中，然后对该副本进行排序。 然后它返回该项目的索引。 此时的内部列表尚未受到影响。 我测试了它，它的工作原理。

再次，可能不是最有效的。