2.1.3 LRU Cache

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

/*

Maintains a least-recently-used cache with fixed capacity. The cache supports lookups and updates by
key, evicting the least recently used entry whenever an insertion would exceed capacity.

This implementation combines a doubly linked list (`std::list`) with a map from keys to list
iterators. The front of the list stores the most recently used item. The operation
`items.splice(items.begin(), items, it)` is the standard-library way to move an existing list node
to the front in O(1) time.

To implement the same cache without `std::list`, use the intrusive doubly linked list operations
from section 2.1.2. Store a `Node*` in the map instead of a list iterator, move hits to the front
with `move_to_front(&sentinel, node)`, and evict `sentinel.prev`.

- `LRUCache<Key, Value>(capacity)` constructs an empty cache holding at most `capacity` keys.
- `get(key, &value)` returns whether `key` is present. If present, it stores the value in `value`
  and marks the key as most recently used.
- `put(key, value)` inserts or updates `key`, marking it as most recently used and evicting the
  least recently used key if needed.
- `size()` returns the number of keys currently stored.

Time Complexity:
- O(1) amortized per call to `get(key, &value)` and `put(key, value)`.

Space Complexity:
- O(n), where $n$ is the cache capacity.

*/

#include <list>
#include <unordered_map>
#include <utility>

// Replacing std::list with a manual doubly-linked list would look something like:
//   struct DListNode { Key key; Value value; DListNode *prev, *next; };
//   std::unordered_map<Key, DListNode*> where;
//
// On get:
//   move_to_front(&sentinel, where[key]);
//
// On eviction:
//   DListNode *old = sentinel.prev;
//   erase(old);
//   where.erase(old->key).

template<class Key, class Value>
class LRUCache {
  using ListIter = typename std::list<std::pair<Key, Value>>::iterator;

  int cap;
  std::list<std::pair<Key, Value>> items;
  std::unordered_map<Key, ListIter> where;

 public:
  explicit LRUCache(int capacity) : cap(capacity) {}

  int size() const { return static_cast<int>(items.size()); }

  bool get(const Key &key, Value *value) {
    auto it = where.find(key);
    if (it == where.end()) {
      return false;
    }
    items.splice(items.begin(), items, it->second);
    it->second = items.begin();
    *value = it->second->second;
    return true;
  }

  void put(const Key &key, const Value &value) {
    auto it = where.find(key);
    if (it != where.end()) {
      it->second->second = value;
      items.splice(items.begin(), items, it->second);
      it->second = items.begin();
      return;
    }
    if (cap == 0) {
      return;
    }
    if (static_cast<int>(items.size()) == cap) {
      where.erase(items.back().first);
      items.pop_back();
    }
    items.push_front({key, value});
    where[key] = items.begin();
  }
};

/*** Example Usage ***/

#include <cassert>
using namespace std;

int main() {
  LRUCache<int, int> cache(2);
  int value = 0;
  cache.put(1, 10);
  cache.put(2, 20);
  assert(cache.get(1, &value) && value == 10);
  cache.put(3, 30);  // Evicts key 2.
  assert(!cache.get(2, &value));
  assert(cache.get(3, &value) && value == 30);
  cache.put(1, 11);
  assert(cache.get(1, &value) && value == 11);
  return 0;
}