C++培训LRU是什么，相信很多人对这个都还不是很了解!今天，小蓝就给大家介绍LRUCache的简单C++实现
LRUCache是一个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的节点数。
先定义一个存数据的节点数据结构
typedefstruct_Node_{ intkey;//键 intvalue;//数据 struct_Node_*next;//下一个节点 struct_Node_*pre;//上一个节点 }CacheNode; 类定义： classLRUCache{ public: LRUCache(intcache_size=10);//构造函数，默认cache大小为10 ~LRUCache();//析构函数 intgetValue(intkey);//获取值 boolputValue(intkey,intvalue);//写入或更新值 voiddisplayNodes();//辅助函数，显示所有节点 private: intcache_size_;//cache长度 intcache_real_size_;//目前使用的长度 CacheNode*p_cache_list_head;//头节点指针 CacheNode*p_cache_list_near;//尾节点指针 voiddetachNode(CacheNode*node);//分离节点 voidaddToFront(CacheNode*node);//将节点插入到第一个 }; 类实现： LRUCache:RUCache(intcache_size) { cache_size_=cache_size; cache_real_size_=0; p_cache_list_head=newCacheNode(); p_cache_list_near=newCacheNode(); 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) { deletep-pre; p=p-next; } deletep_cache_list_near; } voidLRUCache::detachNode(CacheNode*node) { node-pre-next=node-next; node-next-pre=node-pre; } voidLRUCache::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; } intLRUCache::getValue(intkey) { CacheNode*p=p_cache_list_head-next; while(p-next!=NULL) { if(p-key==key)//catchnode { detachNode(p); addToFront(p); returnp-value; } p=p-next; } return-1; } boolLRUCache::putValue(intkey,intvalue) { CacheNode*p=p_cache_list_head-next; while(p-next!=NULL) { if(p-key==key)//catchnode { p-value=value; getValue(key); returntrue; } p=p-next; } if(cache_real_size_=cache_size_) { cout"free" p=p_cache_list_near-pre-pre; deletep-next; p-next=p_cache_list_near; p_cache_list_near-pre=p; } p=newCacheNode();//(CacheNode*)malloc(sizeof(CacheNode)); if(p==NULL) returnfalse; addToFront(p); p-key=key; p-value=value; cache_real_size_++; returntrue; } voidLRUCache::displayNodes() { CacheNode*p=p_cache_list_head-next; while(p-next!=NULL) { cout"Key:"p-key"Value:"p-valueendl; p=p-next; } coutendl; }
说在后面的话
其实，程序还可以优化，首先，把数据int类型换成模板形式的通用类型，另外，数据查找的时候复杂度为O(n)，可以换成hash表来存数据，链表只做置换处理，这样查找添加的时候速度将快很多。
治疗白癜风的医院白癜风能治好吗