Обнаружьте и исправьте дефекты в реализации LRU‑кэша

Условие

Найдите недочёты в следующем классе, из‑за которых его нельзя использовать в продакшн‑окружении.

class TLruCache {
private:
    int maxSize = 0;
    int timestamp = 0;
    unordered_map<int, int> lastAccess;
    unordered_map<int, int> storage;
    set<pair<int, int>> orderSet;

public:
    TLruCache(int sizeLimit) : maxSize(sizeLimit) {}

    void Erase(int key) {
        if (!storage.count(key)) {
            throw runtime_error("key not found");
        }
        orderSet.erase({lastAccess[key], key});
        lastAccess.erase(key);
        storage.erase(key);
    }

    void Set(int key, int value) {
        if (storage.count(key)) {
            orderSet.erase({lastAccess[key], key});
            storage.erase(key);
            lastAccess.erase(key);
        }
        if (orderSet.size() == maxSize) {
            auto [_, evictKey] = *orderSet.begin();
            Erase(evictKey);
        }
        lastAccess[key] = timestamp++;
        storage[key] = value;
        orderSet.insert({lastAccess[key], key});
    }

    int Get(int key) {
        if (!storage.count(key)) {
            throw runtime_error("key not found");
        }
        orderSet.erase({lastAccess[key], key});
        lastAccess[key] = timestamp++;
        orderSet.insert({lastAccess[key], key});
        return storage[key];
    }
};

Ответ

При нулевой ёмкости Set разыменовывает begin пустого set. Также опасны переполнение signed timestamp, рассогласование трёх контейнеров при исключении и отсутствие межпоточной синхронизации.

Сразу отклоняйте отрицательную ёмкость и явно задайте поведение нулевой: запрет или кеш, ничего не сохраняющий. Текущие операции стоят O(log n) из-за set, а timestamp со временем переполняется.

Типичное исправление архитектуры — list узлов в порядке использования и unordered_map ключ → итератор. Get перемещает узел в начало через splice, вытеснение удаляет хвост. При вставке сначала создайте узел и запись индекса с откатом при ошибке, лишь затем вытесняйте старое. Копирование кеша требует перестроения итераторов; при общем доступе защитите всю составную операцию, а не контейнеры по отдельности.