C++ LRU

向右看齐 2022-10-24 02:05 12阅读 0赞

#include<bits/stdc++.h>
    using namespace std;
    
    /* 思路：LRU最近最少使用，使用list存储链表 使用unordered_map，来存储key和list的迭代器的映射 查找的时候，使用map快速定位list，并且更新mp和list 插入的时候也对他们两个进行更新 */
    
    class Lru{ 
    public :
        Lru(int siz=5):cnt(siz){ };
    
        void show(){ 
            auto t=data.begin();
            while(t!=data.end()){ 
                cout<<t->key<<" "<<t->value<<endl;
                t++;
            }
        }
        void test(){ 
            cout<<data.begin()->key<<" " <<data.begin()->value;
        }
        void set(int k,int v){ 
            if(mp.find(k)!=mp.end()){ //曾经存在
                mp[k]->value=v;
                data.splice(data.begin(),data,mp[k]);
                mp[k]=data.begin();
            }else{ 
                if(data.size()<cnt){ //list未满，直接插入只一个
                    data.push_front(Node(k,v));
                    mp[k]=data.begin();
                }else{ //list表已经满,先删除一个再插入一个
                    mp.erase(data.back().key);
                    data.pop_back();
                    data.push_front(Node(k,v));
                    mp[k]=data.begin();
                }
            }
        }
        int get(int k){ 
            if(mp.find(k)==mp.end())return -1;//发生缺页中断
            data.splice(data.begin(),data,mp[k]);
            mp[k]=data.begin();
            return mp[k]->value;
    
    
        }
    private:
        struct Node{ 
            int key;
            int value;
            Node(int k,int v):key(k),value(v){ }
        };
        int cnt;
        list<Node> data;
        unordered_map<int ,list<Node>::iterator> mp;
    };
    int main(){ 
        Lru lru(5);
        for(int i=0;i<=5;i++){ 
            lru.set(i,i);
            cout<<"-----------"<<endl;
            lru.show();
        }
        cout<<endl<<endl;;
        cout<<lru.get(3);
        cout<<"-----------"<<endl;
        lru.show();
    
    
        cout<<lru.get(2);
        cout<<"-----------"<<endl;
        lru.show();
    
    
        cout<<lru.get(4);
        cout<<"-----------"<<endl;
        lru.show();
    
        return 0;
    }