前言
本文首发于我的公众号：码农手札，主要介绍linux下c++开发的知识包括网络编程的知识同时也会介绍一些有趣的算法题，欢迎大家关注，利用碎片时间学习一些编程知识，冰冻三尺非一日之寒，让我们一起加油！
实习过程中遇到一个场景，在多线程下用到一个缓存当前分析的结果的map，当时只是用了一个map来解决这个问题，但是当时就觉得这个办法不是很好，因为分析结果基本上是很快就会被更新掉的，但是如果一个结果被用到，说明其很可能会被继续用到，分析了一下场景，我们就能很明了的想到，应该是用LRU来解决这个问题，LRU是一种被广泛使用的缓存算法，在操作系统以及一些开源的库中都能见到其身影，这里我们也对LRU也做出一个简单的拓展，实现一个模板LRUC_Cache类
实现代码
#include <list>
#include <mutex>
#include <unordered_map>
template <typename T> using LISTT = std::list<T>;
template <typename T, typename Y>
using PAIRTL = std::pair<Y, typename LISTT<T>::iterator>;
template <typename T, typename Y>
using UMAPTP = std::unordered_map<T, PAIRTL<T, Y>>;
template <typename T, typename Y> class LRU_Cache {
public:
LRU_Cache(const size_t &capacity) : capacity_(capacity) {}
Y Get(const T &key) {
std::lock_guard<std::mutex> lck(cache_mutex_);
auto it = cache_.find(key);
if (it == cache_.end()) {
return Y();
}
touch(it);
return it->second.first;
}
void Put(const T &key, const Y &value) {
std::lock_guard<std::mutex> lck(cache_mutex_);
auto it = cache_.find(key);
if (it != cache_.end()) {
touch(it);
} else {
if (cache_.size() == capacity_) {
cache_.erase(elements_.back());
elements_.pop_back();
}
elements_.push_front(key);
}
cache_[key] = {value, elements_.begin()};
}
private:
void touch(typename UMAPTP<T, Y>::iterator it) {
///注意这里不能加锁，否则就死锁了，因为这个函数不会被单独调用，总是在有锁的情况下
///被调用，所以函数本身不需要再加锁
T key = it->first;
elements_.erase(it->second.second);
elements_.push_front(key);
it->second.second = elements_.begin();
}
size_t capacity_;
///由于element_和cache_都是被同时访问，因此一个锁就够了
std::mutex cache_mutex_;
LISTT<T> elements_;
UMAPTP<T, Y> cache_;
};
简单解释
不考虑多线程的情况下（其实考虑也没啥，只有一个锁哈哈），我们使用来一个list来储存所有的key，使用unorderedmap来保存key，然后value是一个pair，pair的首元素是value，次元素是指向key在list中的位置的迭代器，这里list的作用其实只是标示元素的顺序，因为lru算法要求每当一个元素被access，它就应该排到队列的最前端，当lru的缓存已经满了的时候，就应该删除队列中最后面的元素，因为这个元素是least_recently_used(lru),unorderedmap的作用也就很明显了，一方面储存value，一方面储存key在list中对应的迭代器，方便进行删除操作。
至于实现的话，这里有个小技巧，就是抽离出了一个touch函数，这个函数的作用是根据一个确定已经在缓存中的元素的key，访问一次，其目的就是改变元素在队列中的位置，同时unorderedmap中的迭代器也需要更新，本质上就是把元素挪到队列头。
其他的应该都比较直接，反而模板这一块由于自己不太熟，写那个using声明弄了蛮久，说起来还怪不好意思
总结
这个实现虽然简单，但是基本效果还是能达到的，我自己也做了简单的测试，可能不是很全面，但是基本还是能用的，毕竟代码也相对比较简单（笑），
网友评论