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