Volver al código
C++
Una caché que olvida lo que hace más tiempo no se usa
Caché LRU con una lista y un mapa: buscar, guardar y desalojar en tiempo constante.
El problema
Consultar el mismo dato caro una y otra vez es desperdicio, pero guardar todo para siempre agota la memoria. Hace falta una caché con tope que descarte lo menos usado.
C++
#include <iostream>
#include <list>
#include <string>
#include <unordered_map>
class CacheLRU {
size_t capacidad;
std::list<std::pair<std::string, std::string>> orden; // el frente es lo más reciente
std::unordered_map<std::string, decltype(orden)::iterator> indice;
public:
explicit CacheLRU(size_t n) : capacidad(n) {}
const std::string* obtener(const std::string& clave) {
auto it = indice.find(clave);
if (it == indice.end()) return nullptr;
orden.splice(orden.begin(), orden, it->second); // lo usado pasa al frente
return &it->second->second;
}
void guardar(const std::string& clave, const std::string& valor) {
if (auto it = indice.find(clave); it != indice.end()) orden.erase(it->second);
orden.emplace_front(clave, valor);
indice[clave] = orden.begin();
if (orden.size() > capacidad) { indice.erase(orden.back().first); orden.pop_back(); }
}
};
int main() {
CacheLRU cache(2);
cache.guardar("a", "1"); cache.guardar("b", "2");
cache.obtener("a"); // "a" vuelve a ser reciente
cache.guardar("c", "3"); // sale "b"
std::cout << (cache.obtener("b") ? "b sigue" : "b salió") << "\n";
}Por qué está escrito así
- La lista guarda el orden de uso; el mapa guarda, para cada clave, dónde está en la lista. Juntas dan todo en tiempo constante.
- splice mueve un nodo al frente sin copiarlo ni invalidar los iteradores que el mapa tiene guardados.
- Cuando se pasa de la capacidad, lo que sale es el último de la lista: lo que hace más tiempo no se toca.
- obtener devuelve un puntero: nullptr significa "no está", sin excepciones ni valores mágicos.
Cómo probarlo
Guardalo como lru.cpp y corré: c++ -std=c++17 -Wall -o lru lru.cpp && ./lru
Ojo con esto
No es segura entre hilos: dos hilos a la vez corrompen la lista. Y el puntero que devuelve obtener deja de valer si esa clave se desaloja después.
Adaptalo a tu caso con IA
El botón copia este prompt con el código pegado debajo. Reemplazá los corchetes con lo tuyo y pegalo en ChatGPT, Claude, Gemini o Copilot.
El prompt
Tengo esta caché LRU en C++17. Convertila en una plantilla genérica para cualquier tipo de clave y valor, hacela segura entre hilos con un mutex, que obtener devuelva std::optional en vez de puntero, y agregá vencimiento por tiempo de [SEGUNDOS] segundos por entrada. La voy a usar para cachear [QUÉ DATOS]. Incluí una prueba mínima en main.
Ejemplo escrito y revisado a mano.
Comentarios
Todavía no hay comentarios. El primero puede ser el tuyo.
¿Lo adaptaste a algo tuyo?
Contame qué resolviste con esto, o qué le faltó.
