高阶数据结构学习——LRU Cache

1、了解LRU Cache（Least Recently Used缩写）

Cache是缓存，在磁盘和内存之间，内存和寄存器之间都存在，CPU和内存之间存在三级缓存，是一个三层结构。缓存用于两个速度不一致的硬件之间，提高效率用。缓存空间有限，满了以后，新数据要进入，旧数据应当怎么办？操作系统中有个热数据概念，意思是经常被使用的数据，可能放进缓存就被拿出来，再次放进后又被拿出来使用，对应的，也有很少被使用的，也就是LRU的意思，缓存满了后，新数据进来，这些很少被使用的就出去。

设计一个LRU Cache不难，设计一个高效的，任意操作都是O(1)的LRU Cache不简单，但只有这样才能满足要求。LRU Cache最主要的操作是get和put，这两个接口必须以O(1)的时间复杂度进行。

2、代码实现

看一个题

146. LRU 缓存

看在不在，可以看地址是否在缓存中。整个操作有查找，更新，新增。虽然可以用unordered_map作为缓存，做到查找，更新都O(1)，但如何找到LRU？这涉及到顺序问题，还有时间问题，这里的解决办法就是用vector或list来控制LRU，比如list，在这个list里，让处于尾部就是最久未被使用的，用一个数据就把它提到头部，list<pair<int, int>> _LRUList。但这两个结合还是做不到O(1)。因为更新时无法做到O(1)，更新时可以直接修改map里的数据，但在list中更新时需要先找到这个数据再放到头部，所以不是O(1)。

以上问题的解决办法是找到key时，就同时找到key对应存储数据在list中的位置。把map中value的类型换成list的迭代器，这样map[key]中存的就是一个指针，指向list中的对应的元素，如果要使用这个数据时就用指针把它拿出来，然后头插即可。

private:typedef list<pair<int, int>>::iterator LtIter;unordered_map<int, LtIter> _hashMap;list<pair<int, int>> _LRUList;

class LRUCache {
public:LRUCache(int capacity) :_capacity(capacity){}int get(int key) {auto ret = _hashMap.find(key);if(ret != _hashMap.end()){//更新key对应值的位置LtIter it = ret->second;//方案1: erase + push_front 更新迭代器，原迭代器失效//方案2: list的splice接口可以转移节点_LRUList.splice(_LRUList.begin(), _LRUList, it);return ret->second->second;//第一个second对应迭代器，第二个second对应list的pair}else{return -1;}}void put(int key, int value) {//1、新增//2、更新auto ret = _hashMap.find(key);if(ret == _hashMap.end())//新增{if(_capacity == _hashMap.size()){pair<int, int> back = _LRUList.back();_hashMap.erase(back.first);_LRUList.pop_back();  }_LRUList.push_front(make_pair(key, value));_hashMap[key] = _LRUList.begin();}else//更新{LtIter it = ret->second;it->second = value;_LRUList.splice(_LRUList.begin(), _LRUList, it);}}
private:typedef list<pair<int, int>>::iterator LtIter;unordered_map<int, LtIter> _hashMap;list<pair<int, int>> _LRUList;size_t _capacity;
};

结束。