LRU Cache 说的是一种数据结构，对于类型参数 KeyT, ValT, 它至少支持：
void put(KeyT k, ValT v); // 存Maybe<ValT> get(KeyT k); // 取两种操作。
更详细地描述这个 LRUCache 支持的方法是这样：
template <typename KeyT, typename ValT>
class LRUCache {
public:
// 向 LRUCache 中存入一个 (key,val) 键值对，
// 使得后续可以通过 get(key) 把这个 val 快速地取出来（前提是 key 是仍然 valid）
// 前后两次 put(key, val1), put(key, val2),
// 不管中间间隔了什么，都会使得前面那个 val1 被覆盖，后续的 get(key) 操作得到的是 val2,
// 也就是说，相同的 key 不允许重复出现，一旦重复出现了，旧的 key 对应的 val 就会被覆盖。
void put(KeyT key, ValT val);
// 在 LRUCache 中查询是否有一个 (key, x) 这样对键值对，如果有，不管 x 是什么，返回 x,
// 如果没有这样的键值对，返回一个空的 std::shared_ptr<ValT>.
std::shared_ptr<ValT> get(const KeyT &key);
};
因为对于 put 方法，传入的 key 需要被保存在内部的 HashMap 中，所以我们没有用引用，以此强调这个 KeyT 类型的 key 对象本身至少会被复制一次，复制到内部的 HashMap 中作为 key.
LRU Cache 中的 LRU 是一种缓存失效策略。
什么是缓存失效策略呢？当缓存空间占满了，而且又立刻需要缓存空间来存放从未见过的键值对的时候，一个 Cache 的实现就需要自己判断该使现有的哪一个键失效（从而把空间让出来），至于它是如何判断该选哪个的，就是缓存失效策略。
LRU 大概是这样的一个策略：当有需要的时候（当不得不的时候），我就使「最久没有被访问过」的键值对失效。你可以把它理解为键值对缓存的末位淘汰策略。
举个例子，假设我们有一个 capacity 为 3 的 LRU Cache 实例：
constexpr size_t lruCacheCapacity = 3;
LRUCache lruCache (lruCacheCapacity);
我们先做 3 次 put 操作：
lruCache.put(1, 1);
lruCache.put(2, 2);
lruCache.put(3, 3);
现在，最久没有被碰过的 key 是 1, LRU Key 是 1.
而假如说我们这个时候再做一次 get 操作呢？
lruCache.get(1); // 返回 1, 因为之前 put 入了 (1, 1) 并且没有失效
这时 LRU Key 是 2, 因为按照 put 的顺序，1 是最久没有被访问的，其次是 2, 其次是 3, 现在 1 被访问了，这个最久没有被访问的 key 就顺延到了 2, 你可以想象逻辑上这里存在一个「队列」，不过我们不一定用队列实现 LRU Cache.
这时，如果我们再 put 一个新的 key, 并且 put 之后再去 get 2, 就会发现 2 已经失效了：