LFU Cache LeetCode solution in C++

1
class list_node {
2
 public:
3
  int key, val, cnt;
4
  list_node *next;
5
  list_node *prev;
6
  list_node(int k, int v, list_node *n, list_node *p) {
7
    key = k;
8
    val = v;
9
    cnt = 1;
10
    next = n;
11
    prev = p;
12
  }
13
};
14
class LFUCache {
15
 public:
16
  int min_cnt;
17
  bool zero;
18
  unordered_map<int, list_node *> key2node;
19
  unordered_map<int, pair<list_node *, list_node *>> cnt2list;
20
  LFUCache(int capacity) {
21
    cin.tie(0);
22
    ios_base::sync_with_stdio(0);
23
    min_cnt = 0;
24
    c = capacity;
25
    zero = (c == 0);
26
  }
27

28
  int get(int key) {
29
    if (zero) return -1;
30
    auto it = key2node.find(key);
31
    if (it == key2node.end() || it->second == NULL) return -1;
32
    addcnt(key);
33
    return it->second->val;
34
  }
35

36
  void put(int key, int value) {
37
    if (zero) return;
38
    auto it = key2node.find(key);
39
    if (it != key2node.end() && it->second != NULL) {
40
      addcnt(key);
41
      it->second->val = value;
42
      return;
43
    }
44
    if (c)
45
      --c;
46
    else {
47
      key2node[cnt2list[min_cnt].first->key] = NULL;
48
      list_node *tmp = cnt2list[min_cnt].first;
49
      if (tmp->next) tmp->next->prev = NULL;
50
      cnt2list[min_cnt].first = tmp->next;
51
      if (cnt2list[min_cnt].second == tmp) cnt2list[min_cnt].second = NULL;
52
    }
53

54
    min_cnt = 1;
55
    list_node *node = new list_node(key, value, NULL, NULL);
56
    key2node[key] = node;
57
    if (cnt2list.find(1) == cnt2list.end() || cnt2list[1].first == NULL) {
58
      cnt2list[1].first = cnt2list[1].second = node;
59
    } else {
60
      node->prev = cnt2list[1].second;
61
      cnt2list[1].second->next = node;
62
      cnt2list[1].second = node;
63
    }
64
  }
65

66
 private:
67
  int c;
68
  void addcnt(int key) {
69
    if (cnt2list[key2node[key]->cnt].first == key2node[key])
70
      cnt2list[key2node[key]->cnt].first = key2node[key]->next;
71
    if (cnt2list[key2node[key]->cnt].second == key2node[key])
72
      cnt2list[key2node[key]->cnt].second = key2node[key]->prev;
73
    if (min_cnt == key2node[key]->cnt && cnt2list[key2node[key]->cnt].first == NULL) min_cnt++;
74
    key2node[key]->cnt++;
75
    if (key2node[key]->prev) key2node[key]->prev->next = key2node[key]->next;
76
    if (key2node[key]->next) key2node[key]->next->prev = key2node[key]->prev;
77
    key2node[key]->next = NULL;
78
    auto lit = cnt2list.find(key2node[key]->cnt);
79
    if (lit == cnt2list.end() || lit->second.first == NULL) {
80
      cnt2list[key2node[key]->cnt].first = cnt2list[key2node[key]->cnt].second = key2node[key];
81
      key2node[key]->prev = NULL;
82
    } else {
83
      key2node[key]->prev = cnt2list[key2node[key]->cnt].second;
84
      cnt2list[key2node[key]->cnt].second->next = key2node[key];
85
      cnt2list[key2node[key]->cnt].second = key2node[key];
86
    }
87
  }
88
};