Одна из основных проблем с LRU-кешами состоит в том, что существует мало «const» операций, большинство из них изменят базовое представление (хотя бы потому, что они увеличивают доступ к элементу).
Это, конечно, очень неудобно, потому чтоэто означает, что это не традиционный контейнер STL, и поэтому любая идея выставления итераторов довольно сложна: когда разыменовывается итератор, это доступ, который должен изменить список, по которому мы итерируем ... ой мой.
И есть соображения производительности, как с точки зрения скорости, так и с точки зрения потребления памяти.
К сожалению, вам понадобится какой-то способ организовать ваши данные в очередь (LRU) (с возможностью удаленияэлементы из середины), и это означает, что ваши элементы должны быть независимы друг от друга.A std::list подходит, конечно, но это больше, чем нужно.Здесь достаточно односвязного списка, так как вам не нужно повторять список в обратном направлении (в конце концов, вы просто хотите очередь).
Однако одним из основных недостатков является их плохое месторасположение,если вам нужна большая скорость, вам нужно будет предоставить свой собственный распределитель (пул?) для узлов, чтобы они были как можно ближе друг к другу.Это также несколько облегчит фрагментацию кучи.
Далее вам, очевидно, потребуется структура индекса (для бита кеша).Наиболее естественным является обращение к хэш-карте.std::tr1::unordered_map, std::unordered_map или boost::unordered_map обычно являются качественной реализацией, некоторые из них должны быть доступны для вас.Они также выделяют дополнительные узлы для обработки коллизий хешей, вы можете предпочесть другие виды хеш-карт, посмотрите статью Википедии на эту тему и прочитайте о характеристиках различных методов реализации.
Продолжениеесть (очевидная) поддержка потоков.Если вам не нужна поддержка потоков, тогда все в порядке, если вы делаете, однако, это немного сложнее:
- Как я уже сказал, на такой структуре мало операций
const, поэтомувам на самом деле не нужно различать доступ для чтения / записи - Внутренняя блокировка в порядке, но вы можете обнаружить, что она не подходит для ваших целей.Проблема с внутренней блокировкой заключается в том, что она не поддерживает концепцию «транзакции», поскольку освобождает блокировку между каждым вызовом.Если это ваш случай, преобразуйте ваш объект в мьютекс и предоставьте метод
std::unique_ptr<Lock> lock() (в отладке вы можете утверждать, что блокировка берется в точке входа каждого метода) - Есть (в блокировкестратегии) проблема повторного входа, т. е. возможность "заблокировать" мьютекс из одного потока, проверьте Boost.Thread для получения дополнительной информации о различных доступных блокировках и мьютексах
Наконец, естьпроблема сообщения об ошибках.Поскольку ожидается, что кэш не сможет извлечь введенные вами данные, я бы подумал об использовании исключения «плохой вкус».Рассмотрим либо указатели (Value*), либо Boost. Опционально (boost::optional<Value&>).Я бы предпочел Boost.Optional, потому что его семантика ясна.