Альтернатива для SortedSet <T> в портативной библиотеке классов?

Question

Есть ли альтернативы в PCL для SortedSet<T>? Или я должен реализовать свое?

Мне нужен индексированный список не дублированных строк, который я могу выполнить для поиска в PCL, который поддерживает .NET 4.0. Мое текущее обходное решение заключается в том, чтобы полагаться на объект 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) ...

Существуют и другие алгоритмы, которые могут быть быстрее; но не намного больше, я выбрал простой и понятный алгоритм.