- LRU Cache[面试必备]
#include <bits/stdc++.h>
using namespace std;
class LRUCache {
public:
LRUCache(int capacity) { this->capacity = capacity; }
int get(int key) {
if (dir.count(key)) {
vistied(key);
return dir[key]->second;
}
return -1;
}
void put(int key, int value) {
if (dir.count(key)) {
vistied(key);
} else {
if (capacity <= dir.size()) {
dir.erase(cacheList.back().first);
cacheList.pop_back();
}
cacheList.push_front(make_pair(key, value));
dir[key] = cacheList.begin();
}
dir[key]->second = value;
}
void vistied(int key) {
auto p = *dir[key];
cacheList.erase(dir[key]);
cacheList.push_front(p);
dir[key] = cacheList.begin();
}
private:
unordered_map<int, list<pair<int, int>>::iterator> dir;
list<pair<int, int>> cacheList;
int capacity;
};
