PrepBro
← Назад к вопросам

Реализация LRU Cache

1.8 Middle🔥 221 комментариев
#STL контейнеры и алгоритмы#Структуры данных и алгоритмы

Условие

Реализуйте класс LRUCache (Least Recently Used Cache) с заданной ёмкостью.

Класс должен поддерживать две операции:

  • int get(int key) — возвращает значение по ключу, если ключ существует в кэше, иначе возвращает -1
  • void put(int key, int value) — обновляет значение по ключу, если ключ существует; если ключ не существует, добавляет пару ключ-значение. Если количество ключей превышает ёмкость кэша, нужно удалить наименее недавно использованный элемент.

Требования:

  • Обе операции должны выполняться за O(1) в среднем
  • Используйте стандартную библиотеку C++

Пример

LRUCache cache(2); // ёмкость = 2

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // возвращает 1
cache.put(3, 3);    // удаляет ключ 2
cache.get(2);       // возвращает -1 (не найден)
cache.put(4, 4);    // удаляет ключ 1
cache.get(1);       // возвращает -1 (не найден)
cache.get(3);       // возвращает 3
cache.get(4);       // возвращает 4

Подсказка

Рассмотрите комбинацию std::list и std::unordered_map для достижения требуемой сложности.

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Решение: Реализация LRU Cache

Описание подхода

Для достижения требуемой O(1) сложности для обеих операций используем комбинацию двусвязного списка (std::list) и хеш-таблицы (std::unordered_map):

  • std::list хранит пары (ключ, значение) в порядке использования. Самый свежий элемент находится в конце, самый старый — в начале
  • std::unordered_map отображает ключ на итератор в списке для O(1) доступа к элементам

Этот подход позволяет:

  • Быстро найти элемент по ключу (O(1) через хеш-таблицу)
  • Быстро переместить элемент в конец списка при обращении (O(1) благодаря двусвязности)
  • Быстро удалить самый старый элемент (O(1) — просто удалить начало списка)

Реализация

#include <unordered_map>
#include <list>

class LRUCache {
private:
    int capacity;
    std::unordered_map<int, std::pair<int, std::list<int>::iterator>> cache;
    std::list<int> keys;
    
    void moveToEnd(int key) {
        auto it = cache[key].second;
        keys.erase(it);
        keys.push_back(key);
        cache[key].second = std::prev(keys.end());
    }
    
public:
    LRUCache(int capacity) : capacity(capacity) {}
    
    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1;
        }
        moveToEnd(key);
        return cache[key].first;
    }
    
    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            cache[key].first = value;
            moveToEnd(key);
            return;
        }
        
        if (cache.size() == capacity) {
            int oldest = keys.front();
            keys.pop_front();
            cache.erase(oldest);
        }
        
        keys.push_back(key);
        cache[key] = {value, std::prev(keys.end())};
    }
};

Анализ сложности

  • get(key): O(1) — поиск в unordered_map + перемещение в списке
  • put(key, value): O(1) — вставка/удаление/обновление
  • Память: O(capacity)

Ключевые моменты

  1. Двусвязный список позволяет O(1) удаление элемента по итератору
  2. Хеш-таблица хранит итератор для быстрого доступа
  3. При get или put с существующим ключом — перемещаем в конец
  4. При переполнении — удаляем front() списка (самый старый)
  5. Новый элемент добавляется в back() (самый свежий)

Почему это работает

Комбинация list + unordered_map идеальна: list отслеживает порядок LRU, unordered_map даёт мгновенный доступ. Любой другой подход (только array, только tree) требует O(N) или O(log N) для какой-то из операций.