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 = {, , , };

  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 ;

　　关于LRU cache的使用，示例代码如下：

#include "stout/cache.hpp"

#include <iostream>

#include <string>

int main()

{

  Cache<int, std::string> a();

  a.put(, "one");

  a.put(, "two");

  a.put(, "three");

  std::cout << a << std::endl;

  a.get();

  std::cout << a << std::endl;

  a.put(, "four");

  std::cout << a << std::endl;

  return ;

}

　　注：在使用过程中发现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类

最新文章

热门文章