aboutsummaryrefslogtreecommitdiff
path: root/lru_cache.cpp
blob: f8d1656314223608cbb7de49a55a36bbb2558303 (plain)
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
// 146. LRU Cache
#include "leetcode.h"

/*
 * design a data structure that follows the constraints of a least recently used
 * cache (LRU). implete the 'LRUCache' class. the functions 'get' and 'put' must
 * each run in O(1) average time complexity
 */

class LRUCache {
private:
  typedef list<int> li;
  typedef pair<int, li::iterator> pii;
  typedef unordered_map<int, pii> hipii;
  hipii cache;
  li used;
  int _capacity;
  void touch(hipii::iterator i) {
    int key = i->first;
    used.erase(i->second.second);
    used.push_front(key);
    i->second.second = used.begin();
  }

public:
  LRUCache(int capacity) { _capacity = capacity; }
  int get(int key) {
    auto i = cache.find(key);
    if (i == cache.end())
      return -1;
    touch(i);
    return i->second.first;
  }
  void put(int key, int value) {
    auto i = cache.find(key);
    if (i != cache.end())
      touch(i);
    else {
      if (cache.size() == _capacity) {
        cache.erase(used.back());
        used.pop_back();
      }
      used.push_front(key);
    }
    cache[key] = {value, used.begin()};
  }
};

int main() {
  LRUCache *obj = new LRUCache(2);
  obj->put(1, 1);
  obj->put(2, 2);
  printf("%d\n", obj->get(1)); // expect: 1
  obj->put(3, 3);
  printf("%d\n", obj->get(2)); // expect: -1
  obj->put(4, 4);
  printf("%d\n", obj->get(1)); // expect: -1
  printf("%d\n", obj->get(3)); // expect: 3
  printf("%d\n", obj->get(4)); // expect: 4
}