Pourquoi n'y a-t-il pas de tri pour IList <T>?!?! (édité)

Question

J'ai été assez surpris quand j'ai découvert qu'il n'y a pas de moyen direct pour trier ou effectuer une recherche binaire sur un IList < T>. Tout comme il existe des méthodes statiques pour trier et effectuer une recherche binaire sur un tableau, je pense qu'il serait terriblement utile d'avoir des méthodes statiques similaires qui prennent un IList < T>.

Actuellement:

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

Je souhaite qu'ils ajouteraient:

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

Je jetai au .NET Framework 4.0 SDK Beta et il encore ne semble pas être une solution ce problème.

Je sais que je pourrais contourner cela en créant une méthode d'extension qui vérifie si c'est une liste < T> puis trier/rechercher en utilisant l'instance T> List <; cependant, s'il ne s'agit pas d'une instance d'une liste, alors je dois effectuer une copie (qui pue pour les listes très volumineuses). Je sais que je pourrais faire tout ça, mais pourquoi? Y at-il une raison pour laquelle ils ont intentionnellement omis cette fonctionnalité? Pour essayer de l'obtenir dans le Framework .NET 4.0, j'ai créé une suggestion via le programme Connect de Microsoft. Si vous êtes frustré comme moi à ce sujet, votez-y et peut-être que cela sera ajouté.

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

Answer 1

LINQ a une méthode OrderBy qui fonctionne sur tous les IEnumerable <T>, y compris IList <T>. Vous pouvez accomplir la même chose en utilisant OrderBy.

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

Answer 2

Vous ne disposez ArrayList.Adapter qui permet l'utilisation de routines « s tri ArrayList, mais cela causerait un énorme impact sur les performances des listes génériques de types de valeur unboxed, plus à la fois appel virtuel et une interface expédition aérienne.

Pour les deux types de référence et la valeur, l'envoi d'interface pourrait être coûteux, ce qui signifie un appel à ICollection<T>.CopyTo un tableau T[] suivi trier séparée pourrait être l'option but le plus rapide en général, y compris une extension personnalisée pour sorte directement sur l'objet IList<T>.

List<T> a une méthode Sort car il peut très fonctionner efficacement sur le tableau sous-jacent de type T[]. Il n'y a simplement aucun moyen de le faire pour un IList<T> arbitraire.

Answer 3

Je pense qu'il y a un très bon cas pour ne pas inclure une méthode de tri pour IList<T>. Tout d'abord, cela créerait une complexité supplémentaire pour ceux qui veulent implémenter un IList et, en second lieu, cela rendrait plus difficile la conformité de l'interface IList avec le Interface Segregation Principle.

En général ce que je fais si je dois faire une sorte sur un IList<T> est de créer une nouvelle List<T> et passer dans le IList<T> comme paramètre

donc par exemple:

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

Answer 4

Je ne suis pas un expert C#, mais très peu d'implémentations de listes supportent le tri, la recherche binaire, ou même la recherche indexée. Les listes sont généralement basées sur linked lists qui n'offrent généralement pas de moyen de récupérer un article par son index O(1).Si vous souhaitez localiser un élément rapidement, utilisez un élément qui conserve les éléments dans un ordre tel qu'un tree ou un tableau comme suggéré par d'autres.

Je trouve le fait que IList comprend un indexed retrieval method intéressant. Vous pouvez envisager d'utiliser SortedList au lieu de List car il semble qu'il devrait prendre en charge les recherches par index ou par clé en O(1) temps. En général, si vous avez besoin de quelque chose qui prend en charge la recherche rapide, recherchez une structure de données qui conserve ses éléments dans l'ordre au lieu de les trier explicitement. Si rien d'autre, C# a déjà toute la litanie de structures de données.

Answer 5

Les bonnes nouvelles sont que vous pouvez écrire ces méthodes assez facilement; et grâce à C# 3.0 méthodes d'extension, vous pouvez faire ce travail sur l'interface:

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 
} 

Maintenant, tout ce qui reste est le code TODO lui-même (et probaby récrire Sort ;-P); mais après:

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

Il est important, IList<T> a une lecture/écriture indexeur, il est certainement possible de faire les deux le genre et recherche binaire sans le hack ci-dessus.