# Практика. LRU кеш ## Описание проекта Вам предстоит написать проект — динамическую библиотеку с классом для кеширования. Бенчмарки `benchmarks.cpp` и юнит-тесты `tests.cpp` для библиотеки уже готовы. Вам всего лишь остается: — Реализовать класс `LRUCache` для кеширования ключей и значений. В качестве алгоритма кеширования используйте [LRU](https://ru.m.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%BA%D1%8D%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F#Least_Recently_Used_(%D0%9D%D0%B0%D0%B8%D0%BC%D0%B5%D0%BD%D0%B5%D0%B5_%D0%B4%D0%B0%D0%B2%D0%BD%D0%BE_%D0%B8%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%B2%D1%88%D0%B8%D0%B9%D1%81%D1%8F)) (Least Recently Used): первыми из кеша удаляются наименее актуальные данные. То есть те, которые не использовались дольше всех. Добавление элемента и обращение к нему делает его наиболее актуальным. — Дополнить файлы `CMakeLists.txt`, чтобы собрать динамическую библиотеку и добиться ее успешной линковки с бенчмарками и юнит-тестами. ### Описание класса LRUCache Интерфейс класса `LRUCache` состоит из методов: — Конструктор `LRUCache(std::size_t max_size)` принимает максимальное количество элементов кеша. Значение `max_size`, равное 0, означает, что кеш отключен. — `std::pair<std::string, bool> get(int key)` принимает ключ элемента и возвращает пару. Первый элемент пары — значение ключа либо пустая строка, если ключ не найден. Второй элемент пары — флаг, сигнализирующий о присутствии ключа в кеше. Он равен `true`, если ключ найден, иначе — `false`. Ремарка: возвращать пару из некоего объекта и флага — вполне рабочий подход. Например, так работает метод [insert()](https://en.cppreference.com/w/cpp/container/map/insert.html) контейнера `std::map`. Однако можно сделать удобнее. Как? Вы узнаете в следующих главах! — `void put(int key, std::string value)` принимает ключ и значение, которые нужно закешировать. Если ключ уже находится в кеше, то он актуализируется. Если кеш отключен (`max_size == 0`), метод не должен ничего кешировать. — `void clear()` очищает кеш. — `std::size_t size()` возвращает текущее количество элементов кеша. — `std::size_t max_size()` возвращает максимальное количество элементов. Пример использования LRUCache: ```c++ LRUCache cache(2); cache.put(7, "a"); cache.put(9, "b"); cache.put(8, "c"); // вытеснение 7 cache.get(9); // "b",true cache.put(4, "d"); // вытеснение 8 cache.get(8); // "", false ``` ### Требования к реализации класса — Интерфейс класса `LRUCache` разместите в файле `lru_cache.h`, а имплементацию — в `lru_cache.cpp`. — Методы `get()` и `put()` класса `LRUCache` должны в среднем работать за `O(1)`. — Не импортируйте модуль стандартной библиотеки `std`. Вместо этого подключайте все необходимые хедеры директивой `#include`. Чтобы посмотреть, в каких хедерах находятся те или иные классы и функции, воспользуйтесь [cppreference](https://cppreference.com/). ### Автоматизация сборки проекта Дополните файлы `CMakeLists.txt` в корне проекта и в директории `lru_cache`: — Сборка должна быть релизной. Для этого задайте правильное значение переменной `CMAKE_BUILD_TYPE`. — Соберите единицу трансляции `lru_cache.cpp` в [динамическую библиотеку](/courses/cpp/chapters/cpp_chapter_0110/#block-dynamic-libs) и слинкуйте ее с бинарниками `main` и `tests`. — В юнит-тестах используется библиотека GTest (GoogleTest). Она установлена по системным путям в докер-образе, внутри которого компилируется и запускается проект. Найдите ее с помощью команды [find_package](https://cmake.org/cmake/help/latest/module/FindGTest.html) и слинкуйте с тестами `tests`. Цель для линковки - `GTest::gtest`. — В бенчмарках используется библиотека [benchmark](https://github.com/google/benchmark) от Google. Ее исходники расположены в директории `/third_party/google/benchmark-1.9.4/`. Вам нужно подключить ее к проекту с помощью модуля [FetchContent](https://cmake.org/cmake/help/latest/module/FetchContent.html) и слинковать с бенчмарками проекта. Цель для сборки `main` должна быть слинкована с файлом библиотеки `benchmark`. Библиотека хранится локально, а не в git-репозитории. Поэтому в команду [FetchContent_Declare](/courses/cpp/chapters/cpp_chapter_0120/#block-fetchcontent-example) вместо параметра `GIT_REPOSITORY` передайте параметр `SOURCE_DIR` с указанием полного пути. ## Теория Стратегия LRU эффективна, когда _чаще других_ из кеша читаются недавно прочитанные или добавленные элементы. Самая простая реализация LRU задействует [двусвязный список](/courses/cpp/chapters/cpp_chapter_0072/#block-list-it) и [хеш-таблицу.](/courses/cpp/chapters/cpp_chapter_0074/#block-unordered) Именно ее чаще всего просят написать на собеседованиях и в тестовых заданиях. — Двусвязный список хранит [пары](/courses/cpp/chapters/cpp_chapter_0073/#block-pair) ключ-значение, которые попадают в кеш. Добавляйте и удаляйте из списка элементы таким образом, чтобы они всегда были отсортированы в порядке убывания «новизны». В начале списка располагаются самые свежие записи, а в конце — те, к которым не было обращений дольше всех. — Хеш-таблица хранит пары из ключей и [итераторов,](/courses/cpp/chapters/cpp_chapter_0060/) указывающих на соответствующие этим ключам элементы списка.  {.illustration} При обращении к элементу кеша не забывайте передвигать этот элемент в начало списка. В этом вам поможет метод [std::list::splice()](https://en.cppreference.com/w/cpp/container/list/splice). Чтобы переместить элемент списка `l`, на который указывает итератор `it`, в самое начало, `splice()` вызывается следующим образом: ```c++ l.splice(l.begin(), l, it); ``` [Инвалидации итераторов](/courses/cpp/chapters/cpp_chapter_0060/#block-invalidation) на элементы списка опасаться [не стоит.](/courses/cpp/chapters/cpp_chapter_0072/#block-list-it) ## Тестирование По кнопке **«Запустить»** компилируется и запускается `benchmarks.cpp`. По кнопке **«Отправить на проверку»** выполняются юнит-тесты из файла `tests.cpp`. Запустите их, когда класс `LRUCache` будет готов к проверке. В `tests.cpp` можно посмотреть ожидаемое поведение класса. Проект будет засчитан как выполненный после успешного прохождения юнит-тестов. Если у вас возникнут проблемы при выполнении практики, воспользуйтесь подсказкой. Она доступна по кнопке со знаком вопроса.