LRU缓存机制

时间：2021-08-04 19:23:00 阅读：26 评论：0 收藏：0 [点我收藏+]

技术分享图片

变量简洁正确完整思路

哈希表key2node，双向队列cache存放pair，

对于put，如果key在key2ndoe中提前删除，如果cache等于最大容量maxCapacity提前删除key2node中的cache最后一个和删除cache最后一个，更新cache和key2node，{key,node}放入cache前面并更新key2node[key]

对于get，如果key2node找不到keyreturn-1，将{key,val}从key2node取出，更新cache，cache删除key2node[key]指向的节点并将该节点放到cache前面，更新key2node[key]，key2node[key]指向cache前面，返回val

精确定义

key2node哈希表，key映射一个迭代器，指向cache中{key,value}

cache双向链表，保存{key，value}

class LRUCache {
public:
    LRUCache(int capacity) :maxCapacity(capacity){}
    
    int get(int key) {
        if(!key2node.count(key))return -1;
        cache.splice(cache.begin(),cache,key2node[key]);
        return key2node[key]->second;
    }
    
    void put(int key, int value) {
        if(key2node.count(key))cache.erase(key2node[key]);
        if(cache.size()==maxCapacity){
            key2node.erase(cache.back().first);
            cache.pop_back();
        }
        cache.push_front({key,value});
        key2node[key]=cache.begin();
    }
private:
    list<pair<int,int>>cache;
    unordered_map<int,list<pair<int,int>>::iterator>key2node;
    int maxCapacity;
};

踩过的坑

list<pair<int,int>>cache;list小写

cache.erase(key2node[key]);哈希表才能用val来删除，这个list用迭代器删除

if(key2node.count(key))cache.erase(key2node[key]);哈希表查找，list需要迭代器才能删除

key2node.erase(cache.back().first);删除key2node中cache最后一个

cache.splice(cache.begin(),cache,key2node[key]);将cache的key2node[key]

指向的节点接到cache的cache.begin()迭代器指向的节点前面

详细思路

在原来的基础上修改，实现myList和Node，实现myList一些

struct Node{
    Node(int key,int value):key(key),value(value){}
    int key;
    int value;
    Node *prev;
    Node *next;
};
class myList{
public:
    myList(){
        head=new Node(-1,-1);
        tail=new Node(-1,-1);
        head->next=tail;
        tail->prev=head;
        mSize=0;
    }
    void splice(Node *it1, myList l2, Node*it2){
        it2->prev->next=it2->next;
        it2->next->prev=it2->prev;
        it2->prev=it1->prev;
        it2->next=it1;
        it1->prev->next=it2;
        it1->next->prev=it2;
        mSize++;
    }
    Node *begin() { return head->next; }
    void erase(Node *it) {
        it->prev = it->next;
        mSize--;
        delete it;
    }
    int size() { return mSize; }
    Node* back() { return tail->prev; }
    void pop_back(){
        tail = tail->prev;
        mSize--;
        delete tail->next;
    }
    void push_front(Node*node){
        node->prev = head;
        node->next = head->next;
        head->next = node;
        node->next->prev = node;
        mSize++;
    }

private:
    Node* head,*tail;
    int mSize;
};
class LRUCache {
public:
    LRUCache(int capacity) :maxCapacity(capacity){}
    
    int get(int key) {
        if(!key2node.count(key))return -1;
        cache.splice(cache.begin(),cache,key2node[key]);
        return key2node[key]->value;
    }
    
    void put(int key, int value) {
        if(key2node.count(key))cache.erase(key2node[key]);
        if(cache.size()==maxCapacity){
            key2node.erase(cache.back()->key);
            cache.pop_back();
        }
        Node *node =new Node(key, value);
        cache.push_front(node);
        key2node[key]=cache.begin();
    }
private:
    myList cache;
    unordered_map<int,Node*>key2node;
    int maxCapacity;
};

LRU缓存机制

原文：https://www.cnblogs.com/zhouzihong/p/15099908.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)