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

一个list存数据，一个unordered_map存key和对应数据的引用。 这里最最最最最最最最最关键的一点就是List增删改元素是不会使迭代器无效的，只要知道这个，写出对应的数据结构和算法应该不会难。

下面的代码对于数据的pair做了移动处理，可能可以提升get太多情况下的效能。不过不太知道这会不会产生UB，还请大手子解答！

public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    unordered_map<int,list<pair<int,int>>::iterator> is_present;
    list<pair<int,int>> cache;
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        vector<int> result;
        pair<int,int> cur_elem;
        for (const vector<int>& operation: operators){
            switch (operation[0]){
                case 1:{
                    // Remove the key first if already present
                    if (is_present.count(operation[1]) != 0)
                    {
                        cur_elem = move(*is_present[operation[1]]);
                        cache.erase(is_present[operation[1]]);
                        is_present.erase(operation[1]);
                        cur_elem.second = operation[2];
                        cache.push_back(move(cur_elem));
                    }
                    else
                    {
                        cache.push_back(pair<int,int>(operation[1], operation[2]));
                    }
                    
                    // Insert the key to the cache and the map
                    pair<int,list<pair<int,int>>::iterator> new_elem = {operation[1], prev(cache.end())};
                    is_present.insert(new_elem);
                    
                    // Exceed maximum capacity, remove oldest
                    if (is_present.size() > k)
                    {
                        is_present.erase(cache.front().first);
                        cache.pop_front();
                    }
                    break;
                }
                case 2:{
                    if (is_present.count(operation[1]) == 0)
                    {
                        result.push_back(-1);
                    }
                    else
                    {
                        cur_elem = move(*is_present[operation[1]]); 
                        result.push_back(cur_elem.second);
                        
                        cache.erase(is_present[operation[1]]);
                        is_present.erase(operation[1]);
                        
                        cache.push_back(move(cur_elem));
                        pair<int,list<pair<int,int>>::iterator> new_elem = {operation[1], prev(cache.end())};
                        is_present.insert(new_elem);
                    }
                    break;
                }
                default:
                    break;
            }
        }
        return result;
    }
};