-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path146.-LRU-Cache.cpp
More file actions
152 lines (134 loc) · 3.72 KB
/
Copy path146.-LRU-Cache.cpp
File metadata and controls
152 lines (134 loc) · 3.72 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
// 参考http://stackoverflow.com/questions/13337854/understanding-lru-algorithm
// version 2: dlinklist + hash map
// 这里age可以不要了，因为永远都是最新的在tail，最旧的在head处
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <unordered_map>
using namespace std;
// version 2: dlinklist + hash map
class LRUCache{
public:
LRUCache(int capacity) {
cap = capacity;
size = 0;
age = 0;
head = new DLNode(0,0,0,nullptr,nullptr);
tail = head;
map = new unordered_map<int, DLNode*>();
}
int get(int key) {
if(size==0) return -1;
age++;
if((*map).find(key)!=(*map).end()){
DLNode * target = (*map)[key];
if(target==tail){
target->age = age;
return (*map)[key]->val;
}
DLNode * tmp = target->next;
target->pre->next = tmp;
tmp->pre = target->pre;
tail->next = new DLNode(key,(*map)[key]->val, age, tail, nullptr);
tail = tail->next;
(*map)[key] = tail;
delete target;
return (*map)[key]->val;
}
return -1;
}
void set(int key, int value) {
age++;//updateAge();
if(size==0){
head->next = new DLNode(key, value, age, head,nullptr);
size++;
tail = head->next;
(*map).insert(make_pair(key, tail));
return;
}
DLNode * tobeDelete = nullptr;
if((*map).find(key)!=(*map).end()){
DLNode * target = (*map)[key];
if(target==tail){
tail->val = value;
tail->age = age;
return;
}
tobeDelete = target;
} else{ // cache miss
if(size>=cap) {
tobeDelete = head->next;
} else
size++;
}
if(tobeDelete!=nullptr){
DLNode * tmp = tobeDelete->next;
tobeDelete->pre->next = tmp;
if(tmp) // Runtime Error 1,[set(2,1),get(2),set(3,2),get(2),get(3)]
tmp->pre = tobeDelete->pre;
(*map).erase(tobeDelete->key);
delete tobeDelete;
}
tail->next = new DLNode(key,value, age, tail, nullptr);
tail = tail->next;
(*map)[key] = tail;
return;
}
private:
struct DLNode{
int key;
int val;
long age;
DLNode * pre=nullptr;
DLNode * next=nullptr;
DLNode(int k, int v, long a, DLNode* p, DLNode* n):key(k),val(v),age(a),pre(p),next(n){
}
};
int size;
int cap;
long age; // may overflow
DLNode * head;
DLNode * tail;
unordered_map<int, DLNode*>* map;
// 有可能超过最大时变为负，然后另外的还为正
void updateAge(){
if(age<LONG_MAX){
age++;
return;
} else {
DLNode * p = tail;
long minage = 0;
while(p!=head){
if(p->age<minage)
minage = p->age;
p = p->pre;
}
p = tail;
while(p!=head){
p->age-=minage;
}
}
}
};
int main()
{
LRUCache lru(4);
cout<<lru.get(1)<<endl;
lru.set(1,18);
cout<<lru.get(1)<<endl;
lru.set(2,28);
lru.set(3,38);
lru.set(4,48);
cout<<lru.get(1)<<endl;
cout<<lru.get(2)<<endl;
cout<<lru.get(3)<<endl;
cout<<lru.get(4)<<endl;
cout<<lru.get(0)<<endl;
lru.set(5,58);
cout<<lru.get(1)<<endl;
cout<<lru.get(2)<<endl;
cout<<lru.get(3)<<endl;
cout<<lru.get(4)<<endl;
cout<<lru.get(5)<<endl;
}