Задача с собеседования в Яндекс

Есть 2 взаимодействующие системы. Одна из них - БД хранящая информацию о пользователях, вторая - использует эту информацию для принятия решения. Пользователи обычно используют систему периодами (сессиями), и в рамках сессии делают много запросов. Между сессиями достаточно большой промежуточный интервал. Хочется сэкономить ресурсы БД и повторяющиеся запросы по возможности не выполнять заново, а выдавать уже запомненный где-то результат.

Необходимо реализовать класс кеша. Класс должен иметь метод для получения данных по ключу, метод для вставки данных. Ограничение на максимальное количество элементов (или размер потребляемой памяти).

Решение:
Покумекав, поразмыслив, в конце вы должны прийти к выбору LRU-кеша
Код класса (по-хорошему надо писать шаблонную реализацию)
template <class Key,
class T,
class Hash = std::hash<Key>,
class Pred = std::equal_to<Key>,
class Alloc = std::allocator<std::pair<const Key, T>> >
class LRU;

Со сложностью вставки\поиска за O(1)
Методы:

const_iterator find(const Key& key) const;
iterator find(const Key& key) const;
std::pair<iterator, bool> insert(const Key& key, const T& val);
По аналогии с STL контейнерами

@algoses