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

用一个双向链表，哈希表存key以及双向链表的迭代器。

当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。

在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。

class Solution {
    list<pair<int, int>> dlist;//双向链表
    unordered_map<int, list<pair<int, int>>::iterator> map;
    int cap;
    
    //用链表存，链表头部是最近使用的，尾部是最后使用的，如果要删去，就直接把尾部删去就好
public:
    Solution(int capacity){
         cap=capacity;
    }
    
    //key就变得最常用了
    int get(int key) {
        if(map.count(key))
        {
            //把这个放在头部，所以需要个tmp存着，然后删掉这个位置，再放到头部
            auto tmp=*map[key];
            dlist.erase(map[key]);
            //map.erase(key);
            dlist.push_front(tmp);//把它放在最前面
            map[key]=dlist.begin();
            //return tmp.second;
            return dlist.front().second;
        }
        return -1;
    }
    
    void set(int key, int value){
         if(map.count(key))//如果存在
         {
             dlist.erase(map[key]);//放在头部
             //map.erase(key);
         }
        else if(cap==dlist.size())
        {
            //先删掉末尾的
            auto tmp=dlist.back();
            map.erase(tmp.first);
            dlist.pop_back();
        }
        dlist.push_front(pair<int, int>(key, value));
        map[key]=dlist.begin();//第一个迭代器
    }
};