C ++ кеш, который высвобождает элементы в зависимости от их «стоимости»

Question

Я хотел бы реализовать кеш в C ++, который является шаблонным и ограниченным по памяти. Я могу довольно легко просто получить первый элемент, когда размер достигает определенного предела, основываясь на некотором элементарном значении, таком как memlimit / (sizeof(TKey) + sizeof(TVal))

Но в идеале я хотел бы применить некоторую логику, чтобы «наименее ценный» предмет был исключен. Я думал, что логика будет чем-то вроде этого:

• При обнаружении ошибки в кэше рассчитайте ее, но также помните, сколько времени потребовалось для ее расчета. Сохраните это время (где-нибудь).
• При попадании в кэш увеличивайте количество обращений к этому кешированному значению.
• Когда предел памяти достигнут и другой элемент хочет сохранить, выселите N элементов с наименьшей «стоимостью», где «ценность» определяется как время, необходимое для вычисления, умноженное на количество обращений к нему.

Кто-нибудь может подсказать, разумна ли эта логика?

Это вызвано проблемами Project Euler, но не определено для какой-то одной из них - я хочу создать универсальный компонент, и это был бы неплохой универсальный инструмент для других вещей.

Есть ли на полке что-нибудь подходящее?

Я начинаю как

template<class TKey, class TValue>
public class cache
{
    public:
        std::map<TKey, TValue> values;

        void encache(const TKey& key, const TKey& value)
        {
            if(values.insert(std::pair<TKey, TValue>(key, value))
            {
                if(values.size() > 10000000 /* some limit */ )
                {
                     // evict the 'worst' values - ???
                }
            }
        }
}

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