¿Por qué no hay SortedList <T> en .NET?

Question

¿Por qué hay solo un SortedList<TKey, TValue> que se parece más a un diccionario, pero no SortedList<T> que en realidad es solo una lista que siempre está ordenada?

De acuerdo con the MSDN documentation on SortedList, en realidad se implementa internamente como una matriz de tamaño dinámico de KeyValuePair<TKey, TValue> que siempre está ordenada por la clave. ¿No sería la misma clase más útil como una lista de cualquier tipo T? ¿No encajaría eso mejor el nombre también?

Answer 1

Aunque nadie puede decirle realmente por qué no hay SortedList<T>, es posible analizar por qué SortedList toma una clave y un valor. Un diccionario mapea las claves de los valores. Las formas típicas de hacerlo son con un árbol binario, una tabla hash y una lista (matriz), aunque las tablas hash son más comunes porque son O (1) para la mayoría de las operaciones.

La operación principal que no admite en O (1) es obtener la siguiente clave en orden. Si desea poder hacer eso, normalmente usa un árbol binario, que le proporciona un diccionario ordenado.

Si decide implementar el mapa como una lista, mantendrá los elementos ordenados por clave para que la búsqueda sea O (lg n), proporcionándole otro diccionario ordenado, en forma de una lista ordenada. Por supuesto, el nombre SortedDictionary ya estaba tomado, pero SortedList no. Podría haberlo llamado SortedListDictionary o SortedDictionaryList, pero no pude nombrarlo.

Answer 2

Es una lista con la clasificación realizada por la clave. Solo estoy especulando, pero al proporcionar la capacidad de especificar la clave separada del elemento, su elemento no tiene que ser comparable, solo la clave debe ser. Me imagino que, en el caso general, esto ahorra una buena cantidad de código que se está desarrollando para implementar IComparable, ya que la clave es probablemente un tipo que ya es comparable.

Answer 3

Los comentarios RPM son bastante válidos. Además, con las extensiones Linq, puede ordenar por cualquier propiedad de T utilizando el método de extensión Ordenar. Creo que ese podría ser el principal razonamiento detrás de esto.

Answer 4

Creo que la razón probablemente sea que List<T> ya tiene BinarySearch y Insert, lo que significa que implementar su propia lista siempre ordenada es trivial.

No es que esto signifique que una clase SortedList<T> no pertenece al marco, solo que probablemente no era una prioridad muy alta, ya que cualquier desarrollador que la necesitara podría escribirla rápidamente.

Creo que lo mismo ocurrió con HashSet<T>, que originalmente no existía porque podría usar fácilmente un Dictionary<T, byte> (por ejemplo) para simular uno antes de .NET 3.5.

sé que es lo que hice en los dos casos: que tenía una clase UniqueSet<T> y una clase AlwaysSortedList<T>, que acaba de terminar un Dictionary<T, byte> y una List<T> (y utiliza BinarySearch y Insert), respectivamente.

Answer 5

Hay ahora :)

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; 
     } 
    } 
} 

Answer 6

creo que el camino a seguir con este problema es poner en práctica un método de extensión que se suma a List<T> de una manera ordenada (sólo 2 líneas de código;), y luego List<T> se puede utilizar como una lista ordenada (suponiendo que evite el uso de 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); 
    }