http://boost-consulting.com/boost/libs/multi_index/doc/index.html
すごい面白そうなライブラリが提案されているじゃんとか思って見てみたらすでにacceptされている模様．しかしどこを探してもこのMultiIndexのレビューが一向に見つからない．で，よくよく見てみるとBoost.IndexedSetがレビューの過程で改名されたものだということが判明．うーむ，名前は重要だなぁ．IndexedSetって名前だからてっきりindex付いただけのsetをイメージしてたよ・・・．MultiIndexって名前になってライブラリの機能が正確に想像できるようになったので途端に興味が沸いてきた．
要するに複数のindex付けの基準を持てるコンテナという提案のようである．例えばvectorに対して要素に基づいた順序（例えば小さい順）でソートされているように「見せかける」ことが出来る．これだけだとAssocVectorと変わりないけれど，MultiIndexの面白いところはSequence（任意の場所での要素の挿入・削除が可能なコンテナ）としてもアクセスできるところ．多分，2つ以上の順序を持たせたりvector以外のコンテナ（連想含む）に適用できたりしているに違いない・・・と，ドキュメントを読む前からライブラリの中身を予想＆期待．
実装を読んでない（以前にドキュメントすらろくに読んでいない）けれど，多分置換（permutation）を表現するindexの配列を余分に持っていてそれ経由でアクセスしているのだと予想．（大抵こういった予想は良い意味で裏切られるんですが．）
ちなみに，上でごちゃごちゃ書いていることを簡単に説明すると以下のようになります．
int a[5] = {0,1,2,3,4}; // ベースとなる配列
int p1[5] = {4,3,2,1,0}; // 置換を表現する配列その1
int p2[5] = {2,1,0,3,4}; // 置換を表現する配列その2
for(int i = 0; i < 5; ++i){
std::cout << a[i] << std::endl; // aに直接アクセスすれば当然普通に並んでいます．
}
std::cout << std::endl;
// p1を通してaにアクセスすると，まるでaが
// {a[4],a[3],a[2],a[1],a[0]}と逆順に並んでいるように見せかけること出来ます．
for(int i = 0; i < 5; ++i){
std::cout << a[p1[i]] << std::endl;
}
std::cout << std::endl;
// 同じようにp2を通してaにアクセスすると，
// aが{a[2],a[1],a[0],a[3],a[4]}と並んでいるように見えます．
for(int i = 0; i < 5; ++i){
std::cout << a[p2[i]] << std::endl;
}この手法を使って，ベースのコンテナの要素の順序にまったく触れることなく順序付けの基準を同時に複数持たせることが可能になります．
この手法は他でもよく使われます．自分の経験では行列の計算で行あるいは列の交換を定数時間で計算する（行（列）の要素全部を交換しなくて済む）ようにするために使ったことがありました．また，RDBの文脈などでも多用されています．
・・・って，ここまで書いておいて実際実装読んだら「全然違う手法でした」なんてことになったら嫌だにゃ〜．
あれ？っていうか・・・
この実装でSorted Associative Containerの複雑性の要件全て満たすコンテナ作れちゃうような・・・．RB-Treeでの実装と（脳内で）比較すると，空間的には絶対に有利だし一部の操作（iteratorによるtraverseとか）がこの実装のほうが速くなるような・・・．要素・上下限探索は実測してみないとどちらが速いかは分からないけど．
・・・ちゃちゃっと試してみようかな．
「全然違う手法でした」
と，とりあえずノードベースコンテナだということだけは分かった・・・．
ダメじゃん
だから上のやり方だと要素の挿入にO(N)かかるからダメだって．＞俺
しかも上のようにしたいならboost::permutation_iteratorがあるっつーの．
#include <iostream>
#include <boost/random.hpp>
#include <boost/iterator/counting_iterator.hpp>
#include <boost/iterator/permutation_iterator.hpp>
#include <boost/lambda/lambda.hpp>
int main()
{
using namespace ::std;
using namespace ::boost;
using namespace ::boost::lambda;
mt19937 rnd_gen(10);
uniform_smallint<> rnd_dst(0, 100);
variate_generator<mt19937, uniform_smallint<> >
mt_rnd(rnd_gen, rnd_dst);
// 乱数を保持したコンテナを作成
vector<int> v(100);
generate(v.begin(), v.end(), mt_rnd);
typedef vector<int>::size_type size_type;
// vをソートしているように見せかける置換(ビュー)を作成
vector<int> sorted_view(v.size());
copy(counting_iterator<int>(0), counting_iterator<int>(v.size()),
sorted_view.begin());
sort(sorted_view.begin(), sorted_view.end(),
var(v)[_1] < var(v)[_2]);
cout << "本来のコンテナ" << endl;
copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
cout << endl;
cout << endl;
cout << "ソートしているように見せかけてみる" << endl;
copy(make_permutation_iterator(v.begin(), sorted_view.begin()),
make_permutation_iterator(v.begin(), sorted_view.end()),
ostream_iterator<int>(cout, " "));
cout << endl;
}
