可移植类库中的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）...

还有其他算法可能会更快;但没有更多的继续，我选择了一个简单而且很好理解的算法。