C++教程：LRUCache的簡單C++實(shí)現(xiàn)

　　C++培訓(xùn)LRU是什么，相信很多人對這個都還不是很了解!今天，小編就給大家介紹LRU Cache 的簡單 C++ 實(shí)現(xiàn)

　　LRU Cache是一個Cache的置換算法，含義是“最近最少使用”，把滿足“最近最少使用”的數(shù)據(jù)從Cache中剔除出去，并且保證Cache中第一個數(shù)據(jù)是最近剛剛訪問的，因?yàn)檫@樣的數(shù)據(jù)更有可能被接下來的程序所訪問。

　　LRU的應(yīng)用比較廣泛，最基礎(chǔ)的內(nèi)存頁置換中就用了，對了，這里有個概念要清楚一下，Cache不見得是CPU的高速緩存的那個Cache，這里的Cache直接翻譯為緩存，就是兩種存儲方式的速度有比較大的差別，都可以用Cache緩存數(shù)據(jù)，比如硬盤明顯比內(nèi)存慢，所以常用的數(shù)據(jù)我們可以Cache在內(nèi)存中。

　　LRU 基本算法描述

　　前提：

　　由于我只是簡單實(shí)現(xiàn)一下這個算法，所以數(shù)據(jù)都用int代替，下一個版本會改成模板形式的，更加通用。

　　要求：

　　只提供兩個接口，一個獲取數(shù)據(jù)getValue(key),一個寫入數(shù)據(jù)putValue(key,value)

　　無論是獲取還是寫入數(shù)據(jù)，當(dāng)前這個數(shù)據(jù)要保持在最容易訪問的位置

　　緩存數(shù)量有限，最長時(shí)間沒被訪問的數(shù)據(jù)應(yīng)該置換出緩存

　　算法：

　　為了滿足上面幾個條件，實(shí)際上可以用一個雙向鏈表來實(shí)現(xiàn)，每次訪問完數(shù)據(jù)(不管是獲取還是寫入)，調(diào)整雙向鏈表的順序，把剛剛訪問的數(shù)據(jù)調(diào)整到鏈表的最前方，以后再訪問的時(shí)候速度將最快。

　　為了方便，提供一個頭和一個尾節(jié)點(diǎn)，不存具體的數(shù)，鏈表的基本形式如下面的這個簡單表述

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

　　OK，就這么些，比較簡單，實(shí)現(xiàn)起來也不難，用c++封裝一個LRUCache類，類提供兩個方法，分別是獲取和更新，初始化類的時(shí)候傳入Cache的節(jié)點(diǎn)數(shù)。

　　先定義一個存數(shù)據(jù)的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)

　　typedef struct _Node_{

　　int key; //鍵

　　int value; //數(shù)據(jù)

　　struct _Node_ *next; //下一個節(jié)點(diǎn)

　　struct _Node_ *pre; //上一個節(jié)點(diǎn)

　　}CacheNode;

　　類定義：

　　class LRUCache{

　　public:

　　LRUCache(int cache_size=10); //構(gòu)造函數(shù)，默認(rèn)cache大小為10

　　~LRUCache(); //析構(gòu)函數(shù)

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

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

　　void displayNodes(); //輔助函數(shù)，顯示所有節(jié)點(diǎn)

　　private:

　　int cache_size_; //cache長度

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

　　CacheNode *p_cache_list_head; //頭節(jié)點(diǎn)指針

　　CacheNode *p_cache_list_near; //尾節(jié)點(diǎn)指針

　　void detachNode(CacheNode *node); //分離節(jié)點(diǎn)

　　void addToFront(CacheNode *node); //將節(jié)點(diǎn)插入到第一個

　　};

　　類實(shí)現(xiàn)：

　　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;

　　}

　　說在后面的話

　　其實(shí)，程序還可以優(yōu)化，首先，把數(shù)據(jù)int類型換成模板形式的通用類型，另外，數(shù)據(jù)查找的時(shí)候復(fù)雜度為O(n)，可以換成hash表來存數(shù)據(jù)，鏈表只做置換處理，這樣查找添加的時(shí)候速度將快很多。