排序的数据结构

您将需要编写自己的集合。从概念上讲，您想要的似乎是基于树的结构，这就是SortedDictionary的实现方式。底层结构具有实现所有这些任务的潜力，. net实现根本没有公开所有这些任务，也没有提供对足够的底层工具的访问来完成这些目标，迫使您从头开始。

幸运的是，构建这种基于树的结构对于入门级程序员来说是一项常见的任务，因此您将找到大量的开源第三方实现来查看，这些实现可以实现您的目标，或者作为起点。如果您愿意，还可以考虑获取SortedDictionary的源代码并重新编译您自己的版本。

我已经为您创建了一个排序字典。我希望它能满足你的需要。

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. 满意。