指上半生了了
人间万事茫茫。
C++，LRU页面置换算法实现。使用数据结构：std::list+std::unordered_map+std::pair。
这道题最重要的就是要想到用链表了，没想到的话就做不出来了。
因为只有链表才能做到插入/删除时间复杂度为O(1)，而std::unordered_map可以做到查询O(1)，自然能达到题目中的要求。
了解下面两个问题就清楚了：
-
这里面什么地方要用到“插入/删除时间复杂度为O(1)”呢？页表。
-
什么地方要用到“查询O(1)”呢？查询key在页表中的位置时。
因为题目的难点在于，怎么样能找到最近最久（最近最少）访问的key。
基于上面说到的两个问题和两种数据结构，就可以实现“每访问一次键值，就把这个键值插入到链表（页表）头”。这样，页表尾就是“最近最久（最近最少）访问的key”了，每次页表超容量的时候，就删除链表尾部的元素。
基于上述理解，就能写出代码了。
class LRUCache {
public:
LRUCache(int capacity) : capacity_(capacity) {}
int get(int key) {
if (hash_.find(key) == hash_.end())
return -1;
else {
int value = hash_[key]->second;
ls_.erase(hash_[key]);
ls_.push_front(make_pair(key, value));
hash_[key] = ls_.begin();
return value;
}
}
void put(int key, int value) {
if (hash_.find(key) != hash_.end())
ls_.erase(hash_[key]);
else if (ls_.size() >= capacity_) {
hash_.erase(ls_.back().first);
ls_.pop_back();
}
ls_.push_front(make_pair(key, value));
hash_[key] = ls_.begin();
}
private:
int capacity_;
list<pair<int, int>> ls_;
unordered_map<int, list<pair<int, int>>::iterator> hash_;
};
/**
* 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);
*/
