本文共 2782 字，大约阅读时间需要 9 分钟。

class LRUCache {
   public:    LRUCache(int capacity):c(capacity) {
       }        int get(int key) {
           if(m.find(key)==m.end())            return -1;        moveToHead(key);        return m[key]->second;    }        void put(int key, int value) {
           if(m.find(key)==m.end()){
               l.push_front(pr(key,value));            m[key]=l.begin();            if(l.size()>c){
                   m.erase(l.back().first);                l.pop_back();            }        }        else{
               m[key]->second=value;            moveToHead(key);        }    }    void moveToHead(int key){
           l.push_front(*m[key]);        l.erase(m[key]);        m[key]=l.begin();    }private:    using pr=pair
   
    ;    using it=list
    
     ::iterator;    //双向链表    list
     
       l;    //哈希表    unordered_map
      
        m;    //容量    int c;};/** * 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); */
      
     
    
   

或者自己实现一个双向链表：

class LRUCache {
   private:    struct node{
           int key,value;        node *nxt,*pre;        node():key(0),value(0),nxt(nullptr),pre(nullptr){
   }        node(int key,int value):key(key),value(value),nxt(nullptr),pre(nullptr){
   }    };    //伪头尾节点    node head,tail;    unordered_map
   
     m;    //容量和当前节点个数    int c,siz;public:    LRUCache(int capacity):c(capacity),siz(0) {
           head.nxt=&tail;        tail.pre=&head;    }        int get(int key) {
           if(m.find(key)==m.end())            return -1;        node *tmp=m[key];        moveToHead(tmp);        return tmp->value;    }        void put(int key, int value) {
           if(m.find(key)==m.end()){
               node *tmp=new node(key,value);            addHead(tmp);            m[key]=tmp;            if(++siz>c){
                   removeTail();                --siz;            }        }        else{
               node *tmp=m[key];            tmp->value=value;            moveToHead(tmp);        }    }    void removeNode(node* n){
           n->pre->nxt=n->nxt;        n->nxt->pre=n->pre;    }    void addHead(node* n){
           n->nxt=head.nxt;        head.nxt->pre=n;        head.nxt=n;        n->pre=&head;    }    void moveToHead(node* n){
           removeNode(n);        addHead(n);    }    void removeTail(){
           node *tmp=tail.pre;        removeNode(tmp);        m.erase(tmp->key);        delete tmp;    }};/** * 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); */
   

转载地址：https://blog.csdn.net/xiji333/article/details/108100681 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！