Portable Class Library의 SortedSet <T>에 대한 대안?

Question

PCL에 SortedSet<T>에 대한 대안이 있습니까? 아니면 내 자신을 구현해야합니까?

.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 (n) 대신 O (log n) 검색을 수행하도록 최적화 할 수 있습니다.

다른 알고리즘이 더 빠를 수 있습니다. 계속 진행할 필요없이 간단하고 잘 이해 된 알고리즘을 선택했습니다.