为什么只有一个SortedList<TKey, TValue>
看起来更像字典的,但SortedList<T>
实际上不是一个总是排序的列表?
根据有关 SortedList 的 MSDN 文档,它实际上在内部实现为KeyValuePair<TKey, TValue>
始终按键排序的动态大小的数组。同一个类作为任何类型的列表不会更有用T
吗?那不是更适合这个名字吗?
为什么只有一个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;
}
}
}
我认为解决这个问题的方法是实现一个以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
and Insert
,这意味着实现你自己的总是排序的列表是微不足道的。
并不是说这意味着一个SortedList<T>
类不属于框架——只是它可能不是一个非常高的优先级,因为任何需要它的开发人员都可以轻松地快速编写它。
我认为 .NET 3.5 之前的情况也是如此HashSet<T>
,它最初并不存在,因为您可以轻松地使用Dictionary<T, byte>
(例如)来模拟 .NET 3.5 之前的情况。
我知道这就是我在这两种情况下所做的:我有一个UniqueSet<T>
类和一个AlwaysSortedList<T>
类,它们分别包装了 aDictionary<T, byte>
和 a List<T>
(并使用了BinarySearch
and Insert
)。
它是一个列表,排序由键完成。我只是在推测,但是通过提供与元素分开指定键的能力,您的元素不必具有可比性——只需要键即可。我想在一般情况下,这可以节省大量正在开发的代码来实现 IComparable,因为密钥可能是已经可比较的类型。
RPM 评论非常有效。此外,通过 Linq 扩展,您可以使用 Sort 扩展方法按 T 的任何属性进行排序。我认为这可能是其背后的主要原因。