Tại sao không có Sắp xếp cho IList <T>?!?! (đã chỉnh sửa)

Question

Tôi đã rất ngạc nhiên khi phát hiện ra rằng không có cách nào trực tiếp để sắp xếp hoặc thực hiện tìm kiếm nhị phân trên một IList < T>. Cũng giống như có các phương pháp tĩnh để sắp xếp và thực hiện tìm kiếm nhị phân trên một mảng, tôi nghĩ rằng nó sẽ rất hữu ích để có các phương thức tĩnh tương tự có một IList < T>.

Hiện tại:

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

Tôi ước họ sẽ thêm:

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

Tôi liếc nhìn .NET Framework 4.0 Beta SDK và có vẫn không xuất hiện như một giải pháp cho vấn đề này.

tôi biết rằng tôi có thể làm việc này bằng cách tạo ra một phương pháp khuyến nông để kiểm tra nếu nó là một danh sách < T> và sau đó sắp xếp/tìm kiếm bằng cách sử dụng Danh sách < T> Ví dụ; tuy nhiên, nếu nó không phải là một thể hiện của một Danh sách < T>, thì tôi phải thực hiện một bản sao (mà stinks cho các danh sách rất lớn). Tôi biết tôi có thể làm tất cả những điều này, nhưng tại sao? Có lý do gì mà họ đã cố ý bỏ qua tính năng này không?

Để cố gắng thực hiện điều này trong .NET 4.0 Framework, tôi đã tạo một đề xuất qua chương trình Kết nối của Microsoft. Nếu bạn thất vọng như tôi về vấn đề này, hãy bỏ phiếu cho nó và có thể nó sẽ được thêm vào.

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

Answer 1

LINQ có phương thức OrderBy hoạt động trên tất cả IEnumerable <T>, bao gồm IList <T>. Bạn có thể thực hiện điều tương tự bằng cách sử dụng OrderBy.

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

Answer 2

Bạn có ArrayList.Adapter cho phép việc sử dụng các ArrayList 's sắp xếp thói quen, nhưng nó sẽ gây ra một tác động hiệu quả rất lớn cho các danh sách chung của các loại giá trị không có hộp bọc, cộng với cả cuộc gọi và giao diện văn ảo trên cao. Đối với cả hai loại tham chiếu và giá trị, việc gửi giao diện có thể tốn kém, nghĩa là cuộc gọi tới ICollection<T>.CopyTo một mảng T[] theo sau là sắp xếp riêng có thể là tùy chọn mục đích chung nhanh nhất, bao gồm tiện ích mở rộng tùy chỉnh để sắp xếp trực tiếp trên đối tượng IList<T>.

List<T> có một phương pháp Sort vì nó có thể rất hiệu quả hoạt động trên các mảng cơ bản của loại T[]. Đơn giản là không có cách nào để làm điều này cho một tùy ý IList<T>.

Answer 3

Tôi nghĩ rằng có trường hợp khá tốt để không bao gồm phương thức sắp xếp cho IList<T>. Đầu tiên, nó sẽ tạo thêm sự phức tạp cho những người muốn thực hiện một IList và thứ hai nó sẽ làm cho nó khó hơn cho giao diện IList để phù hợp với Interface Segregation Principle.

Nói chung những gì tôi làm gì nếu tôi cần phải thực hiện một sắp xếp trên một IList<T> là tạo ra một mới List<T> và vượt qua trong IList<T> như một tham số

để ví dụ:

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

Answer 4

Tôi không một chuyên gia C#, nhưng rất ít triển khai Danh sách hỗ trợ phân loại, tìm kiếm nhị phân hoặc thậm chí là truy lục được lập chỉ mục. Danh sách nói chung dựa trên linked lists, thường không cung cấp cách thức truy xuất một mục theo chỉ mục của nó theo cách O(1).Nếu bạn muốn xác định nhanh một phần tử, hãy sử dụng thứ gì đó giữ các phần tử theo thứ tự được sắp xếp như một số tree hoặc một mảng theo đề xuất của những người khác.

Tôi thấy thực tế là IList bao gồm một thú vị indexed retrieval method. Bạn có thể muốn xem xét sử dụng SortedList thay vì List vì có vẻ như nó sẽ hỗ trợ tra cứu theo chỉ mục hoặc khóa trong thời gian O(1). Nói chung, nếu bạn cần một cái gì đó hỗ trợ tra cứu nhanh, hãy tìm cấu trúc dữ liệu giữ nguyên tố của nó theo thứ tự thay vì sắp xếp chúng một cách rõ ràng. Nếu không có gì khác, C# có khá nhiều cấu trúc dữ liệu.

Answer 5

Tin tốt là bạn có thể viết phương pháp như vậy khá dễ dàng; và nhờ C# 3.0 phương pháp khuyến nông, bạn có thể làm cho công việc này trên giao diện:

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 
} 

Bây giờ tất cả những gì còn lại là mã TODO bản thân (và probaby lại viết Sort ;-p); nhưng sau đó:

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

Quan trọng hơn, IList<T> có đọc/ghi indexer, vì vậy nó chắc chắn có thể làm cả hai loại và nhị phân tìm kiếm mà không hack ở trên.