SortedList<TKey, TValue>，而没有一个实际上只是始终排序的列表SortedList<T>？SortedList在MSDN文档中的说明，它实际上是作为一个总是通过键排序的KeyValuePair<TKey, TValue>的动态大小数组来实现的。同样的类作为任何类型T的列表会更有用吗？这不也更符合名称吗？虽然没有人能真正告诉你为什么没有SortedList<T>，但是可以讨论一下为什么SortedList需要一个键和一个值。字典将键映射到值上。通常的做法是使用二叉树、哈希表和列表（数组），但哈希表最常用，因为它们对于大多数操作来说都是O(1)。
它不支持的主要操作是以O(1)的时间获取下一个键。如果您想要能够这样做，通常会使用二叉树，从而得到排序的字典。
如果您决定将映射实现为列表，则应通过关键字保持元素排序，以便查找的复杂度为O(lg n)，从而得到另一个排序的字典--以排序列表的形式呈现。当然，SortedDictionary这个名字已经被使用了，但是SortedList还没有。我可能会称其为SortedListDictionary或SortedDictionaryList，但我没有机会给它命名。
public class SortedList<T> : ICollection<T>
{
private List<T> m_innerList;
private Comparer<T> m_comparer;
public SortedList() : this(Comparer<T>.Default)
{
}
public SortedList(Comparer<T> comparer)
{
m_innerList = new List<T>();
m_comparer = comparer;
}
public void Add(T item)
{
int insertIndex = FindIndexForSortedInsert(m_innerList, m_comparer, item);
m_innerList.Insert(insertIndex, item);
}
public bool Contains(T item)
{
return IndexOf(item) != -1;
}
/// <summary>
/// Searches for the specified object and returns the zero-based index of the first occurrence within the entire SortedList<T>
/// </summary>
public int IndexOf(T item)
{
int insertIndex = FindIndexForSortedInsert(m_innerList, m_comparer, item);
if (insertIndex == m_innerList.Count)
{
return -1;
}
if (m_comparer.Compare(item, m_innerList[insertIndex]) == 0)
{
int index = insertIndex;
while (index > 0 && m_comparer.Compare(item, m_innerList[index - 1]) == 0)
{
index--;
}
return index;
}
return -1;
}
public bool Remove(T item)
{
int index = IndexOf(item);
if (index >= 0)
{
m_innerList.RemoveAt(index);
return true;
}
return false;
}
public void RemoveAt(int index)
{
m_innerList.RemoveAt(index);
}
public void CopyTo(T[] array)
{
m_innerList.CopyTo(array);
}
public void CopyTo(T[] array, int arrayIndex)
{
m_innerList.CopyTo(array, arrayIndex);
}
public void Clear()
{
m_innerList.Clear();
}
public T this[int index]
{
get
{
return m_innerList[index];
}
}
public IEnumerator<T> GetEnumerator()
{
return m_innerList.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return m_innerList.GetEnumerator();
}
public int Count
{
get
{
return m_innerList.Count;
}
}
public bool IsReadOnly
{
get
{
return false;
}
}
public static int FindIndexForSortedInsert(List<T> list, Comparer<T> comparer, T item)
{
if (list.Count == 0)
{
return 0;
}
int lowerIndex = 0;
int upperIndex = list.Count - 1;
int comparisonResult;
while (lowerIndex < upperIndex)
{
int middleIndex = (lowerIndex + upperIndex) / 2;
T middle = list[middleIndex];
comparisonResult = comparer.Compare(middle, item);
if (comparisonResult == 0)
{
return middleIndex;
}
else if (comparisonResult > 0) // middle > item
{
upperIndex = middleIndex - 1;
}
else // middle < item
{
lowerIndex = middleIndex + 1;
}
}
// At this point any entry following 'middle' is greater than 'item',
// and any entry preceding 'middle' is lesser than 'item'.
// So we either put 'item' before or after 'middle'.
comparisonResult = comparer.Compare(list[lowerIndex], item);
if (comparisonResult < 0) // middle < item
{
return lowerIndex + 1;
}
else
{
return lowerIndex;
}
}
}
SortedList<T>无法实现IList<T>，因为在排序集合的上下文中，某些操作是没有意义的，比如索引设置器、InsertAt和RemoveAt。 - ironstone13RemoveAt(int index) 没有问题，列表仍将保持排序。 - AnloRemoveAt的看法完全正确。 - ironstone13IList<T>，并在调用InsertAt()时抛出异常。虽然不是最理想的解决方案，但这就是数组实现IList<T>的方式，我认为相比于根本不实现接口来说，这种做法更好。 - BlueRaja - Danny Pflughoeft我认为解决这个问题的方法是实现一个扩展方法，以有序的方式向 List<T> 添加元素（仅需2行代码），然后可以将 List<T> 用作排序列表（假设您避免使用 List.Add(...)）：
public static void AddSorted<T>(this List<T> list, T value)
{
int x = list.BinarySearch(value);
list.Insert((x >= 0) ? x : ~x, value);
}
List<T>已经有了BinarySearch和Insert，这意味着实现自己的始终排序列表是微不足道的。这并不意味着SortedList<T>类不属于框架 - 只是它可能不是非常重要，因为任何需要它的开发人员都可以很快地编写它。HashSet<T>也是如此，它最初不存在，因为在.NET 3.5之前，您可以轻松使用Dictionary<T，byte>（例如）来模拟一个。UniqueSet<T>类和一个AlwaysSortedList<T>类，它们只是分别包装了一个Dictionary<T，byte>和一个List<T>（并且使用了BinarySearch和Insert）。SortedList<T> 已经优先级太低了，那么显然提供了严格子集功能的 SortedList<TKey, TValue> 将会更加低优先级。 - TimwiSortedList<TKey, TValue>和SortedDictionary<TKey, TValue>之间的所有比较（以及SortedList<TKey, TValue>实现IDictionary<TKey, TValue>的事实）都可以看出来。我不知道为什么 他们会优先考虑这一点而不是一个“真正”的排序列表；事实仍然存在，自己实现一个排序列表几乎不费吹灰之力。 - Dan Tao这是一个按键排序的列表。我只是推测，通过提供单独指定键而不是元素的能力，您的元素不必是可比较的--只有键需要是可比较的。我想在一般情况下，这样做可以节省大量代码来实现IComparable，因为键可能是已经可比较的类型。
SortedList<TK,TV>也显然不能提供所需的功能。 - TimwiSortedList<T>，你最终会需要为一个类实现IComparable接口，而这个IComparable接口只是重新实现（或委托）值类型的可比性。鉴于这种情况，使排序键明确化可以简化类的用户的实现，但会增加一些存储开销——假设键来自类属性。显然，您可以保持已排序键的列表和相关值的列表以相同的顺序。我认为这就是SortedList的实现方式。不是很高效。 - tvanfossonRPM的评论非常有道理。此外，使用Linq扩展，您可以使用Sort扩展方法按T的任何属性进行排序。我认为这可能是其主要原因。
Sort扩展方法。如果您想要使用的是List<T>.Sort（它既不是扩展方法也不是LINQ的一部分），那么在每次调用Add和Insert之后使用它会比必要的慢得多。如果你想用OrderBy，那更加慢了。 - TimwiSorted..类的重点在于，当您添加/删除元素时，它会维护排序。这与每次需要进行排序时调用List.Sort非常不同；如果这是唯一的解决方案，则在某些用例中，程序员必须每次添加新元素时都调用Sort：非常缓慢。一个好的Sorted..类将比在每次插入时调用Sort（通过适当的内部结构）表现得更好。 - ToolmakerSteve