.NET中是否有SortedList 类？

我需要根据它们的内容对某些对象进行排序（实际上根据它们的一个属性，这不是关键，可能在不同对象之间重复）。

.NET提供了两个类（ SortedDictionary和SortedList ），并且都使用二叉树实现。 它们之间的唯一区别是

• SortedList比SortedDictionary使用更少的内存。
• 对于未排序的数据，SortedDictionary具有更快的插入和删除操作，O（log n）而不是SortedList的O（n）。
• 如果列表是从排序数据中一次性填充的，则SortedList比SortedDictionary快。

我可以使用List实现我想要的东西，然后将它的Sort（）方法与IComparer的自定义实现一起使用，但它不会节省时间，因为每次我想插入一个新对象时我会对整个List进行排序，而一个好的SortedList只会将项目插入正确的位置。

我需要的是一个带有RefreshPosition（int索引）的SortedList类，它只移动已更改（或插入）的对象，而不是每次内部对象更改时都使用整个列表。

我错过了一些明显的东西吗

Answer 1

也许我很慢，但这不是最容易实现的吗？

 class SortedList : List { public new void Add(T item) { Insert(~BinarySearch(item), item); } } 

http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx

---

不幸的是， Add不能重写，所以当我有List list = new SortedList;时，我不得不List list = new SortedList; 我实际上需要做的……所以我继续重建整个事情……

 class SortedList : IList { private List list = new List(); public int IndexOf(T item) { var index = list.BinarySearch(item); return index < 0 ? -1 : index; } public void Insert(int index, T item) { throw new NotImplementedException("Cannot insert at index; must preserve order."); } public void RemoveAt(int index) { list.RemoveAt(index); } public T this[int index] { get { return list[index]; } set { list.RemoveAt(index); this.Add(value); } } public void Add(T item) { list.Insert(~list.BinarySearch(item), item); } public void Clear() { list.Clear(); } public bool Contains(T item) { return list.BinarySearch(item) >= 0; } public void CopyTo(T[] array, int arrayIndex) { list.CopyTo(array, arrayIndex); } public int Count { get { return list.Count; } } public bool IsReadOnly { get { return false; } } public bool Remove(T item) { var index = list.BinarySearch(item); if (index < 0) return false; list.RemoveAt(index); return true; } public IEnumerator GetEnumerator() { return list.GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() { return list.GetEnumerator(); } } 

---

或者类似这样的东西是更合适的Removefunction……

  public bool Remove(T item) { var index = list.BinarySearch(item); if (index < 0) return false; while (((IComparable)item).CompareTo((IComparable)list[index]) == 0) { if (item == list[index]) { list.RemoveAt(index); return true; } index++; } return false; } 

假设项目可以比较相等但不相等......

Answer 2

我不久前问了一个类似的问题，那里有一些很好的答案 。 这里有很多collections品。

Answer 3

我最终决定写它：

 class RealSortedList : List { public IComparer comparer; public int SortItem(int index) { T item = this[index]; this.RemoveAt(index); int goodposition=FindLocation(this[index], 0, this.Count); this.Insert(goodposition, item); return goodposition; } public int FindLocation(T item, int begin, int end) { if (begin==end) return begin; int middle = begin + end / 2; int comparisonvalue = comparer.Compare(item, this[middle]); if (comparisonvalue < 0) return FindLocation(item,begin, middle); else if (comparisonvalue > 0) return FindLocation(item,middle, end); else return middle; } } 

Answer 4

不要忘记将项目插入由数组支持的列表中可能是一项昂贵的操作 – 插入一堆项目然后排序可能会更快，除非您确实需要在每次操作后进行排序。

或者，您可以始终包装列表并使添加操作找到正确的位置并将其插入其中。

Answer 5

我过去通过编写一个在IList上进行二进制搜索的扩展方法和另一个执行插入的方法解决了这个问题。 您可以在CLR源中查找正确的实现，因为有一个仅适用于数组的内置版本，然后只需将其调整为IList上的扩展。

其中一个“应该在BCL已经”的事情。

Answer 6

我需要的是一个带有RefreshPosition（int索引）的SortedList类，它只移动已更改（或插入）的对象，而不是每次内部对象更改时都使用整个列表。

当此类更新使索引无效时，为什么要使用索引进行更新？ 真的，我认为通过对象引用更新会更方便。 您可以使用SortedList执行此操作 – 只需记住您的Key类型与从对象中提取可比较数据的函数的返回类型相同。

 class UpdateableSortedList { private SortedList list = new SortedList(); public delegate K ExtractKeyFunc(V v); private ExtractKeyFunc func; public UpdateableSortedList(ExtractKeyFunc f) { func = f; } public void Add(V v) { list[func(v)] = v; } public void Update(V v) { int i = list.IndexOfValue(v); if (i >= 0) { list.RemoveAt(i); } list[func(v)] = v; } public IEnumerable Values { get { return list.Values; } } } 

我想是这样的。