C++实现LRU缓存——LeetCode 146

1.手动实现双向链表

class LRUCache {
public:
    // 双向链表的数据结构
    struct Node{
        int key,val;
        Node*left,*right;
        Node(int _key,int _val):key(_key),val(_val),left(NULL),right(NULL){}
    };
    Node *L,*R;  // 最左边的和最右边的节点;第一个元素：L->right;最后一个元素：R->left
    unordered_map<int,Node*> map ;
    int n;     // 当前节点数量
    int size ; // 最大容量

    // 双向链表的基本操作
    void remove(Node *p){
        p->left->right = p->right;
        p->right->left = p->left ;
    }
    void insertAtLeft(Node *p){
        p->right = L->right;
        p->left = L ;
        L->right->left = p;
        L->right  = p;
    }
    
    // LRUCache的基本操作
    LRUCache(int capacity) {
        size = capacity ; 
        n = 0;   
        L = new Node(-1,-1);
        R = new Node(-1,-1);
        L->right = R ;
        R->left = L ;
    }
    
    int get(int key) {
        if(map.count(key)==0)
            return -1;
        // 删掉原节点  将其插入到最左边
        int val = map[key]->val;
        remove(map[key]); 
        Node *newNode = new Node(key,val);
        map[key] = newNode ;
        insertAtLeft(newNode);

        return val;
    }
    
    void put(int key, int value) {
        // 判断是否存在此节点
        if(get(key)!=-1){  // key存在, get函数已经将key移到头部
            map[key]->val = value;  // 或 L->right->val
        }
        else{
            Node *newNode = new Node(key,value);
            if(n==size){    //满了
                map.erase(R->left->key);
                remove(R->left);   // 从双向链表删除最右边节点
                insertAtLeft(newNode);
            }else{
                insertAtLeft(newNode);
                n++ ;
            }
            map[key]=newNode;
        }
        
    }
};

/**
 * 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);
 */

2.使用STL容器list（省去很多麻烦…）

list的常见方法：

• begin(): 返回第一个元素的迭代器
• end(): 最后一个元素的下一个位置的迭代器
• front(): 第一个元素的引用
• back(): 最后一个元素的引用
• emplace_front(), emplace_back() : 头部，尾部生成一个元素，比push_back效率高
• push_back(), pop_back(): 尾部插入、删除一个元素
• splice(): 将一个 list 容器中的元素插入到另一个容器的指定位置

class LRUCache {
private:
    int cap = 0 ;
    list<pair<int,int>> li;     // 保存Cache数据的
    unordered_map<int,list<pair<int,int>>::iterator> mp;   // 查找Cache中是否存在此key的
public:
    LRUCache(int capacity) {
        cap = capacity ;
    }
    
    int get(int key) {
        if(mp.find(key)==mp.end())   // key不存在
            return -1;
        li.splice(li.begin(),li,mp[key]); // li的mp[key]，插入到li.begin()，这里都是迭代器
        return li.begin()->second;  
        // return li.front().second;  // 或者这么写
    }
    
    void put(int key, int value) {
        if(get(key)!=-1)  // key 存在 ，get函数已经将其移到头部
            li.begin()->second = value ;
        else{   // key不存在
            if(li.size()==cap){
                int delKey = li.back().first;
                li.pop_back();
                mp.erase(delKey);
            }  // 满了
            li.emplace_front(key,value);
            mp[key]=li.begin();
        }
    }
};

/**
 * 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);
 */