Dlaczego nie ma Sortuj dla IList <T>?!?! (edytowane)

Question

Byłem bardzo zaskoczony, gdy odkryłem, że nie ma bezpośredniego sposobu sortowania lub wykonywania wyszukiwania binarnego na IList < T>. Tak jak istnieją statyczne metody do sortowania i przeprowadzania wyszukiwania binarnego na tablicy, myślę, że byłoby bardzo pomocne mieć podobne statyczne metody, które wymagają IList < T>.

Aktualnie

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

życzę oni by dodać:

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

Zerknęłam na .NET Framework 4.0 Beta SDK i tam nadal nie wydaje się być rozwiązaniem ten problem.

Wiem, że mógłbym obejść ten problem, tworząc metodę rozszerzenia, która sprawdza, czy jest to lista < T>, a następnie sortuj/wyszukuj używając instancji List < T>; Jeśli jednak nie jest to instancją Listy < T>, to muszę wykonać kopię (która śmierdzi na bardzo duże listy). Wiem, że mogłem to wszystko zrobić, ale dlaczego? Czy jest jakiś powód, dla którego celowo pominęli tę funkcję?

Aby spróbować uzyskać to w środowisku .NET 4.0 Framework, stworzyłem sugestię za pośrednictwem programu Connect firmy Microsoft. Jeśli jesteś sfrustrowany, tak jak ja, w tej sprawie, zagłosuj na niego, a może zostanie dodany.

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

Answer 1

LINQ ma metodę OrderBy, która działa na wszystkich IEnumerable <T>, w tym IList <T>. Możesz zrobić to samo, używając OrderBy.

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

Answer 2

Trzeba ArrayList.Adapter, który umożliwia korzystanie z ArrayList „s sortujących rutyny, ale spowodowałoby to ogromny wpływ na wydajność dla ogólnych listach typów wartości odpakowanych, plus zarówno wirtualnych połączeń i interfejs wysyłki napowietrznych.

Dla obu typów referencyjnych i wartości, wysyłka interfejs może być kosztowne, czyli wezwanie do ICollection<T>.CopyTo tablicę T[] następnie oddzielnego rodzaju mogłaby być opcja najszybszy ogólnego przeznaczenia, w tym rozszerzenie niestandardowego bezpośrednio porządek na obiekcie IList<T>.

List<T> ma metodę Sort ponieważ może bardzo skutecznie działać na bazowym tablicy typu T[]. Po prostu nie można tego zrobić dla arbitralnego IList<T>.

Answer 3

Myślę, że jest całkiem niezły przypadek, ponieważ nie uwzględniono metody sortowania dla IList<T>. Po pierwsze, spowodowałoby to dodatkową złożoność dla tych, którzy chcą wdrożyć IList, a po drugie utrudniłoby interfejs IList dostosowanie się do Interface Segregation Principle.

Ogólnie co zrobić, jeśli trzeba wykonać coś w rodzaju na IList<T> jest utworzyć nową List<T> i przechodzą w IList<T> jako parametr

tak na przykład:

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

Answer 4

nie jestem ekspert C#, ale bardzo niewiele implementacji list obsługuje sortowanie, wyszukiwanie binarne, a nawet indeksowane pobieranie. Listy są zwykle oparte na linked lists, które zazwyczaj nie oferują sposobu pobrania elementu według jego indeksu.Jeśli chcesz szybko znaleźć element, użyj czegoś, co spowoduje uporządkowanie elementów, takich jak tree lub tablica, jak sugerują inni.

Znalazłem fakt, że IList zawiera interesującą indexed retrieval method. Możesz rozważyć użycie SortedList zamiast List, ponieważ wygląda na to, że powinno obsługiwać wyszukiwania według indeksu lub klucza w czasie O(1). Ogólnie rzecz biorąc, jeśli potrzebujesz czegoś, co zapewnia szybkie wyszukiwanie, poszukaj struktury danych, która zachowa swoje elementy, zamiast ich wyraźnego sortowania. Jeśli nic więcej, C# ma już litanię struktur danych.

Answer 5

Dobrą wiadomością jest to, że można napisać takie metody dość łatwo; a dzięki C# 3.0 metod rozszerzenie, można dokonać tej pracy na interfejsie:

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 
} 

Teraz pozostaje tylko sam kod TODO (i probaby ponownie napisać Sort ;-p); ale po tym:

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

ważne, IList<T> ma odczytu/zapisu podziałowe, więc na pewno jest to możliwe do zrobienia zarówno rodzaj i binarne-wyszukiwanie bez hack powyżej.