C++基于unordered_map和list实现LRU设计，仅需50行代码

要点：

1. 采用list作为数据存储容器，unordered_map作为查询容器来存储list节点的迭代器。由于set和get操作时间复杂度均为O(1)，因此不能用map。
2. set操作：
   • 判断键值是否存在：
   • 若存在，则提取出键值对，同时摧毁原有list容器中的节点，并从链表头部重新增加更新节点；
   • 不存在，则需要判断当前链表长度是否超过限制长度k；超过k，则需要摧毁list尾结点和unordered_map中的相应键值对，同时从头部重新增加新的键值对。
3. get操作:
   • 同样需要判断键值是否存在：
   • 若存在，与set处理方法一致，并返回value；
   • 不存在，则返回-1。

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<pair<int, int> > data;
        unordered_map<int, list<pair<int, int> >::iterator> hash;
        vector<int> res;
        for(auto& opt : operators) {
            if(opt[0] == 1) {
                // 插入值
                if(hash.count(opt[1])) {		// map中存储过key值，则将其移动到头部
                    auto& it = hash[opt[1]];	// 提取已有节点
                    data.erase(it);				// 摧毁list原有键值对
                    data.push_front(make_pair(opt[1], opt[2]));	// 重新插入新的键值对
                    hash[opt[1]] = data.begin();// 更新unordered_map
                    continue;
                }
                if(data.size() >= k) {
                    auto& node = data.back();	// 提取尾结点
                    int key = node.first;		// 提取尾结点键值
                    auto& it = hash[key];		// 提取尾结点迭代器对象
                    data.erase(it);				// 摧毁尾结点
                    hash.erase(key);			// 摧毁键值对
                }
                data.push_front(make_pair(opt[1], opt[2]));
                hash[opt[1]] = data.begin();
            } else {
                if(hash.count(opt[1])) {
                    auto& it = hash[opt[1]];
                    int value = (*it).second;
                    res.push_back(value);
                    data.erase(it);
                    data.push_front(make_pair(opt[1], value));
                    hash[opt[1]] = data.begin();
                } else {
                    res.push_back(-1);
                }
            }
        }
        return res;
    }
};