← C++ roadmap

Topic 25 of 27 · Advanced

Implement an LRU cache with stable list iterators

Implement integer-key get/put with capacity-limited least-recent eviction.

AdvancedMid-level · 3–5 yearsData structures

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.

  1. Find key in map.
  2. Splice hits to front.
  3. Insert misses with rollback on map failure.
  4. 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?
Practise C++ with the AI mentor

Can't find a C++ topic you need for exams or placements? Request it and we'll add it.