排序的数据结构

Question

我要寻找一个排序键的数据结构在.NET 4.0中支持以下功能：

1. 在O(n log n)时间
2. 获取O(log n)时间关键的项目创建结构
3. 在集合中查找大于或等于O(log n)时间内给定参数的最小项目（我们将使用最可能的double键入它）
4. 找到O(log n)中的最大项目小于给定参数
5. 对于集合中的一个给定的项目，获得下一个和上一个项目
6. 键必须是唯一的集合

我参加了一个快速浏览一下SortedDictionary和SortedList，但他们不似乎从上面的列表中提供了（3）和（4）。 SortedDictionary似乎不支持（5）， ，我不确定SortedList是否支持（6）。

不幸的是我们仅限于.Net4。

Answer 1

你将需要编写自己的集合。从概念上说，你想要的是一个基于树的结构，这就是SortedDictionary的实现方式。底层结构有潜力执行所有这些任务，但.NET实现并未将它们全部公开，也没有提供足够的底层工具来实现这些目标，迫使您从头开始。

幸运的是，构建这样的基于树的结构对介绍性程序员来说是一项常见任务，因此您会发现许多开源第三方实现需要查看，要么能实现您的目标，要么作为一个起点。如果你愿意，你也可以考虑grabbing the source of SortedDictionary并重新编译你自己的版本。

Answer 2

我已经为你创建了一个分类词典。我希望它能满足你的需求。

public class MyDictionary<TKey, TItem> : IDictionary<TKey, TItem> 
    where TKey : IComparable<TKey> 
    where TItem : IEquatable<TItem> 
{ 
    private readonly List<TKey> keys; 
    private readonly List<TItem> items; 
    private readonly ReadOnlyCollection<TKey> roKeys; 
    private readonly ReadOnlyCollection<TItem> roItems; 

    public MyDictionary() 
    { 
     keys = new List<TKey>(); 
     items = new List<TItem>(); 
     roKeys = new ReadOnlyCollection<TKey>(keys); 
     roItems = new ReadOnlyCollection<TItem>(items); 
    } 

    public MyDictionary(int capacity) 
    { 
     keys = new List<TKey>(capacity); 
     items = new List<TItem>(capacity); 
     roKeys = new ReadOnlyCollection<TKey>(keys); 
     roItems = new ReadOnlyCollection<TItem>(items); 
    } 

    public MyDictionary(TKey[] keys, TItem[] items) 
    { 
     if (keys == null) 
      throw new ArgumentNullException("keys"); 
     if (items == null) 
      throw new ArgumentNullException("items"); 
     if (keys.Length != items.Length) 
      throw new ArgumentException("Arrays lengths must be equal."); 

     TKey[] keysCopy = new TKey[keys.Length]; 
     keys.CopyTo(keysCopy, 0); 
     TItem[] itemsCopy = new TItem[items.Length]; 
     items.CopyTo(itemsCopy, 0); 

     Array.Sort(keysCopy, itemsCopy); 

     this.keys = new List<TKey>(keysCopy); 
     this.items = new List<TItem>(itemsCopy); 
     roKeys = new ReadOnlyCollection<TKey>(keys); 
     roItems = new ReadOnlyCollection<TItem>(items); 
    } 

    public int BinarySearch(TKey key) 
    { 
     return keys.BinarySearch(key); 
    } 

    public bool ContainsKey(TKey key) 
    { 
     return BinarySearch(key) >= 0; 
    } 

    public void Add(TKey key, TItem item) 
    { 
     int index = BinarySearch(key); 
     if (index >= 0) 
      throw new ArgumentException(String.Format("The key {0} already exists.", key), "key"); 
     index = ~index; 
     keys.Insert(index, key); 
     items.Insert(index, item); 
    } 

    public void Add(KeyValuePair<TKey, TItem> item) 
    { 
     Add(item.Key, item.Value); 
    } 

    public bool Remove(TKey key) 
    { 
     int index = BinarySearch(key); 
     if (index < 0) 
      return false; 
     keys.RemoveAt(index); 
     items.RemoveAt(index); 
     return true; 
    } 

    public bool Remove(KeyValuePair<TKey, TItem> item) 
    { 
     int index = BinarySearch(item.Key); 
     if (index < 0) 
      return false; 
     index = ~index; 
     keys.RemoveAt(index); 
     items.RemoveAt(index); 
     return true; 
    } 

    public bool Contains(KeyValuePair<TKey, TItem> item) 
    { 
     int index = BinarySearch(item.Key); 
     if (index < 0) 
      return false; 
     index = ~index; 
     return items[index].Equals(item.Value); 
    } 

    public bool TryGetValue(TKey key, out TItem value) 
    { 
     int index = BinarySearch(key); 
     if (index < 0) 
     { 
      value = default(TItem); 
      return false; 
     } 
     value = items[index]; 
     return true; 
    } 

    public TItem this[TKey key] 
    { 
     get 
     { 
      int index = BinarySearch(key); 
      if (index < 0) 
       throw new ArgumentException(String.Format("The key {0} not found.", key), "key"); 
      return items[index]; 
     } 
     set 
     { 
      int index = BinarySearch(key); 
      if (index < 0) 
       throw new ArgumentException(String.Format("The key {0} not found.", key), "key"); 
      items[index] = value; 
     } 
    } 

    public ICollection<TKey> Keys 
    { 
     get { return roKeys; } 
    } 

    public ICollection<TItem> Values 
    { 
     get { return roItems; } 
    } 

    public IEnumerator<KeyValuePair<TKey, TItem>> GetEnumerator() 
    { 
     return keys.Select((t, i) => new KeyValuePair<TKey, TItem>(t, items[i])).GetEnumerator(); 
    } 

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

    public void Clear() 
    { 
     keys.Clear(); 
     items.Clear(); 
    } 

    public void CopyTo(KeyValuePair<TKey, TItem>[] array, int arrayIndex) 
    { 
     Array.Copy(keys.Select((t, i) => new KeyValuePair<TKey, TItem>(t, items[i])).ToArray(), 0, array, arrayIndex, Count); 
    } 

    public int Count 
    { 
     get { return keys.Count; } 
    } 

    public int Capacity 
    { 
     get { return keys.Capacity; } 
     set 
     { 
      if (value < 0) 
       throw new ArgumentOutOfRangeException("value"); 
      keys.Capacity = value; 
      items.Capacity = value; 
     } 
    } 

    public bool IsReadOnly 
    { 
     get { return false; } 
    } 

    public int GetSmallerOrEqualIndex(TKey key) 
    { 
     int index = BinarySearch(key); 
     if (index >= 0) 
      return index; 
     index = ~index; 
     return index - 1; 
    } 

    public int GetGreaterOrEqualIndex(TKey key) 
    { 
     int index = BinarySearch(key); 
     if (index >= 0) 
      return index; 
     index = ~index; 
     return index; 
    } 

    public KeyValuePair<TKey, TItem> GetItem(int index) 
    { 
     return new KeyValuePair<TKey, TItem>(keys[index], items[index]); 
    } 
} 

的要求：

1. 不满意（我的工作就可以了）。目前，通过MyDictionary(TKey[] keys, TItem[] items)构造函数初始化的操作平均为O（n log n）操作，最坏情况下为O（n^2）操作。添加单个项目是O（n）操作。
2. 满意。
3. 满意（GetGreaterOrEqualIndex方法）。
4. 满意（GetSmallerOrEqualIndex方法）。
5. 如果我正确理解“给定项目”，则不直接满意，但对项目的索引满意。
6. 满意。