-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path31.LRUCache.cpp
More file actions
executable file
·160 lines (142 loc) · 4.04 KB
/
31.LRUCache.cpp
File metadata and controls
executable file
·160 lines (142 loc) · 4.04 KB
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
/*
@filename 31.cpp
@author caonan
@date 2022-04-08 15:40:09
@reference 剑指offer专项
@url https://leetcode-cn.com/problems/OrIXps/
@brief 运用所掌握的数据结构，设计和实现一个 LRU (Least Recently Used，最近最少使用) 缓存机制 。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int
value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
*/
#include <assert.h>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <memory>
#include <unordered_map>
#include <vector>
using namespace std;
struct Node {
Node(int val, int key) : val(val), key(key) {}
int val;
int key;
Node *next = nullptr;
Node *pre = nullptr;
};
class LRUCache {
public:
LRUCache(int capacity) : capacity_(capacity) {
// 构造虚拟节点，否则链表操作会比较麻烦
head_ = new Node(-1, -1);
tail_ = new Node(-1, -1);
head_->next = tail_;
tail_->pre = head_;
}
~LRUCache() {
while (head_) {
auto *p = head_;
head_ = head_->next;
delete p;
p = nullptr;
}
}
int get(int key) {
if (key_to_node_.find(key) != key_to_node_.end()) {
Node *p = key_to_node_[key];
move_node_to_tail(p);
return p->val;
}
return -1;
}
void put(int key, int value) {
if (key_to_node_.find(key) != key_to_node_.end()) {
Node *p = key_to_node_[key];
p->val = value;
move_node_to_tail(p);
} else {
Node *p = new Node(value, key);
move_node_to_tail(p);
key_to_node_[key] = p;
if (key_to_node_.size() > capacity_) {
key_to_node_.erase(head_->next->key);
pop_list_front();
}
}
}
private:
void move_node_to_tail(Node *node) {
if (node->pre && node->next) {
node->pre->next = node->next;
node->next->pre = node->pre;
}
node->pre = tail_->pre;
tail_->pre->next = node;
node->next = tail_;
tail_->pre = node;
}
void pop_list_front() {
auto next = head_->next;
head_->next->next->pre = head_;
head_->next = head_->next->next;
delete next;
next = nullptr;
}
// store key and val arr index
unordered_map<int, Node *> key_to_node_;
// std::unique_ptr<Node *> head_, tail;
Node *head_, *tail_;
// store val in data
const int capacity_;
};
class LRUCacheSTL {
public:
LRUCache(int capacity) : kcapacity_(capacity) {}
int get(int key) {
if (hash_map_.find(key) == hash_map_.end()) {
return -1;
}
node_list_.splice(node_list_.end(), node_list_, hash_map_[key]);
return hash_map_[key]->second;
}
void put(int key, int value) {
if (hash_map_.find(key) != hash_map_.end()) {
hash_map_[key]->second = value;
node_list_.splice(node_list_.end(), node_list_, hash_map_[key]);
return;
}
node_list_.emplace_back(std::make_pair(key, value));
hash_map_[key] = std::prev(node_list_.end());
if (hash_map_.size() > kcapacity_) {
hash_map_.erase(node_list_.front().first);
node_list_.pop_front();
}
}
private:
std::list<pair<int, int>> node_list_;
const int kcapacity_;
std::unordered_map<int, decltype(node_list_.begin())> hash_map_;
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
// todo: 如果用智能指针实现链表？
void uinttest_lrucache(int capacity) {
LRUCache cache(capacity);
cache.put(1, 1);
assert(cache.get(2) == -1);
capacity == 0 ? assert(cache.get(1) == -1) : assert(cache.get(1) == 1);
}
int main() {
uinttest_lrucache(0);
uinttest_lrucache(1);
uinttest_lrucache(2);
uinttest_lrucache(5);
return 0;
}