可移植類庫中的SortedSet <T>的替代方案？

Question

SortedSet<T> PCL有沒有其他的替代品？或者我必須執行我自己的？

我需要一個非重複字符串的索引列表，我可以在支持.NET 4.0的PCL中搜索。我目前的解決方法是依靠一個List<T>對象，調用它的Sort方法並使用BinarySearch方法。它有效，但我希望我能做得更好。

Answer 1

該PCL配置文件中沒有「排序」集合。因此，您必須在另一個集合上調用Sort方法來對其進行排序或編寫自己的排序集合。如果您只需要一個集合，那麼您可以使用簡單的二進制搜索/插入來將項目添加到集合中。使用後盾List<T>可能是這樣一個例子：

public class SortedCollection<T> : ICollection<T> 
{ 
    private readonly List<T> collection = new List<T>(); 
    // TODO: initializable: 
    private readonly IComparer<T> comparer = Comparer<T>.Default; 

    public void Add(T item) 
    { 
     if (Count == 0) 
     { 
      collection.Add(item); 
      return; 
     } 
     int minimum = 0; 
     int maximum = collection.Count - 1; 

     while (minimum <= maximum) 
     { 
      int midPoint = (minimum + maximum)/2; 
      int comparison = comparer.Compare(collection[midPoint], item); 
      if (comparison == 0) 
      { 
       return; // already in the list, do nothing 
      } 
      if (comparison < 0) 
      { 
       minimum = midPoint + 1; 
      } 
      else 
      { 
       maximum = midPoint - 1; 
      } 
     } 
     collection.Insert(minimum, item); 
    } 

    public bool Contains(T item) 
    { 
     // TODO: potential optimization 
     return collection.Contains(item); 
    } 

    public bool Remove(T item) 
    { 
     // TODO: potential optimization 
     return collection.Remove(item); 
    } 

    public IEnumerator<T> GetEnumerator() 
    { 
     return collection.GetEnumerator(); 
    } 

    IEnumerator IEnumerable.GetEnumerator() 
    { 
     return GetEnumerator(); 
    } 

    public void Clear() 
    { 
     collection.Clear(); 
    } 

    public void CopyTo(T[] array, int arrayIndex) 
    { 
     collection.CopyTo(array, arrayIndex); 
    } 

    public int Count { get { return collection.Count; } } 
    public bool IsReadOnly { get { return false; } } 
} 

我已經做了最低限度得到一個分類收集是功能。您可以優化，以便Contains和Remove識別該列表已排序，並執行O（log n）搜索而不是O（n）...

還有其他算法可能會更快;但沒有更多的繼續，我選擇了一個簡單而且很好理解的算法。