首页 > 代码库 > stout代码分析之八:cache类
stout代码分析之八:cache类
stout中实现了LRU cache。cache的成员如下:
public: typedef std::list<Key> list; typedef std::tr1::unordered_map< Key, std::pair<Value, typename list::iterator> > map;
可以看到map的第二项除了value之外,又有一个指向key的迭代器,这种设计有利于提高cache LRU操作的效率:当查询某个key时,同时获取value和key在list中的迭代器,可方便的将该key和ist中最后一个元素进行交换,如下所示:
void use(const typename map::iterator& i) { // Move the "pointer" to the end of the lru list. keys.splice(keys.end(), keys, (*i).second.second); // Now update the "pointer" so we can do this again. (*i).second.second = --keys.end(); }
这里使用了list.splice交换两个元素的位置。splice的用法如下:
#include <list>#include <iostream>#include <algorithm>int main(){ std::list<int> a = {10, 100, 1000, 10000}; for_each(begin(a), end(a), [](int n){std::cout << n << std::endl;}); a.splice(end(a), a, begin(a)); for_each(begin(a), end(a), [](int n){std::cout << n << std::endl;}); return 0;
关于LRU cache的使用,示例代码如下:
#include "stout/cache.hpp"#include <iostream>#include <string>int main(){ Cache<int, std::string> a(3); a.put(1, "one"); a.put(2, "two"); a.put(3, "three"); std::cout << a << std::endl; a.get(2); std::cout << a << std::endl; a.put(4, "four"); std::cout << a << std::endl; return 0;}
注:在使用过程中发现cache重载<<操作符的一个编译错误,
template <typename Key, typename Value>std::ostream& operator << ( std::ostream& stream, const cache<Key, Value>& c){ typename cache<Key, Value>::list::const_iterator i1; for (i1 = c.keys.begin(); i1 != c.keys.end(); i1++) { stream << *i1 << ": "; typename cache<Key, Value>::map::const_iterator i2; i2 = c.values.find(*i1); CHECK(i2 != c.values.end()); stream << *i2 << std::endl; } return stream;}
解决方法:将倒数第三行的
stream << *i2 << std::endl;
改成
stream << i2->second.first << std::endl;
即可。
stout代码分析之八:cache类
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。