题解 | #设计LRU缓存结构#

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        // 使用list来维护LRU缓存
        // 使用哈希表提高查询速度
        list<pair<int, int>> lru_list;
        unordered_map<int, list<pair<int, int>>::iterator> mil; // 直接存储list的迭代器，减少list的查询
        vector<int> res;
        
        // 使用新特性auto
        for (auto op : operators) {
            // set or get
            switch(op[0]) {
                // set
                case 1: {
                    // 插入一个值，这个值可能出现过也可能没有出现过
                    auto it = mil.find(op[1]);
                    if (it != mil.end()) { // 已经在缓存中
                        // 删除list中原来的节点，插入新节点到最前面
                        lru_list.erase(it->second);
                        // 再set新值在最前面
                        lru_list.push_front(make_pair(op[1], op[2]));
                        // 更改map为对应的list节点
                        it->second = lru_list.begin();
                    } else { // 没有在缓存中
                        // 缓存以满，需要先删除最后的节点
                        if (lru_list.size() == k) {
                            // map也要删除
                            mil.erase(lru_list.back().first);
                            lru_list.pop_back();
                        }
                        // 新节点加入
                        lru_list.push_front(make_pair(op[1], op[2]));
                        mil.insert({op[1], lru_list.begin()});
                    }
                } break;
                // get
                case 2: {
                    auto it = mil.find(op[1]);
                    if (it != mil.end()) {
                        // 在缓存中,查找结果加入res中
                        int num = it->second->second;
                        res.push_back(num);
                        // 更新缓存位置
                        lru_list.erase(it->second);
                        lru_list.push_front(make_pair(op[1], num));
                        // 更新map
                        it->second = lru_list.begin();
                    } else {
                        res.push_back(-1);
                    }
                } break;
            }
        }
        return res;
        
    }
};