LRU Cache 的原理及简单实现

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();
    }
};