¿Por qué no hay una lista ordenada<T> en.NET?

sortedlist bcl

Question

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

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

Answer 1

Ahora hay :)

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 2

Aunque nadie puede realmente decirle por qué no hay una lista de SortedList<T> , es posible analizar por qué SortedList toma una clave y un valor. Un diccionario asigna claves a 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 poner la siguiente clave en orden. Si desea poder hacer eso, normalmente utiliza un árbol binario, que le proporciona un diccionario ordenado.

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

Answer 3

Creo que el camino a seguir con este problema es implementar un método de extensión que se agregue a la List<T> de manera ordenada (solo 2 líneas de código;), y luego la List<T> se puede usar como una lista ordenada (asumiendo que List.Add(...) usar 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);
    }

Answer 4

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

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

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

Sé que eso fue lo que hice en ambos casos: tenía una UniqueSet<T> y una clase AlwaysSortedList<T> , que solo incluía un Dictionary<T, byte> y una List<T> (y usaba BinarySearch e Insert ), respectivamente.

Answer 5

Es una lista con la clasificación realizada por la clave. Solo estoy especulando, pero al proporcionar la capacidad de especificar la clave por separado 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 6

Los comentarios de 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.