我需要按照对象内容（实际上是根据它们的一个属性，该属性不是键，并且可能在不同的对象之间重复）对一些对象进行排序。
.NET提供了两个类(SortedDictionary和SortedList)，并且两者都使用二叉树来实现。它们之间唯一的区别在于：
我可以使用List，然后使用其Sort()方法与自定义实现的IComparer来达到想要的效果，但它不是时间效率，因为每次插入新对象时我都需要对整个List进行排序，而好的SortedList只需将项目插入到正确的位置即可。
我需要一个带有RefreshPosition(int index)方法的SortedList类，以仅移动更改（或插入）的对象，而不是每次对象内部发生更改时重新排序整个列表。
我是否忽略了一些明显的东西？
class SortedList<T> : List<T>
{
public new void Add(T item)
{
Insert(~BinarySearch(item), item);
}
}
http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx
不幸的是，Add 方法无法被重写，所以我必须使用 new 方法，但当你需要使用 List<T> list = new SortedList<T>; 时，这并不是一种好的方式……因此，我重新构建了整个东西……
class SortedList<T> : IList<T>
{
private List<T> list = new List<T>();
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<T> GetEnumerator()
{
return list.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return list.GetEnumerator();
}
}
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;
}
public virtual void Add(T item)
{
int index = list_.BinarySearch(item);
list_.Insert(index >= 0 ? index : ~index, item);
} - Suncat2000Remove方法。它基本上是O(n)的。相反，你可以将比较器传递给list.BinarySearch方法。它会给你正确的索引以进行删除。在你的情况下：index = list.BinarySearch(item, Comparer<T>.Default)，然后list.RemoveAt(index)。这是O(n-index)。稍微提高了一点效率 :) Suncat是对的。我会在这里提供答案，介绍这两个更改。 - nawfalSortedList(或这些自制变体)几乎从来不是任何给定任务的适当数据结构。如果您需要在不断变异的情况下对数据进行排序，或者您想要一个普通的List，并且在完成变异后只需偶尔进行排序(如Jon的答案中所讨论的那样)，通常最好使用基于树的结构。 - ServyIList 替换为 ICollection 并删除一些方法。 - mpenclass RealSortedList<T> : List<T>
{
public IComparer<T> 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;
}
}
请不要忘记，在由数组支持的列表中插入一个项目可能是一项昂贵的操作 - 插入一堆项目然后排序可能会更快，除非你确实需要在每个操作之后进行排序。
或者，您可以始终包装一个列表并使您的添加操作找到正确的位置并将其插入那里。
class UpdateableSortedList<K,V> {
private SortedList<K,V> list = new SortedList<K,V>();
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<T> Values { get { return list.Values; } }
}
我猜就是这样吧。
SortedSet<T>，但它仍然不支持重复项。他们必须有某种意识形态问题，不支持带重复项的排序列表。 - Roman Starkov