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

#include<list>
#include<unordered_map>

class Solution {

private:
    int n;
    list<pair<int, int>> List;
    unordered_map<int, list<pair<int, int>>::iterator> Map;
    vector<int> ans;
    unordered_map<int, list<pair<int, int>>::iterator>::iterator it;
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) {
        n = operators.size();
        for(int i = 0; i < n; ++i){
            int opt = operators[i][0];
            int key, val;
            if(opt == 1){
                key = operators[i][1];
                val = operators[i][2];
                if((it = Map.find(key)) != Map.end()){ // 如果map中已经存在该键值，先删除
                    list<pair<int,int>>::iterator it1 = it->second;
                    int val1 = it1->second;
                    List.erase(it1);
                    Map.erase(key);
                }
                else if(List.size() >= k){ // 超过限定大小，删除链表末尾元素
                    int key1 = List.back().first ;
                    List.pop_back();
                    Map.erase(key1);
                }
                // 在链表头插入新的键值对，并用map关联其在链表中的迭代器
                List.push_front(pair<int, int>(key, val));
                Map.insert(pair<int, list<pair<int, int>>::iterator>(key, List.begin()));
            }
            if(opt == 2){
                key = operators[i][1];
                if((it = Map.find(key)) != Map.end()){ // 查找，注意更新查找元素在链表中的位置
                    list<pair<int,int>>::iterator it1 = it->second;
                    int val1 = it1->second;
                    // 先删除
                    List.erase(it1);
                    Map.erase(key);
                    // 再在链表头插入
                    List.push_front(pair<int, int>(key, val1));
                    Map.insert(pair<int, list<pair<int, int>>::iterator>(key, List.begin()));
                    ans.push_back(val1);
                }else{
                    // 没有查找到，返回-1
                    ans.push_back(-1);
                }
            }
            // 输出调试
//             for(list<pair<int,int>>::iterator it = List.begin(); it != List.end(); ++it){
//                 cout << it->first << "," << it->second << " ";
//             }
//             cout << endl;
        }
        return ans;

    }
};