LRU的实现(使用list)

2019-08-19 08:47:22来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

LRU的实现(使用list)

首先是LRU的定义,LRU表示最近最少使用,如果数据最近被访问过,那么将来被访问的几率也更高。

所以逻辑应该是每次都要将新被访问的页放到列表头部,如果超过了list长度限制,就将列表尾部的元素踢出去。

 

主要结构,STL中的双向链表结构list。

主要操作有get,表示访问key对应的value,此时要查询双链表,找到key对应value,再将其从list中删除,插入到list的头部。

     set,  表示设置对应的key值为value,此时先找到key对应的元素,将其从list中删除,再插入到list的头部。

这里设置了两个辅助函数remove和setHead,分别负责删除元素和将元素加入到list头部。

 

代码实现如下:

#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>

using namespace std;

class LRUNode
{
    public:
        int key,value;
        LRUNode(int _key,int _value):key(_key),value(_value)
        {
        }
        bool operator==(LRUNode * p)
        {
            return key==p->key;
        }
};

class LRU
{
    public:
        int get(int key);
        void set(int key,int val);
        LRU(int _cap):cap(_cap)
        {
        }
        int cap;//代表存放的最大页数
        void remove(int key);
        void setHead(int key,int val);
        void printLis();
        list<LRUNode *> lis;
};

void LRU::printLis()
{
    list<LRUNode *>::iterator it;
    for(it=lis.begin();it!=lis.end();it++)
    {
        cout<<(*it)->key<<" "<<(*it)->value<<endl;
    }
    cout<<endl;
}

void LRU::remove(int key)
{
    LRUNode * searchNode=new LRUNode(key,0);
    list<LRUNode *>::iterator it=find(lis.begin(),lis.end(),searchNode);
    if(it!=lis.end())
    {
        lis.remove(*it);
    }
}

void LRU::setHead(int key,int val)
{
    lis.push_front(new LRUNode(key,val));
}

int LRU::get(int key)
{
    LRUNode * searchNode=new LRUNode(key,0);
    list<LRUNode *>::iterator it=find(lis.begin(),lis.end(),searchNode);
    if(it!=lis.end())
    {
        remove((*it)->key);
        setHead((*it)->key,(*it)->value);
        return (*it)->value;
    }
    return -1;//表示没有找到
}

void LRU::set(int key,int value)
{
    if(lis.size()>=cap)
    {
        lis.pop_back();
    }
    LRUNode * searchNode=new LRUNode(key,0);
    list<LRUNode *>::iterator it=find(lis.begin(),lis.end(),searchNode);
    if(it!=lis.end())
    {
        remove(key);
        setHead(key,value);
    }
    else
    {
        setHead(key,value);
    }
}



int main()
{
    LRU * lru=new LRU(5);
    lru->set(1,1);
    lru->printLis();
    lru->set(2,2);
    lru->printLis();
    lru->set(3,3);
    lru->printLis();
    lru->set(4,4);
    lru->printLis();
    lru->set(5,5);
    lru->printLis();
    lru->set(6,6);
    lru->printLis();
    lru->set(7,7);
    lru->printLis();
    return 0;
}

运行结果:

1 1

2 2
1 1

3 3
2 2
1 1

4 4
3 3
2 2
1 1

5 5
4 4
3 3
2 2
1 1

6 6
5 5
4 4
3 3
2 2

7 7
6 6
5 5
4 4
3 3

 


原文链接:https://www.cnblogs.com/JsonZhangAA/p/11374439.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:程序运行时间测试 - 使用libc 中 time 函数 实现秒级的运行时间

下一篇:程序运行时间测试 - 使用系统函数 getrusage 获取程序运行时间