Установка i-го значения SortedDictionary

Question

Мне нужно установить значение элемента в моем отсортированномDictionary, к которому обращается индекс.

I.e.

sortedDictionary.Values[index] = value; // compile error 

Обратите внимание, что следующее неверно, поскольку к нему обращаются по ключу, а не по индексу.

sortedDictionary[index] = value; // incorrect 

Я придумал следующее решение, но интуиция говорит мне, что это медленно. Я предполагаю, что доступ по ключу равен O (log N), а доступ по индексу - O (1), но я не уверен.

sortedDictionary[sortedDictionary.ElementAt(index).Key] = value; 

Некоторые фона:

Я использую SortedDictionary, потому что нужны быстрые вставки, удаления, поиски, и, чтобы иметь возможность доступа к соседним элементам. (т. е. следующий самый высокий или следующий минимум). Эффективность важна.

Answer 1

Это немного компромисс.

Вы можете использовать SortedList и получить быстрый индексный поиск, но вы пожертвуете скоростью вставки.

Цитирую MSDN:

... Еще одно различие между SortedDictionary<(Of <(TKey, TValue>)>) и SortedList<(Of <(TKey, TValue>)>) классов является то, что SortedList<(Of <(TKey, TValue>)>) поддерживает эффективное индексированный извлечение ключей и значений через коллекций, возвращаемых ключей и Ценности. Не требуется для регенерации списков при доступе к объектам , потому что списки - это всего лишь обертки для внутренних массивов и значений .

Оба SortedDictionary и SortedList реализованы IDictionary, поэтому я хотел бы получить некоторые тестовые данные и код профилировщика вместе и попробовать оба.

Если ни один из них достаточно быстр, вам может потребоваться начать использовать Dictionary (быстрые вставки, обновления и поиск ключей) и вручную поддерживать индекс во второй структуре данных.