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

專(zhuān)注于為中小企業(yè)提供成都做網(wǎng)站、成都網(wǎng)站建設(shè)服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)東港免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動(dòng)了上1000家企業(yè)的穩(wěn)健成長(zhǎng)，幫助中小企業(yè)通過(guò)網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。

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

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

LRU 基本算法描述

前提：

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

要求：

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

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

緩存數(shù)量有限，最長(zhǎng)時(shí)間沒(méi)被訪問(wèn)的數(shù)據(jù)應(yīng)該置換出緩存

算法：

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

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

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

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

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

typedef struct _Node_{

int key; //鍵

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

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

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

}CacheNode;

類(lèi)定義：

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); //寫(xiě)入或更新值

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

private:

int cache_size_; //cache長(zhǎng)度

int cache_real_size_; //目前使用的長(zhǎng)度

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)插入到第一個(gè)

};

類(lèi)實(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;

}

說(shuō)在后面的話

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