Отсортированная структура данных

Вам нужно будет написать свою собственную коллекцию. Концептуально то, что вы хотите, выглядит как древовидная структура, как реализовано 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. Довольный.