Desafio C++

Cache LRU com unordered_map e list

Enunciado

Implemente uma classe LRUCache que armazena pares chave-valor (chave e valor inteiros) com capacidade máxima. Quando a capacidade é excedida, o item menos recentemente usado (LRU) deve ser removido. As operações get(chave) e put(chave, valor) devem ter complexidade média O(1). Use std::unordered_map e std::list para implementar.

Requisitos

  • A classe deve ter um construtor que recebe a capacidade máxima.
  • O método get(chave) retorna o valor associado ou -1 se a chave não existir, e marca o item como recentemente usado.
  • O método put(chave, valor) insere ou atualiza o valor, e remove o item menos recentemente usado se a capacidade for excedida.
  • Usar std::unordered_map para mapear chaves a iteradores da lista, e std::list para manter a ordem de uso.

Código inicial

#include <iostream>
#include <unordered_map>
#include <list>

class LRUCache {
public:
    LRUCache(int capacidade) {
        // TODO
    }
    int get(int chave) {
        // TODO
        return -1;
    }
    void put(int chave, int valor) {
        // TODO
    }
private:
    int cap;
    std::list<std::pair<int, int>> itens; // frente = mais recente
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> mapa;
};

int main() {
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    std::cout << cache.get(1) << "\n"; // 1
    cache.put(3, 3);                   // remove chave 2
    std::cout << cache.get(2) << "\n"; // -1
    cache.put(4, 4);                   // remove chave 1
    std::cout << cache.get(1) << "\n"; // -1
    std::cout << cache.get(3) << "\n"; // 3
    std::cout << cache.get(4) << "\n"; // 4
    return 0;
}

Saída esperada

1
-1
-1
3
4
Ver dica

Use std::list para armazenar os pares (chave, valor) na ordem de uso: frente = mais recente. No get, mova o item para a frente com splice. No put, se a chave existir, atualize e mova para a frente; senão, insira na frente e, se exceder a capacidade, remova o último elemento da lista e apague do mapa.

Mostrar solução 
#include <iostream>
#include <unordered_map>
#include <list>

class LRUCache {
public:
    LRUCache(int capacidade) : cap(capacidade) {}

    int get(int chave) {
        auto it = mapa.find(chave);
        if (it == mapa.end()) return -1; // não encontrado
        // Move o item para a frente da lista (mais recente)
        itens.splice(itens.begin(), itens, it->second);
        return it->second->second;
    }

    void put(int chave, int valor) {
        auto it = mapa.find(chave);
        if (it != mapa.end()) {
            // Chave já existe: atualiza valor e move para a frente
            it->second->second = valor;
            itens.splice(itens.begin(), itens, it->second);
        } else {
            // Chave nova: insere na frente
            if (itens.size() == cap) {
                // Remove o menos recentemente usado (último da lista)
                int chave_antiga = itens.back().first;
                mapa.erase(chave_antiga);
                itens.pop_back();
            }
            itens.emplace_front(chave, valor);
            mapa[chave] = itens.begin();
        }
    }

private:
    int cap;
    std::list<std::pair<int, int>> itens; // frente = mais recente
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> mapa;
};

int main() {
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    std::cout << cache.get(1) << "\n"; // 1
    cache.put(3, 3);                   // remove chave 2
    std::cout << cache.get(2) << "\n"; // -1
    cache.put(4, 4);                   // remove chave 1
    std::cout << cache.get(1) << "\n"; // -1
    std::cout << cache.get(3) << "\n"; // 3
    std::cout << cache.get(4) << "\n"; // 4
    return 0;
}

Passo a passo

  1. A classe LRUCache tem dois membros: itens (lista de pares chave-valor na ordem de uso) e mapa (de chave para iterador da lista).
  2. O construtor apenas guarda a capacidade.
  3. Em get, buscamos a chave no mapa. Se não existir, retornamos -1.
  4. Se existir, usamos splice para mover o nó da lista para a frente (marcando como recente) e retornamos o valor.
  5. Em put, se a chave já existe, atualizamos o valor e movemos para a frente.
  6. Se a chave é nova, verificamos se a lista está cheia. Se sim, removemos o último elemento (LRU) e apagamos sua entrada no mapa.
  7. Inserimos o novo par na frente da lista e atualizamos o mapa com o iterador para o novo nó.

Por que funciona

A lista mantém a ordem de uso: frente = mais recente, trás = menos recente. O unordered_map mapeia cada chave para o iterador do nó na lista, permitindo acesso O(1) médio. A operação splice move um nó sem realocar, em tempo constante. Assim, get e put são O(1) médio.

Erros comuns

  • Esquecer de atualizar o iterador no mapa após splice: o iterador permanece válido, mas se você usar push_front e pop_back sem atualizar, pode invalidar iteradores.
  • No put, ao remover o LRU, esquecer de apagar a chave do mapa: o mapa fica com uma chave obsoleta e futuras buscas retornam iterador inválido.
  • Usar itens.erase em vez de splice para mover: isso invalida o iterador no mapa, causando comportamento indefinido.

Outra forma de resolver

Usar std::map para manter a ordem por timestamp (contador de uso) em vez de lista. Cada operação incrementa um contador global e atualiza o timestamp da chave. Para remover o LRU, busca-se a chave com menor timestamp. Complexidade O(log n) por operação, mas mais simples de implementar.

Saída esperada

1
-1
-1
3
4