今天，偶尔有空，我们来实现LRU cache算法。LRU是啥？请问度娘去~~~
LRU实现的三个原则：
（1）越靠近链表头部的节点，表示该节点上次被访问离现在时间最短。而尾部的节点表示最近访问最少。
（2）查询或者设置节点时，若节点存在则将其插入到链表头部，若不存在则新建节点，并插入到链表头部。
（3）插入节点时，若cache的容量已经达到最大值，则将链表尾部的节点删除，新节点插入到链表头部。
OK，按照这三个节点，我们编写代码吧~~~
1.首先，定义cache中的节点：
template <typename T,typename E>
struct CacheNode //链表中的节点
{
T key; //键
E value; //值
CacheNode(T k,E val):key(k),value(val){};
CacheNode<T,E>* pre; //指向前驱节点
CacheNode<T,E>* next; //指向后续节点
};
2.定义LRU类，我将所有的方法都定义在类内部了，这种做**导致方法都是inline的，大家最好将比较长的方法定义在类外部。类中各个方法的实现具体不多说了，注释已经说得很清楚了，有问题回复我。OK，蟹蟹大家！！
template <typename T,typename E>
class LRUChacheList //LRU类
{
public:
//构造函数
LRUChacheList(int sz,T key,E val):mSize(sz)
{
mHead = new CacheNode<T,E>(key,val);
mHead->next = nullptr;
mHead->pre = nullptr;
mCurrentSize = 0;
}
//虚析构函数
virtual ~LRUChacheList()
{
if (nullptr == mHead->next) //只有头结点
{
delete mHead;
}else //有多个节点
{
CacheNode<T,E>* p = mHead->next;
CacheNode<T,E>* q = nullptr;
while (p != mHead)
{
q = p;
p = p->next;
delete q;
}
delete mHead;
}
}
//设置新值
void setKey(T key,E value)
{
CacheNode<T,E>* ret=nullptr;
if (findKey(key,ret) == false) //当前cache没有对应键的值
{
if (mCurrentSize == mSize) //cache已经满 则删除链表尾部的节点
{
CacheNode<T,E>* p = mHead->pre;
CacheNode<T,E>* q = p->pre;
mHead->pre = q;
q->next = mHead;
delete p;
--mCurrentSize;
}
//新建节点 并插入到链表头部
CacheNode<T,E>* s = new CacheNode<T,E>(key,value);
++mCurrentSize;
if (mHead->next == nullptr) //第一次插入节点时
{
mHead->next = s;
s->pre = mHead;
s->next = mHead;
mHead->pre = s;
return;
}
//第二次以后插入节点
mHead->next->pre = s;
s->next = mHead->next;
mHead->next = s;
s->pre = mHead;
}else //如果找到对应的键值 则更新它的值
{
if(nullptr != ret)
{
ret->pre->next = ret->next;
ret->next->pre = ret->pre;
mHead->next->pre = ret;
ret->next = mHead->next;
mHead->next = ret;
ret->pre = mHead;
ret->value = value;
}
}
}
//获取对应键的值
bool getValue(T& key,E& val)
{
CacheNode<T,E>* ret=nullptr;
if(true == findKey(key,ret)) //找到
{
if(nullptr != ret)
{
CacheNode<T,E>* tmp;
ret->pre->next = ret->next;
ret->next->pre = ret->pre;
mHead->next->pre = ret;
ret->next = mHead->next;
mHead->next = ret;
ret->pre = mHead;
val = ret->value;
}
return true;
}
//没找到
return false;
}
//打印cache中的节点的值
void print()
{
if (nullptr == mHead)
return ;
CacheNode<T,E>* p = mHead->next;
while (p != mHead)
{
cout << p->value << " ";
p = p->next;
}
cout << endl;
}
//重载<<
ostream& operator<< (CacheNode<T,E>& s)
{
return cout<<s.value;
}
protected:
//找cache中是否存在对应的键 若存在将节点通过参数s返回 函数返回true
bool findKey(T key,CacheNode<T,E>*& s)
{
if (nullptr == mHead->next)
return false;
CacheNode<T,E>* p = mHead->next;
while (p != mHead)
{
if (key == p->key)
{
s = p;
return true;
}
p = p->next;
}
return false;
}
//找值 并通过参数s返回改节点
bool findValue(E val,CacheNode<T,E>*& s)
{
if (mHead->next == nullptr)
return false;
CacheNode<T,E>* p = mHead->next;
while (p != mHead)
{
if (p->value == val)
{
s = p;
return true;
}
p = p->next;
}
return false;
}
private:
int mSize; //cache的总容量
int mCurrentSize; //cache的当前容量
CacheNode<T,E>* mHead; //链表的头结点 用于管理链表
};
int main()
{
LRUChacheList<int,int> lru(5,-1,-1);
lru.setKey(1,12);
lru.setKey(2,13);
lru.setKey(3,14);
lru.setKey(4,15);
lru.setKey(5,16);
lru.print();
lru.setKey(6,17);
lru.print();
lru.setKey(7,18);
lru.print();
int ret = 0;
int key = 5;
lru.getValue(key,ret);
lru.print();
lru.setKey(7,188);
lru.print();
return 0;
}
测试中我将cache的容量设置为5个元素。
16 15 14 13 12 //这是新加入的5个元素，刚刚满，可以看出，最新插入的元素都在链表头部
17 16 15 14 13 //这里表示有加入一个节点，但是cache已经满了，所以将尾部的节点（这里是12）删除，新节点插入到链表头部
18 17 16 15 14 //同上
16 18 17 15 14 //这里表示获取键为5（对应的值是16）的节点，然后将这个节点插入到链表头部
188 16 17 15 14 //这里表示降键为7的节点的值修改为188，然后将该节点移动到链表头部
到此，LRU cache就实现了。程序有任何问题的请大家@我，蟹蟹！！！
| 
楼主
标题置顶
标题高亮
