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

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* solution = new Solution(capacity);
 * int output = solution->get(key);
 * solution->set(key,value);
 */


 /*
     //哈希表：根据key直接访问value的一种数据结构。用来统计频率、快速检验某个元素是否出现过等。
//     设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 capacity ，操作次数是 n ，并有如下功能:
// 1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
// 2. get(key)：如果关键字 key 存在于缓存中，则返回key对应的value值，否则返回 -1 。
// 3. set(key, value)：将记录(key, value)插入该结构，如果关键字 key 已经存在，则变更其数据值 value，如果不存在，则向缓存中插入该组 key-value ，如果key-value的数量超过capacity，弹出最久未使用的key-value


 */
 #include <list>
class Solution {
    list<pair<int,int>> dou_list;//双向链表
    unordered_map<int, list<pair<int, int>>::iterator> m;//一个容器map
    //unordered_map是一个将key和value关联起来的容器，它可以高效的根据单个key值查找对应的value。
    //用链表存，链表头部是最近使用的，尾部是最后使用的，如果要删去，就直接把尾部删去
    int n_capacity;
public:
    Solution(int capacity){
         // write code here
         n_capacity=capacity;
    }
    
    int get(int key) {
         // write code here
         if(m.count(key))
         {
            //放在头部，需要tmp存着，然后删掉这个位置，再放到头部
            auto tmp=*m[key];
            dou_list.erase(m[key]);
            dou_list.push_front(tmp);//把它放在最前面==在容器头部插入一个数据
            m[key]=dou_list.begin();
            //return tmp.second;
           return dou_list.front().second;
         }
         return -1;
    }
    
    void set(int key, int value){
         // write code here
         if(m.count(key))
         {
            //如果map容器m的key存在
            dou_list.erase(m[key]);//删除这个位置的key

         }
         else if(n_capacity==dou_list.size())
         {
            //删掉末尾的
            auto tmp_f=dou_list.back();//末尾元素赋值给tmp——f
            m.erase(tmp_f.first);
            dou_list.pop_back();//尾删法

         }
         dou_list.push_front(pair<int,int>(key,value));
         m[key]=dou_list.begin();
    }
};