class LRUCache {
private:
map<int,pair<int,int>> m;
int capacity;
int refresh(){
int key=0;
int times=0;
for(auto &e:m){
++e.second.second;
if(e.second.second>times){
times = e.second.second;
key = e.first;
}
}
return key;
}
public:
LRUCache(int capacity) {
this->capacity = capacity;
}
int get(int key) {
auto it = m.find(key);
if(it==m.end()) return -1;
it->second.second = 0;
refresh();
return it->second.first;
}
void put(int key, int value) {
m[key]=pair<int,int>(value,0);
auto k = refresh();
if(m.size()>capacity){
m.erase(k);
}
}
};
可以通过维护一个链表，把读写操作的时间复杂度降低到O(1)。这个算法在实现的时候，出现了野指针，通过修改编译参数，可以返回更多报错信息。
g++ -O -g -fsanitize=address main.cpp
class LRUCache {
typedef list<pair<int, int>> lru_list_t;
typedef unordered_map<int, lru_list_t::iterator> lru_map_t;
private:
lru_list_t lru_list;
lru_map_t lru_map;
int lru_capacity;
public:
LRUCache(int capacity) { lru_capacity = capacity; }
int get(int key) {
lru_map_t::iterator lru_map_it = lru_map.find(key);
if (lru_map_it == lru_map.end()) return -1;
pair<int, int> lru_element = *(lru_map_it->second);
lru_list.erase(lru_map_it->second);
lru_list.push_front(move(lru_element));
lru_map[key] = lru_list.begin();
return lru_element.second;
}
void put(int key, int value) {
lru_map_t::iterator lru_map_it = lru_map.find(key);
if (lru_map_it != lru_map.end()) {
lru_list.erase(lru_map_it->second);
}
pair<int, int> lru_element(key, value);
lru_list.push_front(move(lru_element));
lru_map[key] = lru_list.begin();
if (lru_list.size() > lru_capacity) {
lru_map.erase(lru_list.back().first);
lru_list.pop_back();
}
}
};