сортировка — LRU сортируется по баллам в C ++, есть такой контейнер?

Мне нужно реализовать очень эффективный LRU кеша со следующими свойствами: записи — это индексы в векторе записей кеша, каждое попадание в кеш обновляет эмпирическую оценку, вычисляемую из некоторых значений, которые можно сохранить в значении контейнера, например, количество попаданий, размер подобранного объекта и т. д.

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

До сих пор у меня была возможность придумать только вектор структур, которые содержат значения для расчета баллов, которые обновляются, и двунаправленные ссылки, которые я использую для размещения обновленного элемента на месте после пересчета баллов путем линейного поиска по его текущая позиция и сравнение результатов. Этот поиск, очевидно, может происходить вверх (когда счет обновляется, всегда увеличивается) и вниз (когда элемент выселяется, а его счет сбрасывается до 0). Линейный поиск может быть не таким уж плохим, потому что он выполняется в течение длительного времени, а количество выживших элементов увеличивается, а каждое приращение мало, поэтому элемент не должен перемещаться очень далеко, чтобы добраться до своего места, и в В случае сброса я могу начать поиск снизу.

Я знаю о контейнерах, отсортированных по STL, реализации LRU в кеш-памяти и Boost.Bimap (этот последний вариант кажется мне излишним).

Могу ли я сделать лучше, чем линейный поиск здесь? Кто-нибудь знает о реализации?

Заранее спасибо!