C++教程：LRUCache的简单C++实现

　　C++培训LRU是什么，相信很多人对这个都还不是很了解!今天，小编就给大家介绍LRU Cache 的简单 C++ 实现

　　LRU Cache是一个Cache的置换算法，含义是“最近最少使用”，把满足“最近最少使用”的数据从Cache中剔除出去，并且保证Cache中第一个数据是最近刚刚访问的，因为这样的数据更有可能被接下来的程序所访问。

　　LRU的应用比较广泛，最基础的内存页置换中就用了，对了，这里有个概念要清楚一下，Cache不见得是CPU的高速缓存的那个Cache，这里的Cache直接翻译为缓存，就是两种存储方式的速度有比较大的差别，都可以用Cache缓存数据，比如硬盘明显比内存慢，所以常用的数据我们可以Cache在内存中。

　　LRU 基本算法描述

　　前提：

　　由于我只是简单实现一下这个算法，所以数据都用int代替，下一个版本会改成模板形式的，更加通用。

　　要求：

　　只提供两个接口，一个获取数据getValue(key),一个写入数据putValue(key,value)

　　无论是获取还是写入数据，当前这个数据要保持在最容易访问的位置

　　缓存数量有限，最长时间没被访问的数据应该置换出缓存

　　算法：

　　为了满足上面几个条件，实际上可以用一个双向链表来实现，每次访问完数据(不管是获取还是写入)，调整双向链表的顺序，把刚刚访问的数据调整到链表的最前方，以后再访问的时候速度将最快。

　　为了方便，提供一个头和一个尾节点，不存具体的数，链表的基本形式如下面的这个简单表述

　　Head <===> Node1 <===> Node2 <===> Node3 <===> Near

　　OK，就这么些，比较简单，实现起来也不难，用c++封装一个LRUCache类，类提供两个方法，分别是获取和更新，初始化类的时候传入Cache的节点数。

　　先定义一个存数据的节点数据结构

　　typedef struct _Node_{

　　int key; //键

　　int value; //数据

　　struct _Node_ *next; //下一个节点

　　struct _Node_ *pre; //上一个节点

　　}CacheNode;

　　类定义：

　　class LRUCache{

　　public:

　　LRUCache(int cache_size=10); //构造函数，默认cache大小为10

　　~LRUCache(); //析构函数

　　int getValue(int key); //获取值

　　bool putValue(int key,int value); //写入或更新值

　　void displayNodes(); //辅助函数，显示所有节点

　　private:

　　int cache_size_; //cache长度

　　int cache_real_size_; //目前使用的长度

　　CacheNode *p_cache_list_head; //头节点指针

　　CacheNode *p_cache_list_near; //尾节点指针

　　void detachNode(CacheNode *node); //分离节点

　　void addToFront(CacheNode *node); //将节点插入到第一个

　　};

　　类实现：

　　LRUCache::LRUCache(int cache_size)

　　{

　　cache_size_=cache_size;

　　cache_real_size_=0;

　　p_cache_list_head=new CacheNode();

　　p_cache_list_near=new CacheNode();

　　p_cache_list_head->next=p_cache_list_near;

　　p_cache_list_head->pre=NULL;

　　p_cache_list_near->pre=p_cache_list_head;

　　p_cache_list_near->next=NULL;

　　}

　　LRUCache::~LRUCache()

　　{

　　CacheNode *p;

　　p=p_cache_list_head->next;

　　while(p!=NULL)

　　{

　　delete p->pre;

　　p=p->next;

　　}

　　delete p_cache_list_near;

　　}

　　void LRUCache::detachNode(CacheNode *node)

　　{

　　node->pre->next=node->next;

　　node->next->pre=node->pre;

　　}

　　void LRUCache::addToFront(CacheNode *node)

　　{

　　node->next=p_cache_list_head->next;

　　p_cache_list_head->next->pre=node;

　　p_cache_list_head->next=node;

　　node->pre=p_cache_list_head;

　　}

　　int LRUCache::getValue(int key)

　　{

　　CacheNode *p=p_cache_list_head->next;

　　while(p->next!=NULL)

　　{

　　if(p->key == key) //catch node

　　{

　　detachNode(p);

　　addToFront(p);

　　return p->value;

　　}

　　p=p->next;

　　}

　　return -1;

　　}

　　bool LRUCache::putValue(int key,int value)

　　{

　　CacheNode *p=p_cache_list_head->next;

　　while(p->next!=NULL)

　　{

　　if(p->key == key) //catch node

　　{

　　p->value=value;

　　getValue(key);

　　return true;

　　}

　　p=p->next;

　　}

　　if(cache_real_size_ >= cache_size_)

　　{

　　cout << "free" <

　　p=p_cache_list_near->pre->pre;

　　delete p->next;

　　p->next=p_cache_list_near;

　　p_cache_list_near->pre=p;

　　}

　　p=new CacheNode();//(CacheNode *)malloc(sizeof(CacheNode));

　　if(p==NULL)

　　return false;

　　addToFront(p);

　　p->key=key;

　　p->value=value;

　　cache_real_size_++;

　　return true;

　　}

　　void LRUCache::displayNodes()

　　{

　　CacheNode *p=p_cache_list_head->next;

　　while(p->next!=NULL)

　　{

　　cout << " Key : " << p->key << " Value : " << p->value << endl;

　　p=p->next;

　　}

　　cout << endl;

　　}

　　说在后面的话

　　其实，程序还可以优化，首先，把数据int类型换成模板形式的通用类型，另外，数据查找的时候复杂度为O(n)，可以换成hash表来存数据，链表只做置换处理，这样查找添加的时候速度将快很多。