キャッシュのデータ構造 with Boost.MultiIndex
JavaのLRUMapが便利そうだったのでC++でそれに相当するものがないかなーと調べてみたら
「それBoost.MultiIndexでできるよ」と書いてたのでやってみました。
古いものから順に消せるハッシュマップです。
#include <cassert> #include <iostream> #include <utility> #include <string> #include <boost/multi_index_container.hpp> #include <boost/multi_index/hashed_index.hpp> #include <boost/multi_index/sequenced_index.hpp> #include <boost/multi_index/member.hpp> #include <boost/foreach.hpp> #define foreach BOOST_FOREACH using namespace boost::multi_index; typedef std::pair<std::string, int> value_type; typedef multi_index_container< value_type, indexed_by< hashed_unique<member<value_type, std::string, &value_type::first> >, sequenced<> > > container; int main() { container c; c.insert(value_type("c", 1)); c.insert(value_type("a", 2)); c.insert(value_type("d", 3)); c.insert(value_type("e", 4)); c.insert(value_type("b", 5)); // hash mapとして使う container::nth_index<0>::type& assoc = c.get<0>(); assert(assoc.find("a")->second == 2); // 一番古いのを消す container::nth_index<1>::type& seq = c.get<1>(); seq.erase(seq.begin()); foreach (const value_type& i, c) { std::cout << i.first << "," << i.second << std::endl; } }
a,2 b,5 d,3 e,4