Leetcode146.LRU cache（最近最少使用）

╰半夏微凉° 2023-05-28 11:13 6阅读 0赞

**题目：**  
设计和实现最近最少使用（LRU）缓存的数据结构。它应支持以下操作：get和put。  
get(key)-如果键在缓存中，则获取键的值（始终为正），否则返回-1。  
put(key, value)-如果密钥不存在，请设置或插入值。当缓存达到其容量时，它应在插入新项目之前使最近最少使用的项目无效。  
高速缓存初始化为正容量。  
**思路：**  
需要实现一个类。首先两个任务：1，使用易于查找O（1）的数据结构来存key-value，使用无序map；2，需要知道每次的put和get时的最近最少使用的节点是哪一个。然后在**map的size==capacity时**，踢掉不需要的来插入需要的。**使用list来满足O（1）的时间复杂度来查找到map的key的迭代器**  
细节说明：  
**采用了unordered\_map的结构，key和pair来组合。这样组合的意义在于更加方便的通过map的 iterator 来耦合list，来修改和查询list的位置。**

实现：  
注意是整个缓存都要改变。

class LRUCache { 
    private:
        typedef list<int> LNode;
        typedef pair<int,LNode::iterator> Pair;     //pair中保存的才是val
        typedef unordered_map<int, Pair> MyMap;
        
        //每一个LRUcached 都有一个map用于 索引； 一个list用于管理 最近缓存
        MyMap cache;        //hash
        LNode Recent;       //list
        
        int _capacity;      
        
        void moveNode(MyMap::iterator it){ 
            
            int key=it->first;      //键值
            Recent.erase(it->second.second);        //节点已经被删除了，迭代器失效了！需要再赋值
            Recent.push_front(key);
            it->second.second=Recent.begin();       //key对应的节点迭代器赋值
        };
    public:
        LRUCache(int capacity):_capacity(capacity) { }
        
        int get(int key) { 
        if(cache.find(key)!=cache.end()){ 
            //说明找到了
            auto it=cache.find(key);
            moveNode(it);
            return it->second.first;
            }
        else 
            return -1;
        }
        
        void put(int key, int value) { 
            if(cache.find(key)==cache.end()){ 
                //cache没有
                if(Recent.size()==_capacity){ 
                    cache.erase(Recent.back());
                    Recent.pop_back();
                }
                Recent.push_front(key);     //再首部
            }
            else
                moveNode(cache.find(key));      //有，移动就可
            //避免同一个键回改变val
            cache[key]={ value, Recent.begin()};
            return ;
        }
    };
    
    /** * Your LRUCache object will be instantiated and called as such: * LRUCache* obj = new LRUCache(capacity); * int param_1 = obj->get(key); * obj->put(key,value); */

后一篇文章补充unordered\_map。

> the stones you collect will become the way you walk.