LRU（ Least Recently Used） 是一种淘汰策略的缩写，意思是最近最少使用，它是一种 Cache 替换算法。
什么是 Cache ？狭义的 Cache 指的是位于 CPU 和主存间的快速 RAM， 通常它不像系统主存那样使用 DRAM 技术，而使用昂贵但较快速的 SRAM 技术。 广义上的 Cache 指的是位于速度相差较大的两种硬件之间， 用于协调两者数据传输速度差异的结构。除了 CPU 与主存之间有 Cache， 内存与硬盘之间也有 Cache，乃至在硬盘与网络之间也有某种意义上的 Cache ── 称为 Internet 临时文件夹或网络内容缓存等。
Cache 的容量有限，因此当 Cache 的容量用完后，而又有新的内容需要添加进来时， 就需要挑选并舍弃原有的部分内容，从而腾出空间来放新内容。 LRU Cache 的替换原则就是将最近最少使用的内容替换掉。其实，LRU 译成最久未使用会更形象， 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。
Ⅱ. LRU Cache 的实现
实现 LRU Cache 的方法和思路很多，但是要保持高效实现 O(1) 的 put 和 get，那么使用双向链表和哈希表的搭配是最高效和经典的。使用双向链表是因为双向链表可以实现任意位置 O(1) 的插入和删除，使用 哈希表可以实现 O(1) 的查找。
这分别对应到 stl 中的 list 和 unordered_map ，其中要注意的是，为了能达到 O(1) 的效果，我们在 unordered_map 中存放的 value 值是 list 的迭代器 list<int, int>::iterator ，这样子就能快速找到链表中每个节点。
146. LRU 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。实现 LRUCache 类：
-
LRUCache(int capacity)以 正整数 作为容量capacity初始化LRU缓存 -
int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。 -
void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。 -
函数
get和put必须以O(1)的平均时间复杂度运行。
示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4提示：
1 <= capacity <= 3000 0 <= key <= 10000 0 <= value <= 105
代码实现：
class LRUCache {
public:
LRUCache(int capacity)
:_capacity(capacity)
{}
int get(int key)
{
auto it = _hashMap.find(key);
if(it == _hashMap.end())
{
return -1;
}
else
{
// 存在的话，先要将其更新到链表的首位，有两种方法
// 1、使用 push_front + erase 但是容易迭代器失效问题
// 2、使用 splice 函数进行转移
// 这里采用第二种方法
_LRUList.splice(_LRUList.begin(), _LRUList, it->second);
return it->second->second;
}
}
void put(int key, int value)
{
auto it = _hashMap.find(key);
if(it == _hashMap.end())
{
// 找不到说明要新增
// 需要判断一下是否需要逐出LRU
if(_capacity == _hashMap.size())
{
// 删掉LRU
_hashMap.erase(_LRUList.back().first);
_LRUList.pop_back();
}
// 插入新增元素，记得哈希表也要存
_LRUList.push_front(make_pair(key, value));
_hashMap.insert(make_pair(key, _LRUList.begin()));
}
else
{
// 找到的话则更新到链表头并修改value即可
it->second->second = value;
_LRUList.splice(_LRUList.begin(), _LRUList, it->second);
}
}
private:
// 容量是为了判断是否已经满了
size_t _capacity;
// 哈希表为查找、更新时提供O(1)的时间复杂度
typedef list<pair<int, int>>::iterator LTiter;
unordered_map<int, LTiter> _hashMap;
// 双向链表提供O(1)的插入
list<pair<int, int>> _LRUList;
};
