LRU（Least Recently Used）是一种缓存淘汰算法，当未命中时，将最近最少使用（即上一次使用的时间离现在最久）的块置换出去来加载新块。
例如，以下块的访问顺序为 A B C D E D F：
一旦 A B C D 被放置在缓存中（每个新访问增量为 1），而后又访问 E 没有命中，需要将其替换进其中一个块中。根据 LRU 算法，由于 A 具有最低的时间记录 A(0)，E 将取代 A。
算法需要跟踪何时最近一次使用了各个块，这个代价是昂贵的。实际上只要维持被访问的顺序就可以了，而不必知道确切的时间记录。我们可以用 STL 中的双向链表来实现这样一个功能。
题目参考 Leetcode 146。
实现 get 和 put 两种方法，其中：
-
get(key)返回 key 对应的 value（保证大于 0），如果没有则返回 -1。 -
put(key, value)无返回值，若命中，将其 value 置为新值；若未命中，但 capacity 大于当前已存块数，直接插入；若未命中且数量已达 capacity，执行 LRU 算法进行替换。
借助 list 来记录块的使用情况，每一个新加入或命中的块都被放到头部，未命中时被替换掉的一定是位于尾部的节点。用一个 unordered_map 来存储 key 对应的 value 和在 list 中的位置（因为对 list 迭代器的删除操作不会导致其他迭代器失效），每次操作后都需要更新存储的 list 迭代器。
代码如下，具体细节参照注释：
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int value_1 = obj.get(key);
* obj.put(key,value);
*/
class LRUCache {
public:
LRUCache(int capacity) {
cap = capacity;
cache.reserve(cap); // 预留 capacity 大小的空间
}
int get(int key) {
auto iter = cache.find(key);
if(iter != cache.end()) { // 若命中
touch(iter); // 更新节点记录
return iter->second.first; // 返回 value 值
}
return -1; // 未获取到返回 -1
}
void put(int key, int value) {
auto iter = cache.find(key);
if(iter == cache.end()) { // 未命中
if(cache.size() == cap) { // cache 已满
cache.erase(data.back()); // 从 cache 中删除位于 list 末尾的 key
data.pop_back(); // 从 data 中弹出位于 list 末尾的 key
}
data.push_front(key); // cache 无论满不满都需要，从头部加入新的 key，更新时间顺序记录
}
else { // 命中
touch(iter); // 更新节点记录
}
cache[key] = {value, data.begin()}; // 未命中时置新块，命中时置新值
}
private:
list<int> data;
unordered_map<int, pair<int, list<int>::iterator>> cache;
int cap;
/*
命中时，将块在 list 中原来的节点删除，重新插入到头部。
unordered_map 中存储的迭代器也需要修改。
*/
void touch(unordered_map<int, pair<int, list<int>::iterator>>::iterator it) {
int k = it->first;
data.erase(it->second.second);
data.push_front(k);
it->second.second = data.begin();
}
};
