Словарь <> всегда отсортирован по значению, индекс поиска по ключу

Question

Мне нужен словарь (или любая другая коллекция), который всегда сортируется по значению и может быть проиндексирован по ключу. Моя цель - реализовать кеш, в котором объекты имеют уникальный ключ и метрику, связанную с ними. При необходимости замены кэша объекты с наименьшей метрикой удаляются. Это должно быть как можно быстрее, поэтому делать полный заказ каждый раз, когда замена сделана, не очень хороший вариант. Есть идеи? Thx

Answer 1

Примерно так должно работать нормально (не очень проверено):

http://pastebin.com/eYeE33F5

Answer 2

Вам нужен словарь, который отсортирован по значению, но также имеет индексацию по ключу. Вы не можете упорядочить данные двумя способами одновременно, поэтому вам понадобится две коллекции: ваш базовый словарь значений ключей и словарь обратного просмотра. Ваш первый - стандартный словарь, второй - SortedDictionary с теми же данными и ключами и значениями поменяны местами. Вы должны будете синхронизировать их.

Вы также можете написать собственную реализацию словаря для инкапсуляции этих двух коллекций в одну.

Answer 3

Почему бы вам просто не сохранить обычный словарь. Теперь, когда вам нужно выполнить эту замену кеша, в этот момент вы выбираете элемент с «минимальным» значением и заменяете его.

Редактировать - вот как вы получаете KeyPair с минимальным значением. Просто используйте свойства Key и Value после этого:

var minValuePair = myDictionary.OrderBy(p => p .Value).First();

Answer 4

Вы можете объединить любой вид очереди с быстрым приоритетом (смотрите здесь: Очередь с приоритетом в .Net ) со стандартным словарем для новой коллекции. При вставке нового элемента вставьте ссылку на элемент в оба контейнера. При поиске элемента по «ключу» используйте словарь. Когда вы собираетесь удалить элемент с наименьшей «метрикой», используйте очередь с приоритетами, чтобы найти его, получите ключ от самого элемента, тогда легко удалить ссылки на элементы из обоих контейнеров.

Answer 5

Это показывает, что приоритетная очередь - это то, что вы ищете. Есть хорошие реализации этого класса, использующие двоичную кучу. Пример: http://www.codeproject.com/Articles/126751/Priority-queue-in-Csharp-with-help-of-heap-data-st.aspx