LRU Cache

В данном задании необходимо написать LRU-cache (least recently used cache).

Кешом называется map, который имеет ограниченный максимальный размер. Чтобы не превышать максимальный размер, при вставке нового элемента, удаляют некоторый старый (говорят — новые элементы вытесняют старые). Существуют разные стратегии вытеснения. Одна из них называется LRU (least recently used) — вытесняется самый старый не использовавшийся элемент.

Наивная реализация lru-кеша, могла бы содержать дерево поиска и двусвязный список. Двусвязный список хранил бы элементы в порядке последнего обращения. То есть в голове списка лежит последний элемент к которому обращались, в хвосте — элемент, к которому дольше всего не обращались. При обращении к элементу он переносится в голову списка. При вытеснении удаляется элемент из хвоста.

В предыдущем задании была применена оптимизация, когда один набор node-ов прошивался в два дерева. В этом задании тоже можно применить аналогичную оптимизацию. Можно завести класс node следующего вида:

struct node { key_type key; mapped_type mapped; node* left; node* right; node* parent; node* next; node* prev; };

left, right, parent образуют бинарное дерево поиска по ключу key. next, prev — двусвязный список по последнему обращению.

В lru-кеше можно сделать ещё одну оптимизацию. Обратим внимание, что после того, как кеш достиг своего максимального размера, каждая вставка нового элемента приводит к удалению старого. Наивная реализация могла бы выделять новую node-у, и освобождать старую. Но эту операцию можно сделать вообще без аллокации памяти, если переиспользовать node от старого элемента.

Задание

В этом задании необходимо реализовать класс со следующим интерфейсом:

struct lru_cache
{
    // Вы можете определить эти тайпдефы по вашему усмотрению.
    typedef ... key_type;
    typedef ... mapped_type;
    typedef std::pair<key_type, mapped_type> value_type;

    // Bidirectional iterator.
    struct iterator;

    // Создает пустой lru_cache с указанной capacity.
    lru_cache(size_t capacity);

    // Деструктор. Вызывается при удалении объектов lru_cache.
    // Инвалидирует все итераторы ссылающиеся на элементы этого lru_cache
    // (включая итераторы ссылающиеся на элементы следующие за последними).
    ~lru_cache();

    // Поиск элемента.
    // Возвращает итератор на элемент найденный элемент, либо end().
    // Если элемент найден, он помечается как наиболее поздно использованный.
    iterator find(key_type);

    // Вставка элемента.
    // 1. Если такой ключ уже присутствует, вставка не производиться, возвращается итератор
    //    на уже присутствующий элемент и false.
    // 2. Если такого ключа ещё нет, производиться вставка, возвращается итератор на созданный
    //    элемент и true.
    // Если после вставки число элементов кеша превышает capacity, самый давно не
    // использованный элемент удаляется. Все итераторы на него инвалидируется.
    // Вставленный либо найденный с помощью этой функции элемент помечается как наиболее поздно
    // использованный.
    std::pair<iterator, bool> insert(value_type);

    // Удаление элемента.
    // Все итераторы на указанный элемент инвалидируются.
    void erase(iterator);

    // Возващает итератор на элемент с минимальный ключом.
    iterator begin() const;
    // Возващает итератор на элемент следующий за элементом с максимальным ключом.
    iterator end() const;
};

struct lru_cache::iterator
{
    // Элемент на который сейчас ссылается итератор.
    // Разыменование итератора end() неопределено.
    // Разыменование невалидного итератора неопределено.
    value_type const& operator*() const;

    // Переход к элементу со следующим по величине ключом.
    // Инкремент итератора end() неопределен.
    // Инкремент невалидного итератора неопределен.
    iterator& operator++();
    iterator operator++(int);

    // Переход к элементу со следующим по величине ключом.
    // Декремент итератора begin() неопределен.
    // Декремент невалидного итератора неопределен.
    iterator& operator--();
    iterator operator--(int);
};

// Сравнение. Итераторы считаются эквивалентными если они ссылаются на один и тот же элемент.
// Сравнение с невалидным итератором не определено.
// Сравнение итераторов двух разных контейнеров не определено.
bool operator==(lru_cache::iterator, lru_cache::iterator);
bool operator!=(lru_cache::iterator, lru_cache::iterator);

Необходимо, чтобы lru_cache создавал один объект в памяти на каждый элемент хранящийся в нем. Необходимо, чтобы insert приводящий к вытеснению уже существующего элемента не аллоцировал память.

Необходимо, чтобы lru_cache использовал внутри себя дерево поиска (не обязательно сбалансированное), а операции поиска/вставки/удаления работали за O(h), где h — высота дерева.

Конструкторы копирования и оператор присваивания lru_cache-а должны быть запрещены.

В случаях когда это задание не предписывает определенного поведения, любое поведение конкретной реализации считается удовлетворяющим заданию. Предполагается, что не все случаи неопределенного поведения, указанные в этом задании, можно свести к assert-у, не жертвуя простотой или эффективностью реализации. В тех случаях, где это уместно, рекомендуемым поведением является срабатывание assert-а.

LRU Cache

Введение

Задание