设计LRU缓存结构

解题思路

• 键值对的查询，首选 map。又因为本题中 map 只是用来查询，不涉及排序，所以采用 unordered_map
• 维护最近使用的元素，这涉及了出队和入队的概念，但因为 queue 只能操作头部和尾部的元素，所以不适用于本题。而 list 既满足了对头/尾元素的操作，也可以对中间元素进行删除操作，所以选用 list。
• list 中只需要维护 map 中的键值就足够了，不需要维护 pair<key, value>

代码

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) {
        if (operators.empty())
            return vector<int>();

        vector<int> ret;
        for (auto& o : operators) {
            if (o[0] == 1)
                set(o[1], o[2], k);
            else if (o[0] == 2)
                get(o[1], ret);
        }
        return ret;
    }

private:
    unordered_map<int, int> map;
    list<int> keys;

    void set(int key, int value, int k) {
        if (keys.size() == k) {
            int delKey = keys.back();
            keys.pop_back();
            map.erase(delKey);
        }
        map[key] = value;
        keys.push_front(key);
    }

    void get(int key, vector<int>& ret) {
        auto found = map.find(key);
        if (found == map.end()) {
            ret.push_back(-1);
        } else {
            ret.push_back(found->second);
            keys.remove(found->first);
            keys.push_front(found->first);
        }
    }
};