Daily bit(e) C++. LRU кэш

Добавлено 5 октября 2026 в 11:49

Daily bit(e) C++ 133, популярная задача на собеседованиях – реализация LRU-кэша.

Сегодня рассмотрим классическую задачу для собеседования по C++: реализацию LRU-кэша (кэша с вытеснением элемента, к которому дольше всего не было обращений).

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

struct LRU {
    LRU(int capacity);
    
    /* Возвращает значение, ассоциированное с ключом за O(1). 
           
       Если ключ не представлен, возвращает -1.
    */
    int get(int key);
    
    /* Обновляет или вставляет ключ в кэш за O(1).

       При вставке, если доступной емкости не осталось,
       наиболее давно использовавшийся ключ (get/put) будет удален.
    */
    void put(int key, int value);
};

Прежде чем переходить к решению, рекомендую попытаться решить задачу самостоятельно. Вот ссылка на Compiler Explorer с несколькими тестовыми примерами: https://compiler-explorer.com/z/8nferf1GG.

Решение

Для реализации этой структуры данных нам понадобятся следующие операции:

поиск значения по ключу за O(1)
перемещение ключа в начало (перед другими ключами) за O(1)
вставка и удаление за O(1)

Неупорядоченные контейнеры обеспечивают поиск по ключу за O(1). Списки поддерживают операцию склейки (splicing), которую можно использовать для перемещения ключа мимо других ключей за O(1).

Неупорядоченные контейнеры позволяют выполнять вставку и удаление за O(1); списки обеспечивают вставку и удаление за O(1) в начале или в конце списка.

#include <list>
#include <unordered_map>

struct LRU 
{
    LRU(int capacity) : capacity_{capacity} { }
    
    /* Возвращает значение, ассоциированное с ключом за O(1). 
           
       Если ключ не представлен, возвращает -1.
    */
    int get(int key) 
    {
        auto it = lookup_.find(key);
        // Если у нас нет этого ключа в кэше, возвращаем -1
        if (it == lookup_.end())
            return -1;
        
        // Переместить ключ к последним используемым
        bump(it->second);
        // Вернуть ассоциированное значение
        return it->second->second;
    }
    
    /* Обновляет или вставляет ключ в кэш за O(1).

       При вставке, если доступной емкости не осталось,
       наиболее давно использовавшийся ключ (get/put) будет удален.
    */
    void put(int key, int value) 
    {
        auto it = lookup_.find(key);
        if (it == lookup_.end()) 
        {
            // Вставка; убедиться, что есть месть
            maybe_drop();
            // Вставить, как последний используемый
            store_.push_front(std::pair{key,value});
            // Также добавить в карту поиска
            lookup_.insert_or_assign(key, store_.begin());
        } 
        else 
        {
            // Обновить, переместить ключ к последним используемым
            bump(it->second);
            // Обновить ассоциированное значение
            it->second->second = value;
        }
    }

private:
    void bump(std::list<std::pair<int,int>>::iterator it) 
    {
        // Переместить элемент в начало списка
        store_.splice(store_.begin(), store_, it);
    }

    void maybe_drop() 
    {
        // Место еще есть, ничего не делаем
        if (capacity_ > std::ssize(store_))
            return;
        // Ключ, к которому обращались давнее всего, находится в конце списка
        // Удалить и из карты, и из списка
        lookup_.erase(store_.back().first);
        store_.pop_back();
    }

    ptrdiff_t capacity_;
    using list = std::list<std::pair<int,int>>;
    list store_;
    std::unordered_map<int,list::iterator> lookup_;
};

Пример на Compiler Explorer

Решение

Теги