Почему существует только SortedList<TKey, TValue>, который больше похож на словарь, но не SortedList<T>, который на самом деле является только списком, который всегда сортируется?
В соответствии с документацией MSDN на SortedList, она фактически внутренне реализована как массив с динамическим размером 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> уже есть BinarySearch и Insert, что означает, что реализация вашего собственного всегда отсортированного списка тривиальна.
Не то, чтобы это означало, что класс SortedList<T> не входит в структуру - просто, что он, вероятно, не был очень высоким приоритетом, так как он легко мог быть быстро написан любым разработчиком, который в нем нуждался.
Я думаю, что то же самое верно для HashSet<T>, который изначально не существовал, потому что вы могли легко использовать Dictionary<T, byte> (например) для имитации одного перед .NET 3.5.
Я знаю, что то, что я делал в обоих случаях: у меня был класс UniqueSet<T> и класс AlwaysSortedList<T>, который просто обернул Dictionary<T, byte> и List<T> (и использовал BinarySearch и Insert), соответственно.
Я думаю, что способ решить эту проблему - реализовать метод расширения, который добавляет к 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);
}
Это список с сортировкой, выполняемой ключом. Я просто размышляю, но, предоставляя возможность указывать ключ отдельно от элемента, ваш элемент не должен быть сопоставимым - только ключ должен быть. Я бы предположил, что в общем случае это экономит достаточное количество кода для разработки IComparable, поскольку ключ, скорее всего, является уже сопоставимым типом.
Комментарии RPM вполне допустимы. Кроме того, с расширениями Linq вы можете сортировать по любому свойству T с помощью метода расширения Sort. Я думаю, что это может быть основной причиной этого.