小編給大家分享一下如何使用c++實(shí)現(xiàn)常見緩存算法和LRU，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

成都創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比玉泉街道網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式玉泉街道網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋玉泉街道地區(qū)。費(fèi)用合理售后完善，十余年實(shí)體公司更值得信賴。

前言

對于web開發(fā)而言，緩存必不可少，也是提高性能最常用的方式。無論是瀏覽器緩存(如果是chrome瀏覽器，可以通過chrome:://cache查看)，還是服務(wù)端的緩存(通過memcached或者redis等內(nèi)存數(shù)據(jù)庫)。緩存不僅可以加速用戶的訪問，同時(shí)也可以降低服務(wù)器的負(fù)載和壓力。那么，了解常見的緩存淘汰算法的策略和原理就顯得特別重要。

常見的緩存算法

1. LRU (Least recently used) 最近最少使用，如果數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也更高。

2. LFU (Least frequently used) 最不經(jīng)常使用，如果一個(gè)數(shù)據(jù)在最近一段時(shí)間內(nèi)使用次數(shù)很少，那么在將來一段時(shí)間內(nèi)被使用的可能性也很小。

3. FIFO (Fist in first out) 先進(jìn)先出， 如果一個(gè)數(shù)據(jù)最先進(jìn)入緩存中，則應(yīng)該最早淘汰掉。

LRU緩存

像瀏覽器的緩存策略、memcached的緩存策略都是使用LRU這個(gè)算法，LRU算法會將近期最不會訪問的數(shù)據(jù)淘汰掉。LRU如此流行的原因是實(shí)現(xiàn)比較簡單，而且對于實(shí)際問題也很實(shí)用，良好的運(yùn)行時(shí)性能，命中率較高。下面談?wù)勅绾螌?shí)現(xiàn)LRU緩存：

1. 新數(shù)據(jù)插入到鏈表頭部

2. 每當(dāng)緩存命中（即緩存數(shù)據(jù)被訪問），則將數(shù)據(jù)移到鏈表頭部

3. 當(dāng)鏈表滿的時(shí)候，將鏈表尾部的數(shù)據(jù)丟棄

LRU Cache具備的操作：

1. set(key,value)：如果key在hashmap中存在，則先重置對應(yīng)的value值，然后獲取對應(yīng)的節(jié)點(diǎn)cur，將cur節(jié)點(diǎn)從鏈表刪除，并移動到鏈表的頭部；若果key在hashmap不存在，則新建一個(gè)節(jié)點(diǎn)，并將節(jié)點(diǎn)放到鏈表的頭部。當(dāng)Cache存滿的時(shí)候，將鏈表最后一個(gè)節(jié)點(diǎn)刪除即可。

2. get(key)：如果key在hashmap中存在，則把對應(yīng)的節(jié)點(diǎn)放到鏈表頭部，并返回對應(yīng)的value值；如果不存在，則返回-1。

LRU的c++實(shí)現(xiàn)

LRU實(shí)現(xiàn)采用雙向鏈表 + Map 來進(jìn)行實(shí)現(xiàn)。這里采用雙向鏈表的原因是：如果采用普通的單鏈表，則刪除節(jié)點(diǎn)的時(shí)候需要從表頭開始遍歷查找，效率為O(n)，采用雙向鏈表可以直接改變節(jié)點(diǎn)的前驅(qū)的指針指向進(jìn)行刪除達(dá)到O(1)的效率。使用Map來保存節(jié)點(diǎn)的key、value值便于能在O(logN)的時(shí)間查找元素,對應(yīng)get操作。

雙鏈表節(jié)點(diǎn)的定義：

struct CacheNode {
 int key;  // 鍵
 int value; // 值
 CacheNode *pre, *next; // 節(jié)點(diǎn)的前驅(qū)、后繼指針
 CacheNode(int k, int v) : key(k), value(v), pre(NULL), next(NULL) {}
};

對于LRUCache這個(gè)類而言，構(gòu)造函數(shù)需要指定容量大小

LRUCache(int capacity)
{
 size = capacity;  // 容量
 head = NULL;   // 鏈表頭指針
 tail = NULL;   // 鏈表尾指針
}

雙鏈表的節(jié)點(diǎn)刪除操作：

void remove(CacheNode *node)
{
 if (node -> pre != NULL)
 {
 node -> pre -> next = node -> next;
 }
 else
 {
 head = node -> next;
 }
 if (node -> next != NULL)
 {
 node -> next -> pre = node -> pre;
 }
 else
 {
 tail = node -> pre;
 }
}

將節(jié)點(diǎn)插入到頭部的操作：

void setHead(CacheNode *node)
{
 node -> next = head;
 node -> pre = NULL;

 if (head != NULL)
 {
 head -> pre = node;
 }
 head = node;
 if (tail == NULL)
 {
 tail = head;
 }
}

get(key)操作的實(shí)現(xiàn)比較簡單，直接通過判斷Map是否含有key值即可，如果查找到key，則返回對應(yīng)的value，否則返回-1;

int get(int key)
{
 map::iterator it = mp.find(key);
 if (it != mp.end())
 {
 CacheNode *node = it -> second;
 remove(node);
 setHead(node);
 return node -> value;
 }
 else
 {
 return -1;
 }
}

set(key, value)操作需要分情況判斷。如果當(dāng)前的key值對應(yīng)的節(jié)點(diǎn)已經(jīng)存在，則將這個(gè)節(jié)點(diǎn)取出來，并且刪除節(jié)點(diǎn)所處的原有的位置，并在頭部插入該節(jié)點(diǎn)；如果節(jié)點(diǎn)不存在節(jié)點(diǎn)中，這個(gè)時(shí)候需要在鏈表的頭部插入新節(jié)點(diǎn)，插入新節(jié)點(diǎn)可能導(dǎo)致容量溢出，如果出現(xiàn)溢出的情況，則需要刪除鏈表尾部的節(jié)點(diǎn)。

void set(int key, int value)
{
 map::iterator it = mp.find(key);
 if (it != mp.end())
 {
 CacheNode *node = it -> second;
 node -> value = value;
 remove(node);
 setHead(node);
 }
 else
 {
 CacheNode *newNode = new CacheNode(key, value);
 if (mp.size() >= size)
 {
  map::iterator iter = mp.find(tail -> key);
  remove(tail);
  mp.erase(iter);
 }
 setHead(newNode);
 mp[key] = newNode;
 }
}

看完了這篇文章，相信你對“如何使用c++實(shí)現(xiàn)常見緩存算法和LRU”有了一定的了解，如果想了解更多相關(guān)知識，歡迎關(guān)注創(chuàng)新互聯(lián)網(wǎng)站建設(shè)公司行業(yè)資訊頻道，感謝各位的閱讀！

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站www.cdcxhl.com，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

本文名稱：如何使用c++實(shí)現(xiàn)常見緩存算法和LRU-創(chuàng)新互聯(lián)
URL鏈接：http://weahome.cn/article/psicc.html