Готовая реализация кэша с ограничением по размеру (LRU Cache) на C++

Введение

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

Концепция

Эффективная реализация LRU-кэша комбинирует два контейнера: двусвязный список (хранит порядок «от самого недавнего к самому давнему» обращения) и хеш-таблицу (для быстрого доступа к элементу по ключу за O(1)), где значения хеш-таблицы — итераторы на соответствующие элементы списка. Это позволяет получать значение по ключу, перемещать элемент в начало списка при обращении («освежая» его недавность) и вытеснять элемент с конца списка при превышении лимита размера — всё за амортизированное константное время.

Пример кода

#pragma once
#include <unordered_map>
#include <list>
#include <mutex>
#include <optional>

template <typename Key, typename Value>
class LruCache
{
public:
    explicit LruCache(size_t capacity) : m_capacity(capacity) {}

    std::optional<Value> get(const Key &key)
    {
        std::lock_guard<std::mutex> lock(m_mutex);
        auto it = m_index.find(key);
        if (it == m_index.end()) {
            return std::nullopt;
        }
        // Перемещаем элемент в начало списка — он стал "самым недавним"
        m_items.splice(m_items.begin(), m_items, it->second);
        return it->second->second;
    }

    void put(const Key &key, const Value &value)
    {
        std::lock_guard<std::mutex> lock(m_mutex);

        auto it = m_index.find(key);
        if (it != m_index.end()) {
            it->second->second = value;
            m_items.splice(m_items.begin(), m_items, it->second);
            return;
        }

        if (m_items.size() >= m_capacity) {
            // Вытесняем элемент с конца списка — самый давний по обращению
            const Key &lruKey = m_items.back().first;
            m_index.erase(lruKey);
            m_items.pop_back();
        }

        m_items.emplace_front(key, value);
        m_index[key] = m_items.begin();
    }

    size_t size() const
    {
        std::lock_guard<std::mutex> lock(m_mutex);
        return m_items.size();
    }

private:
    using ListType = std::list<std::pair<Key, Value>>;

    size_t m_capacity;
    ListType m_items; // от самого недавнего (front) к самому давнему (back)
    std::unordered_map<Key, typename ListType::iterator> m_index;
    mutable std::mutex m_mutex;
};

// Использование: кэш результатов "дорогих" вычислений
#include "lrucache.h"
#include <QDebug>

int expensiveComputation(int input)
{
    qDebug() << "Выполняется дорогое вычисление для" << input;
    return input * input;
}

void demonstrateLruCache()
{
    LruCache<int, int> cache(3); // кэш максимум на 3 элемента

    auto computeWithCache = [&cache](int input) {
        if (auto cached = cache.get(input)) {
            qDebug() << "Найдено в кэше:" << *cached;
            return *cached;
        }
        int result = expensiveComputation(input);
        cache.put(input, result);
        return result;
    };

    computeWithCache(1);
    computeWithCache(2);
    computeWithCache(3);
    computeWithCache(1); // уже в кэше — не пересчитывается
    computeWithCache(4); // кэш заполнен — вытеснит наименее недавний (2)
}

Пояснения к коду

m_items хранит пары ключ-значение в порядке недавности обращения, а m_index — хеш-таблицу для быстрого поиска итератора по ключу без линейного сканирования списка. Метод splice() у std::list перемещает элемент внутри того же списка за O(1) без перевыделения памяти — это ключевая операция, позволяющая эффективно «освежать» недавно использованный элемент, перемещая его в начало без копирования.

При добавлении нового элемента в заполненный кэш (m_items.size() >= m_capacity) вытесняется элемент с конца списка (m_items.back()) — он соответствует ключу, к которому давнее всех обращались. Использование std::optional<Value> в качестве возвращаемого типа get() явно отражает возможность отсутствия запрошенного ключа в кэше, что более выразительно, чем возврат специального «невалидного» значения.

Подводные камни

• Гранулярность блокировки — единый мьютекс на весь кэш. При высокой конкуренции из множества потоков единый std::mutex на все операции (включая простое чтение через get()) сериализует доступ — для высоконагруженных сценариев можно рассмотреть шардирование кэша (несколько независимых LRU-кэшей с распределением ключей по хешу) для снижения конкуренции.
• Инвалидация устаревших данных не входит в LRU как стратегию. LRU вытесняет по недавности обращения, но не по времени актуальности данных — если закэшированные значения могут «протухать» (например, результат сетевого запроса, действительный ограниченное время), нужен дополнительный механизм TTL (time-to-live) поверх базовой LRU-логики.
• Размер кэша по числу элементов, а не по объёму памяти. Если значения кэша сильно различаются по размеру (например, кэш изображений разного разрешения), ограничение по числу элементов может не соответствовать реальному использованию памяти — для таких случаев нужен учёт суммарного объёма, а не простого счётчика элементов.
• Стоимость хеширования сложных ключей. Если Key — тяжёлый для хеширования тип (например, длинная строка), частые вызовы get()/put() могут заметно нагружать CPU на сам процесс хеширования — для таких ключей может быть оправдано предварительное кеширование хеша внутри самого ключа.