Tại sao không có SortedList <T> trong .NET?

Question

Tại sao chỉ có một SortedList<TKey, TValue> trông giống như một từ điển, nhưng không có SortedList<T> đó thực sự chỉ là một danh sách luôn được sắp xếp?

Theo the MSDN documentation on SortedList, nó thực sự được thực hiện nội bộ dưới dạng mảng động là KeyValuePair<TKey, TValue> luôn được sắp xếp theo khóa. Lớp học đó có hữu ích hơn không khi bạn có danh sách bất kỳ loại nào T? Điều đó cũng không phù hợp với cái tên tốt hơn?

Answer 1

Mặc dù không ai thực sự có thể cho bạn biết tại sao không có SortedList<T>, có thể thảo luận tại sao SortedList lấy chìa khóa và giá trị. Từ điển ánh xạ khóa tới giá trị. Cách điển hình để làm điều này là với cây nhị phân, bảng băm và danh sách (mảng), mặc dù bảng băm phổ biến nhất vì chúng là O (1) cho hầu hết các hoạt động.

Hoạt động chính mà nó không hỗ trợ trong O (1) là lấy khóa tiếp theo theo thứ tự. Nếu bạn muốn có thể làm điều đó, bạn thường sử dụng một cây nhị phân, cho bạn một từ điển được sắp xếp.

Nếu bạn quyết định triển khai bản đồ dưới dạng danh sách, bạn sẽ giữ các phần tử được sắp xếp theo khóa để tra cứu là O (lg n), cung cấp cho bạn một từ điển được sắp xếp khác - dưới dạng danh sách được sắp xếp. Tất nhiên tên SortedDictionary đã được sử dụng, nhưng SortedList thì không. Tôi có thể đã gọi nó là SortedListDictionary hoặc SortedDictionaryList, nhưng tôi đã không gọi tên nó.

Answer 2

Đây là danh sách có phân loại đang được thực hiện bởi khóa. Tôi chỉ suy đoán nhưng bằng cách cung cấp khả năng xác định khóa tách biệt với phần tử, phần tử của bạn không cần phải so sánh được - chỉ có nhu cầu chính. Tôi sẽ tưởng tượng rằng trong trường hợp chung này tiết kiệm một số tiền hợp lý của mã đang được phát triển để thực hiện IComparable kể từ khi khóa có thể là một loại đã được so sánh.

Answer 3

Nhận xét RPM là khá hợp lệ. Ngoài ra, với phần mở rộng LINQ, bạn có thể sắp xếp theo bất kỳ thuộc tính nào của T bằng cách sử dụng phương thức Mở rộng sắp xếp. Tôi nghĩ đó có thể là lý do chính đằng sau nó.

Answer 4

Tôi nghĩ lý do có thể chỉ là List<T> đã có BinarySearch và Insert, điều đó có nghĩa là việc triển khai danh sách luôn được sắp xếp của riêng bạn là không đáng kể.

Không phải điều này có nghĩa là lớp học SortedList<T> không thuộc về khung - chỉ có thể không phải là ưu tiên rất cao vì nó có thể dễ dàng được viết nhanh chóng bởi bất kỳ nhà phát triển nào cần.

Tôi nghĩ điều tương tự cũng đúng đối với HashSet<T>, vốn không tồn tại trước đây vì bạn có thể dễ dàng sử dụng Dictionary<T, byte> (ví dụ) để mô phỏng trước .NET 3.5.

Tôi biết đó là những gì tôi đã làm trong cả hai trường hợp: Tôi đã có một lớp UniqueSet<T> và một lớp AlwaysSortedList<T>, mà chỉ quấn một Dictionary<T, byte> và List<T> (và sử dụng BinarySearch và Insert), tương ứng.

Answer 5

Hiện nay :)

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

Tôi nghĩ rằng con đường để đi với vấn đề này là để thực hiện một phương pháp khuyến nông mà thêm vào List<T> một cách sắp xếp (chỉ cần 2 dòng mã;), và sau đó List<T> có thể được sử dụng làm danh sách được sắp xếp (giả sử bạn tránh sử dụng 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); 
    }