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

Boost.MultiIndexで動的な並び順を持たせる

C++

Boost.MultiIndexでは、ordered indices, random access indices, sequenced indicesなどのインデックスを指定できますが、これらのインデックスは不変であるため、通常の手段では並び順をあとから変えることはできません。

typedef multi_index_container<
    int,
    indexed_by<random_access<> >
> container;

container c;
boost::random_shuffle(c); // エラー!書き換えできない

こういった動的な並び順をインデックスとして持たせるために、rearrangeというメンバ関数が用意されています。
以下がその使用例です。2つめのrandom access indicesを、動的な並び順として扱えるようにしています。

#include <iostream>
#include <vector>
#include <boost/range/algorithm.hpp>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/assign/list_of.hpp>
#include <boost/foreach.hpp>
#include <boost/ref.hpp>

using namespace boost::multi_index;
typedef multi_index_container<
    int,
    indexed_by<
        random_access<>,
        random_access<>
    >
> container;

int main()
{
    container c = boost::assign::list_of(1)(2)(3)(4)(5);

    std::vector<boost::reference_wrapper<const int> > v;
    BOOST_FOREACH(const int& i, c) {
        v.push_back(boost::cref(i));
    }

    boost::random_shuffle(v);
    c.get<1>().rearrange(v.begin());

    boost::for_each(c.get<0>(), [](int x) { std::cout << x; }); std::cout << std::endl;
    boost::for_each(c.get<1>(), [](int x) { std::cout << x; }); std::cout << std::endl;
}
12345
52431

1つめのrandom access indicesの並び順はそのままに、
2つめのrandom access indicesの方だけが、random_shuffleを適用した動的な並び順になっていることがわかります。


rearrangeを使用するには、multi_index_containerの要素を一旦、reference wrapperのコンテナに持たせてそのコンテナに対して並び順の操作を行う必要があります。
このあたりは、トランプのシャッフルが例として提供されてるので見てみてください。

http://www.boost.org/doc/libs/1_44_0/libs/multi_index/doc/examples.html#example11


ちなみに、rearrangeには引数としてイテレータを渡していますが、reverse iteratorを渡すこともできます。

c.get<1>().rearrange(v.rbegin());

Rangeを渡せるとRangeアダプタが使えてさらに良いのですが、rearrangeは元々テンプレートでイテレータを取っているので、Rangeをとれるようにするには別名のメンバ関数を用意する必要がありますね。並び替え用のRangeアダプタはBoost.Rangeにはないのでほんとに使うかどうかはわかりませんが…。