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表來存數據，鏈表只做置換處理，這樣查找添加的時候速度將快很多。