Perché non esiste una lista ordinata <T> in .NET?

Question

Perché c'è solo un SortedList<TKey, TValue> che sembra più un dizionario, ma non lo SortedList<T> che in realtà è solo un elenco che viene sempre ordinato?

Secondo the MSDN documentation on SortedList, in realtà è implementato internamente come una matrice di dimensioni dinamiche di KeyValuePair<TKey, TValue> che viene sempre ordinata dalla chiave. La stessa classe non sarebbe più utile come un elenco di qualsiasi tipo T? Non sarebbe meglio anche il nome?

Answer 1

Anche se nessuno può davvero dirti perché non c'è lo SortedList<T>, è possibile discutere sul motivo per cui lo SortedList prende una chiave e un valore. Un dizionario mappa le chiavi ai valori. I metodi tipici per farlo sono un albero binario, una tabella hash e un elenco (array), sebbene le tabelle hash siano più comuni perché sono O (1) per la maggior parte delle operazioni.

L'operazione principale che non supporta in O (1) sta ottenendo la prossima chiave in ordine. Se vuoi essere in grado di farlo, di solito usi un albero binario, dandoti un dizionario ordinato.

Se si decide di implementare la mappa come elenco, si manterranno ordinati gli elementi per chiave in modo che la ricerca sia O (lg n), fornendo un altro dizionario ordinato, sotto forma di elenco ordinato. Ovviamente il nome SortedDictionary era già in uso, ma non lo era lo SortedList. Avrei potuto chiamarlo SortedListDictionary o SortedDictionaryList, ma non sono riuscito a chiamarlo.

Answer 2

È un elenco con l'ordinamento eseguito dal tasto. Sto solo ipotizzando ma, fornendo la possibilità di specificare la chiave separata dall'elemento, il tuo elemento non deve essere comparabile, solo la chiave deve essere. Immagino che nel caso generale ciò consenta di risparmiare una discreta quantità di codice sviluppato per implementare IComparable poiché la chiave è probabilmente un tipo già comparabile.

Answer 3

I commenti RPM sono abbastanza validi. Inoltre, con le estensioni Linq, puoi eseguire l'ordinamento in base a qualsiasi proprietà di T utilizzando il metodo di estensione Ordina. Penso che potrebbe essere il ragionamento principale dietro di esso.

Answer 4

Penso che il motivo è probabilmente proprio questo List<T> ha già BinarySearch e Insert, il che significa attuare il proprio elenco sempre-ordinato è banale.

Non che ciò significhi che una classe SortedList<T> non appartiene al framework - solo che probabilmente non era una priorità molto alta poiché poteva essere facilmente scritta rapidamente da qualsiasi sviluppatore che ne aveva bisogno.

Penso che lo stesso fosse vero per HashSet<T>, che in origine non esisteva perché si poteva facilmente usare un Dictionary<T, byte> (per esempio) per simularne uno prima di .NET 3.5.

so che è quello che ho fatto in entrambi i casi: ho avuto una classe UniqueSet<T> e una classe AlwaysSortedList<T>, che ha appena avvolto un Dictionary<T, byte> e un List<T> (e utilizzato BinarySearch e Insert), rispettivamente.

Answer 5

V'è ora :)

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

Penso che il modo di andare con questo problema è quello di implementare un metodo di estensione che aggiunge al List<T> in modo ordinato (solo 2 linee di codice;), e poi List<T> può essere utilizzato come un elenco ordinato (supponendo che si evita di usare 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); 
    }