C++ 基于双map实现LFU缓存结构

数据结构

与上一题实现LRU有些不同，设计LFU时需要从根据缓存set和get的次数来存放数据，不能单纯用链表来实现。这是因为链表只能从头尾插入数据，也不具备自我排序的功能。这个时候我们可以使用双map来实现。首先介绍两个map:

1. 用unordered_map kv存放三个对象，分别是key, value和map迭代器。具体讲，kv的键就是operators的键key，而kv的值是一个pair，pair.first指的是operators的值value；pair.second是一个map迭代器，其存储map对象中的红黑树节点的迭代器对象。
2. map ref存放三个对象，分别是ref_time(即set和get的次数)，index(可以看做是操作时间，每次执行set or get操作后+1)，以及operators的键key。ref_time和index组成一个pair<int, int>类型作为map的键，显然拥有最小ref_time和index的缓存可以通过map.begin()取出。当然为了删除最小使用次数的缓存，我们用operators的key作为map的值，方便删除kv的键值对。

那么两个map解释清楚了，很容易就能实现LFU的功能。简单讲一下核心部分：

1. 对两个map的键值对的更新我使用了一个lambda语法，set和get中都会用得到，其思想是：在kv中找出key对应的值(前提是需要判断一下这个键是否存在哦，即if(kv.count(opt[1])))，这个值是一个pair对象，pair.second是map ref的迭代器，存储了使用次数和上次使用的时间。我们把它干掉，再重新向map插入一个新的使用次数即newRef和时间index。同时kv指向更新的迭代器对象。
2. get和set的思路都很简单，在键值存在时都需要更新两个map，但get需要返回值，也就是kv[opt[1]].first，而set需要考虑缓存满的情况。缓存区满了，就需要从ref.begin()拿出最少使用的最早的那个键值，并从两个map中删除，插入新的键值对即可。

算法实现

class Solution {
public:
    /**
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        unordered_map<int, pair<int, map<pair<int, int>, int>::iterator> > kv;
        map<pair<int, int>, int> ref;
        int index = 0;
        vector<int> res;
        auto updateRef = [&index](unordered_map<int, pair<int, map<pair<int, int>, int>::iterator> >& kv
                       , map<pair<int, int>, int>& ref, vector<int>& opt)->void{
                pair<int, map<pair<int, int>, int>::iterator>& node = kv[opt[1]];   // 取出val
                map<pair<int, int>, int>::iterator itMap = node.second;            // 取出map
                int newRef = (*itMap).first.first + 1;
                ref.erase(itMap);
                auto ret = ref.insert({make_pair(newRef, index), opt[1]});
                node.second = ret.first;
        };
        for(auto& opt:operators) {
            if(opt[0] == 1) {
                //插入值
                if(kv.count(opt[1])) {
                    updateRef(kv, ref, opt);
                    kv[opt[1]].first = opt[2];
                    continue;
                }
                if(kv.size() >= k) {
                    // 处理缓存数量过多的情况，此时已经排除掉了key存在的情况
                    auto delIt = ref.begin();
                    int key = (*delIt).second; //需要取出key，在kv中一并删除
                    ref.erase(delIt);
                    kv.erase(key);
                }
                auto ret = ref.insert({make_pair(1, index), opt[1]});
                kv[opt[1]] = make_pair(opt[2], ret.first);
            } else {
                // 获取值
                if(kv.count(opt[1])) {
                    // 若存在键值，则需要对ref内索引次数进行更新
                    updateRef(kv, ref, opt);
                    res.push_back(kv[opt[1]].first);
                } else {
                    res.push_back(-1);
                }
            }
            ++index;
        }
        return res;
    }
};

复杂度分析

时间复杂度：$O(lgn)O(lgn)$，无论调用get还是set都会调整一次unordered_map和map，而map底层为红黑树，因此查询复杂度为$O(lgn)O(lgn)$级别的。

空间复杂度：$O(n)O(n)$，维护缓存的过程可以看做是增删改两个map的过程，两个map的空间复杂度可以看做是线性的。