1#include <iostream>
2#include <unordered_map>
3#include <list>
4#include <optional>
5#include <string>
6
7template <typename Key, typename Value>
8class LRUCache {
9private:
10 std::size_t m_capacity;
11 // List stores pairs of (Key, Value); Most recent at front, oldest at back
12 std::list<std::pair<Key, Value>> m_itemsList;
13 // Map maps Key -> Iterator in m_itemsList
14 std::unordered_map<Key, typename std::list<std::pair<Key, Value>>::iterator> m_cacheMap;
15
16public:
17 explicit LRUCache(std::size_t capacity) : m_capacity(capacity) {}
18
19 std::optional<Value> get(const Key& key) {
20 auto it = m_cacheMap.find(key);
21 if (it == m_cacheMap.end()) {
22 return std::nullopt; // Cache Miss
23 }
24
25 // Cache Hit: Move item to the front of list (Most Recently Used)
26 m_itemsList.splice(m_itemsList.begin(), m_itemsList, it->second);
27 return it->second->second;
28 }
29
30 void put(const Key& key, const Value& value) {
31 auto it = m_cacheMap.find(key);
32
33 if (it != m_cacheMap.end()) {
34 // Key exists: update value and move to front
35 it->second->second = value;
36 m_itemsList.splice(m_itemsList.begin(), m_itemsList, it->second);
37 return;
38 }
39
40 // Evict oldest if capacity full
41 if (m_itemsList.size() >= m_capacity) {
42 auto oldest = m_itemsList.back();
43 m_cacheMap.erase(oldest.first);
44 m_itemsList.pop_back();
45 std::cout << "[EVICT]: Removed oldest key: " << oldest.first << "\n";
46 }
47
48 // Insert new element at front
49 m_itemsList.emplace_front(key, value);
50 m_cacheMap[key] = m_itemsList.begin();
51 }
52};
53
54int main() {
55 LRUCache<int, std::string> cache(3); // Capacity = 3
56
57 cache.put(1, "Course: C++ Beginner");
58 cache.put(2, "Course: C++ Intermediate");
59 cache.put(3, "Course: C++ Advanced");
60
61 // Access key 1 to make it most recent:
62 cache.get(1);
63
64 // Insert key 4 -> Key 2 (least recently used) should be evicted:
65 cache.put(4, "Course: C++ Mastery Combo");
66
67 auto check2 = cache.get(2);
68 std::cout << "Key 2 in cache: " << (check2.has_value() ? "YES" : "NO (Evicted)") << "\n";
69
70 auto check1 = cache.get(1);
71 std::cout << "Key 1 in cache: " << (check1.has_value() ? check1.value() : "NO") << "\n";
72
73 return 0;
74}