描述
设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能
set(key, value)：将记录(key, value)插入该结构
get(key)：返回key对应的value值
[要求]
set和get方法的时间复杂度为O(1)
某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。
当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。
若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
对于每个操作2，输出一个答案
解题思路

  1. 要求set和get方法的时间复杂度为O(1)，首先想到的就是unordered_map
  2. LRU缓存结构实际上是一种有序的结构，根据访问顺序来进行排序，只要有一种结构能保存这种顺序即可，使用vector、list、链表等等都行
  3. 题目要求在构造时确定大小，所以要有一个成员变量表示最大缓存大小m_max_size，在类的构造函数中进行初始化
  4. 既然有了m_max_size就要有一个表示当前缓存大小的成员变量m_current_size，在插入的时候需要将m_current_size加1，在删除元素的时候需要将m_current_size减1，需要注意的是m_current_size不能比m_max_size大，凡是超过的情况下都应该删除元素

代码

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) {
        //operators = [[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]]
        //oper0=[1,1,1]   oper1=[1,2,2]  oper2=[1,3,2] ...
        //k  = 3
        vector<int> ret;
        lru_cache cache(k);
        for(auto& oper: operators)
        {
            if(oper[0] == 1) {
                cache.set(oper[1], oper[2]);
            }else if(oper[0] == 2) {
                ret.push_back(cache.get(oper[1]));
            }
        }
        return ret;
    }

    class lru_cache {
    public:
        lru_cache(int k)
        {
            m_max_size = k;
            m_current_size = 0;
        }
        void set(int key, int value);
        int  get(int key);
    private:
            using lru_list = std::list<std::pair<int, int>>;
            using lru_list_iter = lru_list::iterator;
            using lru_map = unordered_map<int, lru_list_iter>;
            using lru_map_iter = lru_map::iterator;

            lru_list m_list;
            lru_map  m_map;
            int      m_max_size;
            int      m_current_size;

            void increase_size() {
                m_current_size++;
            }
            void decrease_size() {
                m_current_size--;
            }
    };
};

void Solution::lru_cache::set(int key, int value)
{
    lru_map_iter map_iter = m_map.find(key);
    if(map_iter != m_map.end()) {
        //覆盖旧的值;
        map_iter->second->second = value;
        //更新LRU;
        m_list.splice(m_list.begin(), m_list, map_iter->second);
    }else {
        //插入新值到首部;
        m_list.push_front(make_pair(key,value));
        //更新m_map;
        m_map[key] = m_list.begin();
        //插入后当前大小增加;
        increase_size();

        lru_list_iter list_iter;
        while(m_current_size > m_max_size && !m_list.empty()) {
            //获取最不常用的元素并进行删除;
            list_iter = --m_list.end();
            m_map.erase(list_iter->first);
            m_list.erase(list_iter);
            //删除后当前大小减少;
            decrease_size();
        }
    }
}

int Solution::lru_cache::get(int key)
{
    lru_map_iter map_iter = m_map.find(key);
    if(map_iter != m_map.end()) {
        //更新LRU;
        m_list.splice(m_list.begin(), m_list, map_iter->second);
        //返回最终查询到的数据;
        return map_iter->second->second;
    }else {
        //没有找到则返回-1;
        return -1;
    }
};

拓展
集合set是无序的，cpp中如何实现一个有插入顺序的set呢，和此题类似，满足插入、查询的需求可使用unordered_map，使用vector、list、链表等保证插入顺序即可