読者です 読者をやめる 読者になる 読者になる

キャッシュのデータ構造 with Boost.MultiIndex

C++

キャッシュのデータ構造 - はじめてのにき


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