Implementing an O(1) LRU Cache with Eviction Guarantees in C++20

## 1. The Low-Latency Caching Challenge In distributed operating systems and high-frequency algorithmic backends, in-memory caches must guarantee both strict $O(1)$ lookup time and predictable $O(1)$ eviction semantics. When memory limits are reached, the Least Recently Used (LRU) element must be purged immediately without scanning or reorganizing internal index tables. ```cpp #include <iostream> #include <unordered_map> #include <list> template <typename Key, typename Value> class LRUCache { private: size_t capacity; using ListIterator = typename std::list<std::pair<Key, Value>>::iterator; std::list<std::pair<Key, Value>> itemsList; std::unordered_map<Key, ListIterator> lookupTable; public: explicit LRUCache(size_t cap) : capacity(cap) {} Value* get(const Key& key) { auto it = lookupTable.find(key); if (it == lookupTable.end()) return nullptr; // Splice operation moves node to front in O(1) time without copying itemsList.splice(itemsList.begin(), itemsList, it->second); return &(it->second->second); } void put(const Key& key, const Value& val) { auto it = lookupTable.find(key); if (it != lookupTable.end()) { it->second->second = val; itemsList.splice(itemsList.begin(), itemsList, it->second); return; } if (itemsList.size() >= capacity) { auto oldest = itemsList.back(); lookupTable.erase(oldest.first); itemsList.pop_back(); } itemsList.emplace_front(key, val); lookupTable[key] = itemsList.begin(); } }; ``` ## 2. Mathematical Invariants & Algorithmic Complexity By decoupling spatial location from order traversal, our dual-structure achieves complete determinism: | Operation | Time Complexity | Auxiliary Space | Invariant Rationale | | :--- | :--- | :--- | :--- | | **Get Key** | $O(1)$ amortized | $O(1)$ | Hash lookup + list node pointer dereference | | **Put Key** | $O(1)$ amortized | $O(1)$ | Splice node to head or prepend new item | | **Evict LRU** | $O(1)$ strict | $O(1)$ | `pop_back()` frees least recently used tail | ## 3. Engineering Decisions & Architecture Trade-Offs - **Why std::list::splice instead of manual pointers?** Modern C++ standard library implementations optimize `splice` into raw pointer swaps. No heap allocations or deallocations occur when relocating an active node to the head of the queue. - **Thread-Safety & Locking Contention:** In multi-core setups, wrapping the cache in a coarse-grained `std::mutex` can cause thread starvation. For concurrent workloads, prefer striped locking or a lock-free queue with Hazard Pointers.