Step 5 of 5

Challenge: an LRU cache

A least-recently-used (LRU) cache keeps the capacity most recently used items and evicts the stalest one when full. It sits in front of databases, file systems and web servers everywhere, and it's one of the most common interview questions because it combines two data structures, each covering the other's weakness:

• a std::list of (key, value) pairs ordered by recency (front = most recent). Moving an element or removing the back is O(1), but finding a key would be O(n).
• a std::unordered_map from key to the list iterator, which finds any element in O(1).

The key tool is list.splice(list.begin(), list, it): it moves the element at it to the front in O(1), without invalidating any iterators, so the map stays correct.

#include <iostream>
#include <list>
#include <string>

int main() {
    std::list<std::string> recent = {"a.txt", "b.txt", "c.txt"};   // front = most recent
    auto it = std::next(recent.begin(), 2);                        // points at c.txt

    recent.splice(recent.begin(), recent, it);                     // c.txt used again
    for (const auto& f : recent) std::cout << f << " ";
    std::cout << "| still valid: " << *it << "\n";

    recent.push_front("d.txt");                                    // a new file opened
    if (recent.size() > 3) {
        std::cout << "evict " << recent.back() << "\n";            // least recent
        recent.pop_back();
    }
    for (const auto& f : recent) std::cout << f << " ";
    std::cout << "\n";
}

c.txt a.txt b.txt | still valid: c.txt
evict b.txt
d.txt c.txt a.txt 

Putting it together

• get(key): look it up in the map. Missing: return std::nullopt. Found: splice its list node to the front (it's now the most recent), and return the value.
• put(key, value): if the key exists, update the value in its node and splice it to the front. Otherwise push_front a new pair, store items_.begin() in the map, and if the size is now over capacity, erase the back key from the map first (read items_.back().first), then pop_back().

The order in that eviction matters: after pop_back(), the key you needed to erase from the map is gone.

Your turn: write LruCache with std::optional<int> get(int key) (a hit makes the key most recent) and void put(int key, int value) (insert or update, making it most recent; evict the least recent if over capacity). Both O(1).

Previous: Hashing your own keys