-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution460.cpp
More file actions
89 lines (84 loc) · 2.75 KB
/
Solution460.cpp
File metadata and controls
89 lines (84 loc) · 2.75 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
//
// Solution460.cpp
// Algorithm
//
// Created by Pancf on 2020/12/13.
// Copyright © 2020 Pancf. All rights reserved.
//
#include "Solution460.hpp"
// access count plus 1 and update access time for item
void LFUCache::reorderList(Item &itemRef)
{
auto freqIt = itemRef.freqIt;
auto timeIt = itemRef.timeIt;
if (freqIt != freqList.begin()) { // 非表头
auto prev = freqIt;
prev--;
if (prev->first == (freqIt->first + 1)) { //追加在prev的表头
prev->second.splice(prev->second.begin(), freqIt->second, timeIt);
itemRef.freqIt = prev;
itemRef.timeIt = prev->second.begin();
if (freqIt->second.size() == 0) {
freqList.erase(freqIt);
}
} else {
if (freqIt->second.size() == 1) { //同freq的只有这个key-val
freqIt->first++;
} else {
auto newIt = freqList.emplace(freqIt, std::pair<int, std::list<int>>(freqIt->first + 1, {}));
newIt->second.splice(newIt->second.begin(), freqIt->second, timeIt);
itemRef.freqIt = newIt;
itemRef.timeIt = newIt->second.begin();
}
}
} else { //表头
if (freqList.front().second.size() == 1) { //同freq的只有这个key-val
freqList.front().first++;
} else {
auto freq = freqList.front().first;
std::list<int> tmp;
tmp.splice(tmp.begin(), freqList.front().second, timeIt);
freqList.emplace_front(std::pair<int, std::list<int>>(freq+1,tmp));
itemRef.freqIt = freqList.begin();
itemRef.timeIt = freqList.front().second.begin();
}
}
}
int LFUCache::get(int key)
{
auto it = mp.find(key);
if (it != mp.end()) {
auto val = it->second.val;
reorderList(it->second);
return val;
}
return -1;
}
void LFUCache::put(int key, int value)
{
if (capacity == 0) return;
auto it = mp.find(key);
if (it != mp.end()) { // find key
it->second.val = value;
reorderList(it->second);
} else {
auto *onceList = &(freqList.back().second);
if (mp.size() == capacity) { // erase
if (onceList->size() > 0) {
mp.erase(onceList->back());
onceList->pop_back();
}
}
if (freqList.back().first != 1) { // insert once list
freqList.emplace_back(std::pair<int, std::list<int>>(1, {}));
onceList = &(freqList.back().second);
}
onceList->emplace_front(key);
Item item;
item.val = value;
item.freqIt = freqList.end();
item.freqIt--;
item.timeIt = onceList->begin();
mp[key] = item;
}
}