Perché non esiste un ordinamento per IList <T>?!?! (modificato)

Question

Sono rimasto piuttosto sorpreso quando ho scoperto che non esiste un modo diretto per ordinare o eseguire una ricerca binaria su un IList < T>. Proprio come ci sono metodi statici per ordinare ed eseguire una ricerca binaria su una matrice, penso che sarebbe terribilmente utile avere metodi statici simili che richiedono un IList < T>.

Attualmente:

class Array 
{ 
    static Sort<T>(T[] array); 
    static int BinarySearch<T>(T[] array, T item); 
} 

Vorrei che si aggiungere:

class List 
{ 
    static Sort<T>(IList<T> list); 
    static int BinarySearch<T>(IList<T> list, T item); 
} 

Diedi un'occhiata al .NET Framework 4.0 Beta SDK e ci ancora non sembra essere una soluzione per questo problema.

So che potrei aggirare questo creando un metodo di estensione che controlla se si tratta di un elenco < T> e quindi ordinare/cercare utilizzando l'istanza Elenco < T>; tuttavia, se non è un'istanza di un elenco < T>, quindi devo eseguire una copia (che puzza per elenchi molto grandi). So che potrei fare tutto questo, ma perché? C'è qualche ragione per cui hanno intenzionalmente omesso questa funzione?

Per provare a ottenere questo nel .NET Framework 4.0, ho creato un suggerimento tramite il programma Connect di Microsoft. Se sei frustrato come me riguardo a questo problema, votalo e forse verrà aggiunto.

https://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=474201

Answer 1

LINQ ha un metodo OrderBy che funziona su tutti IEnumerable <T>, incluso IList <T>. Puoi realizzare la stessa cosa usando OrderBy.

// Order a list of addresses: 
IList<string> list = ... 
var orderedList = list.OrderBy(input => input); 

Answer 2

Tu devi ArrayList.Adapter che consente l'utilizzo di ArrayList 's ordinamento routine, ma causerebbe un enorme impatto sulle prestazioni per le liste generiche di tipi di valore unboxed, più sia chiamata e l'invio di interfaccia in testa virtuale.

Per entrambi i tipi di riferimento e il valore, l'invio interfaccia potrebbe essere costoso, cioè una chiamata a ICollection<T>.CopyTo un array T[] seguito da liste separato potrebbe essere l'opzione scopo veloce generale, compreso un'estensione personalizzata per direttamente ordinamento sull'oggetto IList<T>.

List<T> ha un metodo Sort perché può molto operare efficientemente sulla matrice sottostante di tipo T[]. Semplicemente non c'è modo di farlo per un arbitrario IList<T>.

Answer 3

Penso che ci sia un buon caso per non includere un metodo di ordinamento per IList<T>. Innanzitutto, creerebbe una complessità aggiuntiva per coloro che desiderano implementare un IList e in secondo luogo renderebbe più difficile per l'interfaccia IList essere conforme allo Interface Segregation Principle.

In generale quello che faccio se ho bisogno di eseguire una sorta su un IList<T> è creare un nuovo List<T> e passare nel IList<T> come parametro

così per esempio:

 public IList<Address> SortAddresses(IList<Address> addresses) 
     { 
      var sortedAddresses = new List<Address>(addresses); 
      sortedAddresses.Sort(); 
      return sortedAddresses; 
     } 

Answer 4

io non sono un esperto in C#, ma pochissime implementazioni di List supportano l'ordinamento, la ricerca binaria o persino il recupero indicizzato. Gli elenchi si basano generalmente su linked lists che di solito non offrono un modo O(1) di recuperare un elemento dal suo indice.Se si desidera individuare rapidamente un elemento, utilizzare qualcosa che mantenga gli elementi ordinati in ordine come tree o un array come suggerito da altri.

Io trovo interessante il fatto che IList include un indexed retrieval method. Potresti prendere in considerazione l'utilizzo di SortedList invece di List poiché sembra che dovrebbe supportare le ricerche per indice o chiave in tempo O(1). In generale, se hai bisogno di qualcosa che supporti la ricerca veloce, cerca una struttura dati che mantenga i suoi elementi in ordine invece di ordinarli esplicitamente. Se non altro, C# ha già la litania delle strutture dati.

Answer 5

La buona notizia è che si può scrivere tali metodi abbastanza facilmente; e grazie a C# 3.0 metodi di estensione, si può fare questo lavoro sull'interfaccia:

public static class ListExt 
{ 
    public static void AddRange<T>(this IList<T> list, IEnumerable<T> items) { 
     foreach(T item in items) list.Add(item); 
    } 
    public static void Sort<T>(this IList<T> list) { 
     Sort<T>(list,Comparer<T>.Default); // ordinal sort by default 
    } 
    public static void Sort<T>(this IList<T> list, IComparer<T> comparer) 
    { // very poor implementation! 
     List<T> concreteList = new List<T>(list); 
     concreteList.Sort(comparer); // cheat! 
     list.Clear(); 
     list.AddRange(concreteList); 
    } 
    public static int BinarySearch<T>(this IList<T> list, T item) { 
     return BinarySearch<T>(list, item, Comparer<T>.Default); 
    } 
    public static int BinarySearch<T>(this IList<T> list, T item, 
     IComparer<T> comparer) 
    {...} // TODO 
} 

Ora non rimane che il codice TODO stesso (e probaby riscrivere Sort ;-P); ma dopo che:

IList<T> list = ... 
list.Sort(); 
T huntFor = ... 
int i = list.BinarySearch(huntFor); 

È importante sottolineare che, IList<T> ha un indicizzatore di lettura/scrittura, quindi è certamente possibile fare entrambe le cose del genere e binario di ricerca senza l'hack di cui sopra.