最近在工作中需要用到LRU cache用作緩存來(lái)提高性能，經(jīng)過(guò)查閱各種資料，了解了其運(yùn)行的機(jī)制，如下：

LRU cache可以用于在內(nèi)存中保持當(dāng)前的熱點(diǎn)數(shù)據(jù)，下面實(shí)現(xiàn)一個(gè)有大小限制的lru cache，相關(guān)如下：

????1. 模板化；

????2. 利用std::unordered_map實(shí)現(xiàn)o(1)查找，利用std::list實(shí)現(xiàn)o(1)刪除 (雙鏈表+hash表）；

????3. 用map保持key和結(jié)點(diǎn)在鏈表中的位置(iterator)

????4. 需要同時(shí)考慮如下情況：

????????put操作：?

?????????????（1） 如果當(dāng)前key存在，則將對(duì)于的結(jié)點(diǎn)剪切到鏈表的頭部，同時(shí)更新哈希表中value的值；

?????????????（2） 如果當(dāng)前key不存在于hash表中，且元素個(gè)數(shù)已經(jīng)達(dá)到最大值，則刪除鏈表的最后一個(gè)結(jié)點(diǎn)，同時(shí)把新結(jié)點(diǎn)插入到鏈表的頭部，同時(shí)更新hash表（增加新節(jié)點(diǎn)和刪除舊結(jié)點(diǎn)表項(xiàng)）；

????????get操作：

?????????????（1）檢查當(dāng)前hash表中是否有該key，如果存在，則將該key對(duì)應(yīng)的結(jié)點(diǎn)move到list的頭部,并同步獲取map的value；

?????????????（2）如果hash表中不存在該key，則返回false；

主要的代碼如下：

? ? void put(const key_t& key, const value_t& value) {
? ? ? ? if (cache_items_map_.count(key) > 0) { // find the key
? ? ? ? ? ? list_iterator_t iter = cache_items_map_[key];
? ? ? ? ? ? iter->second = value;
? ? ? ? ? ? cache_items_list_.splice(cache_items_list_.begin(), cache_items_list_, iter); // move to header
? ? ? ? } else {
? ? ? ? ? ? if (cache_items_list_.size() >= max_size_) {
? ? ? ? ? ? ? ? cache_items_map_.erase(cache_items_list_.back().first); ?// remove the last element from list
? ? ? ? ? ? ? ? cache_items_list_.pop_back(); // remove the last element in list
? ? ? ? ? ? }

? ? ? ? ? ? //insert new element to map and list
? ? ? ? ? ? cache_items_list_.push_front(key_value_pair_t(key, value));
? ? ? ? ? ? cache_items_map_[key] = cache_items_list_.begin();
? ? ? ? }
? ? }

? ? bool get(const key_t& key, value_t& value) {
? ? ? ? map_iterator_t it = cache_items_map_.find(key);
? ? ? ? if (it == cache_items_map_.end()) {
? ? ? ? ? ? return false;
? ? ? ? } else {
? ? ? ? ? ? cache_items_list_.splice(cache_items_list_.begin(), cache_items_list_, it->second);
? ? ? ? ? ? value = ?it->second->second;
? ? ? ? ? ? return true;
? ? ? ? }
? ? }

? ? std::list<key_value_pair_t> cache_items_list_;
? ? boost::unordered_map<key_t, list_iterator_t> cache_items_map_;
? ? int64_t max_size_;
經(jīng)過(guò)測(cè)試，達(dá)到了預(yù)期的結(jié)果。

總結(jié)

以上是生活随笔為你收集整理的一种简单的LRU cache设计 C++的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。