Topic 25 of 27 · Advanced
Implement an LRU cache with stable list iterators
Implement integer-key get/put with capacity-limited least-recent eviction.
C++20; compile with g++ -std=c++20.
Problem statement
Implement integer-key get/put with capacity-limited least-recent eviction.
Cache bounded results with O(1) expected recency updates.
Input: Nonnegative size_t capacity; integer operations.
Output: optional<int> for get.
- Single-threaded.
- No TTL.
- Exceptions during map insertion roll back the new list node.
Sample 1
Input: cap2 put1 put2 get1 put3 get2 Output: no value
Key2 was least recently accessed.
Sample 2
Input: cap0 put1 get1 Output: no value
Zero capacity retains nothing.
Brute-force solution
Store entries in a vector and scan/move them for each access.
O(1) expected operations; hash worst case O(capacity).
#include <list>
#include <unordered_map>
#include <optional>
#include <iostream>
#include <cassert>
class LRU{std::size_t capacity;std::list<std::pair<int,int>> order;std::unordered_map<int,decltype(order.begin())> index;public:explicit LRU(std::size_t c):capacity(c){}
std::optional<int> get(int k){auto p=index.find(k);if(p==index.end())return {};order.splice(order.begin(),order,p->second);return p->second->second;}
void put(int k,int v){auto p=index.find(k);if(p!=index.end()){p->second->second=v;order.splice(order.begin(),order,p->second);return;}if(capacity==0)return;order.emplace_front(k,v);try{index.emplace(k,order.begin());}catch(...){order.pop_front();throw;}if(order.size()>capacity){index.erase(order.back().first);order.pop_back();}}};
int main() {
LRU c(2);c.put(1,10);c.put(2,20);assert(c.get(1)==10);c.put(3,30);assert(!c.get(2));LRU z(0);z.put(1,1);assert(!z.get(1));std::cout<<*c.get(1)<<"\n";
return 0;
}
Optimized solution
A list preserves iterators through splice and a hash map finds the list node.
- Find key in map.
- Splice hits to front.
- Insert misses with rollback on map failure.
- Evict the last entry after over-capacity insertion.
#include <list>
#include <unordered_map>
#include <optional>
#include <iostream>
#include <cassert>
class LRU{std::size_t capacity;std::list<std::pair<int,int>> order;std::unordered_map<int,decltype(order.begin())> index;public:explicit LRU(std::size_t c):capacity(c){}
std::optional<int> get(int k){auto p=index.find(k);if(p==index.end())return {};order.splice(order.begin(),order,p->second);return p->second->second;}
void put(int k,int v){auto p=index.find(k);if(p!=index.end()){p->second->second=v;order.splice(order.begin(),order,p->second);return;}if(capacity==0)return;order.emplace_front(k,v);try{index.emplace(k,order.begin());}catch(...){order.pop_front();throw;}if(order.size()>capacity){index.erase(order.back().first);order.pop_back();}}};
int main() {
LRU c(2);c.put(1,10);c.put(2,20);assert(c.get(1)==10);c.put(3,30);assert(!c.get(2));LRU z(0);z.put(1,1);assert(!z.get(1));std::cout<<*c.get(1)<<"\n";
return 0;
}
Complexity analysis
Time: O(1) expected operations; hash worst case O(capacity).
Auxiliary space: O(capacity)
Test cases
- Zero capacity.
- Overwrite.
- Missing get.
Supplied main asserts promotion, eviction and zero-capacity behavior.Common mistakes
- Erasing an entry without removing its map iterator.
- Leaving a list node behind if map insertion throws.
Key takeaways
- Keep map/list invariants aligned.
- Use stable iterators.
- Model exception rollback.
Follow-up challenges
- How would thread safety change the design?
- How would you implement TTL eviction?