boost1.32.0から追加されたライブラリの一つ、 multi_index_containerを紹介します。 この解説は、正式リリースの幾分か前(04/08/27頃)に書かれたものであるため、 一部詳細が違っているかもしれませんのでご了承ください。
STLに搭載されているset/multisetは、要素中のある値に基づいてソートされた状態で格納されています。 例えば、
001 002 #include <set> 003 #include <string> 004 005 struct book { 006 std::string isbn; 007 std::string title; 008 009 bool operator<(const book& r) const { 010 return isbn < r.isbn; 011 } 012 }; 013 014 typedef std::set<book> book_set_t; 015 book_set_t book_set;
のように、構造体bookとコンテナbook_set_tを定義したとします。
このとき、book_setはisbnでソートされています。
ここで唐突に、titleでソートされたbookのコンテナが欲しくなったとしたらどうするでしょうか？
一番安易な方法は、次のようなものでしょう。
001 002 #include <vector> 003 #include <algorithm> 004 005 typedef std::vector<book> book_vector_t; 006 book_vector_t book_vector(book_set.size()); 007 008 struct book_title_comp { 009 bool operator()(const book& lhs, const book& rhs) const { 010 return lhs.title < rhs.title; 011 } 012 }; 013 014 std::copy(book_set.begin(), book_set.end(), book_vector.begin()); 015 std::sort(book_vector.begin(), book_vector.end(), book_title_comp());
意外と、手間です。さらにこの方法では、構造体のコピーが大量に発生してしまい、 実行効率の面から見ても美しいとは言えません。 多少工夫すれば、構造体のコピーはなくす事ができますが、さらに面倒な記述が必要となります。
boost::multi_index_containerは、このような問題をスマートに解決するコンテナを提供してくれます。
VC7.0以前のコンパイラなど、テンプレート関連の機能が完全に実装されていないコンパイラの場合、 一部の機能を利用する際に特殊な記法を利用する必要があります。 こちらと照らし合わせつつ読んでください。
このライブラリは、特別にビルドしたりする必要はありません。 ヘッダーファイルをインクルードするだけで使用できます。
multi_index_containerの使い方は見た目がちょっと複雑ですが、慣れてしまえば簡単なものです。
先ほどのbook構造体を格納して、
isbnとtitleでソートするmulti_index_containerをtypedefしてみましょう。
なおこれ以降、特に注釈のない識別子はboost::multi_index名前空間で宣言されています。
001 002 #include <string> 003 004 #include <boost/multi_index_container.hpp> 005 #include <boost/multi_index/ordered_index.hpp> 006 #include <boost/multi_index/key_extractors.hpp> 007 using namespace boost::multi_index; 008 009 struct book { 010 std::string isbn; 011 std::string title; 012 013 bool operator<(const book& r) const { 014 return isbn < r.isbn; 015 } 016 }; 017 018 typedef multi_index_container< 019 book, 020 indexed_by< 021 ordered_unique<identity<book> >, 022 ordered_non_unique<member<book, std::string, &book::title> > 023 > 024 > book_set_t;
18行目から24行目がコンテナの型定義にあたります。 詳しく見ていきましょう。
018 typedef multi_index_container< ... 024 >
ヘッダー<boost/multi_index_container.hpp>で定義されているコンテナ本体です。
テンプレート引数は、1番目に格納する型名(この場合はbook構造体)、
2番目にソートの方法(詳細は後述)、3番目にallocater(省略可能、普通は省略します)を指定します。
020 indexed_by< 021 ordered_unique<identity<book> >, 022 ordered_non_unique<member<book, std::string, &book::title> > 023 >
順序付けの方法を指定します。indexed_by<>で囲って、
使用したい順序付けの方法を複数指定することができます。
この例では、2種類の順序付けの方法を指定しています。
順序付けの方法はいくつでも指定できるというわけでもなく、
マニュアルには、The maximum number of elements of an indexed_by sequence is implementation defined.
とあります。
実装依存で上限が決まっているようですが、
その上限とは別に、VC7.1は4つ以上指定するとほぼ確実にfatal errorを出力してくださいますので、
事実上上限は3つと考えて差し支えないでしょう。
021 ordered_unique<...>, 022 ordered_non_unique<...>
setとmultisetの違いと同じようなものです。 一つ目の順序付けでは全ての要素がユニーク(一意)であることを示し、 二つ目の順序付けでは重複する要素が存在するかもしれないことを示しています。
ヘッダー<boost/multi_index/ordered_index.hpp>で定義されています。
021 identity<book>;
順序付け時に、直接book構造体を<演算子で比較する事を示します。
この例では、book::operator<()で順序付けを行い、
結果としてisbnでソートされることになります。
注意: identityという識別子は、namespace boost::multi_indexだけでなく、
STLPortの<functional>でも使用されています。
これら二つの名前を衝突させないように、using宣言・ディレクティブを使用する際は十分に注意してください。
ヘッダー<boost/multi_index/key_extractors.hpp>で定義されています。
022 member<book, std::string, &book::title>
順序付け時に、book構造体のメンバ変数titleを比較する事を示します。 1番目のテンプレート引数にはコンテナに入れる型の名前、 2番目のテンプレート引数には比較に使用する型の名前、 3番目のテンプレート引数には比較に使用するメンバ変数を指定します。
ヘッダー<boost/multi_index/key_extractors.hpp>で定義されています。
先ほど型定義を行なったbook_set_tを実際に使用します。
001 002 book_set_t books; 003 004 // isbnで順序付けされたコンテナ。 005 book_set_t::nth_index<0>::type& isbn_set = books.get<0>(); 006 007 // 通常のコンテナと同様に扱える。 008 std::copy(isbn_set.begin(), isbn_set.end(), std::ostream_iterator(std::cout)); 009 // 省略記法 010 // std::copy(books.begin(), books.end(), std::ostream_iterator(std::cout)); 011 012 // titleで順序付けされたコンテナ 013 book_set_t::nth_index<1>::type& title_set = books.get<1>(); 014 015 book effectivecpp = { "4756118089" , "Effective C++" }; 016 // あるコンテナへの変更は即時に他のコンテナにも伝播する。 017 title_set.insert(effectivecpp); 018 if(isbn_set.count() == 1) { 019 std::cout << "Successfully effected!" << std::endl; 020 }
実際に操作するコンテナは、get<>()メソッドで取得できます。
テンプレート引数には使用したい順序付けのインデックス
(indexed_byで指定したもの、インデックスは0から始まる)を指定します。
また、そのコンテナの型はnth_index<>::typeで取得できます。
ここで、コンテナは参照で受け取る必要があるという点に注意してください。
このコンテナは、std::set/multisetと同様の使い方ができるようです。
省略記法も存在します。
0番目のコンテナへのアクセスは、
multi_index_container<>クラスのインスタンス(この場合はbooks)から直接行えます。
先ほどの例ではメンバ変数の値でソートさせていましたが、 当然メンバ関数の返り値でソートすることも可能です。
001 002 #include <string> 003 004 #include <boost/multi_index_container.hpp> 005 #include <boost/multi_index/ordered_index.hpp> 006 #include <boost/multi_index/key_extractors.hpp> 007 using namespace boost::multi_index; 008 009 struct book { 010 std::string isbn; 011 std::string title; 012 013 bool operator<(const book& r) const { 014 return isbn < r.isbn; 015 } 016 017 std::string& getTitle(void) { return title; } 018 }; 019 020 typedef multi_index_container< 021 book, 022 indexed_by< 023 ordered_unique<identity<book> >, 024 ordered_non_unique<mem_fun<book, std::string&, &book::getTitle> > 025 > 026 > book_set_t;
前の例とほとんど同じですが、member<>の代わりにmem_fun<>を使用しています。
第一引数にコンテナ要素の型、第二引数に関数の型(関数の返り値)、第三引数にメンバ関数へのポインタを指定します。
ちなみに、constメンバ関数を使用する際はconst_mem_fun<>を使用します。
setのようなデータ構造は便利な事は便利なのですが、データを勝手にソートしてしまうので、
データの順列を保持したい場合には使えません。
データの順列を保持したいときには、sequenced<>を利用します。
001 002 #include <boost/multi_index_container.hpp> 003 #include <boost/multi_index/ordered_index.hpp> 004 #include <boost/multi_index/sequenced_index.hpp> 005 #include <boost/multi_index/key_extractors.hpp> 006 007 typedef multi_index_container< 008 book, 009 indexed_by< 010 sequenced<>, 011 ordered_unique<identity<book> > 012 > 013 > book_set_t;
sequenced<>を使うためには、
<boost/multi_index/sequenced_index.hpp>をインクルードする必要があります。
コンテナの取得などの操作は、ordered_unique<>などと全く同じです。
取得したコンテナは、std::listとほぼ同様の扱いが出来ます。
細かい違いについては後述。
multi_index_containerからコンテナへの参照を取得するとき、
nth_indexを利用すると「どんな」コンテナを取得しているのか判りにくい事があります。
これを解決するために、multi_index_containerにはタグ付けと呼ばれる機能があります。
001 002 #include <string> 003 004 #include <boost/multi_index_container.hpp> 005 #include <boost/multi_index/ordered_index.hpp> 006 #include <boost/multi_index/key_extractors.hpp> 007 using namespace boost::multi_index; 008 009 struct title {}; // タグ付けに利用する型 010 011 typedef multi_index_container< 012 book, 013 indexed_by< 014 ordered_unique<identity<book> >, 015 ordered_non_unique< 016 tag<title>, 017 member<book, std::string, &book::title> 018 > 019 > 020 > book_set_t; 021 book_set_t books; 022 023 // つかいかた 024 book_set_t::index<title>::type& title_set = books.get<title>(); 025 // これでも同じ 026 // book_set_t::nth_index<1>::type& title_set = books.get<1>();
ordered_unique<>やordered_non_unique<>、
sequencial<>の第一引数に、tag<タグとして使用する型>
を指定すると、そのコンテナをタグから取得する事ができるようになります。
例ではタグを一種類しか指定していませんが、複数のタグを指定することも可能です。
その場合は、tag<>のテンプレート引数に複数のタグをカンマで区切って指定すればOKです。
例えばstd::setを利用するとき、
二番目のテンプレート引数に、要素の比較に使用する型(std::lessなど)
を渡すことで順序付けの方法を変更できます。
それと同様の機能が、もちろんmulti_index_containerにも実装されています。
001 002 #include <string> 003 #include <functional> 004 005 #include <boost/multi_index_container.hpp> 006 #include <boost/multi_index/ordered_index.hpp> 007 #include <boost/multi_index/key_extractors.hpp> 008 using namespace boost::multi_index; 009 010 011 typedef multi_index_container< 012 book, 013 indexed_by< 014 ordered_unique<identity<book> >, 015 ordered_non_unique< 016 member<book, std::string, &book::title>, 017 std::greater<std::string> // 降順に並べる 018 > 019 > 020 > book_set_t;
タグ付け同様、ordered_unique<>などの最後のテンプレート引数に、
比較に使用する構造体の型を渡すことによって、
順序付けの方法を変更することが出来ます。
ordered_unique<>やoredered_non_unique<>によって利用できるようになるコンテナは、
STLで定義されているset/multisetと
同じメンバ関数を実装しているだけでなく、さらにいくつかのメンバ関数を追加で実装しています。
set/multisetに対する不満の一つに、要素の検索が不便である点が挙げられます。
どういう事かと言いますと、例えば今まで例に挙げたbook型では、
ISBNから検索するのに、
001 #include <set> 002 003 // bookのoperator<()はisbnについて比較しているものとします。 004 typedef std::set<book> bookset_t; 005 bookset_t books; 006 007 ... 008 009 // isbn4756118089を検索する 010 book effectivecpp; 011 effectivecpp.isbn = "4756118089"; 012 result = books.find(effectivecpp);
のように、book型を構築してから検索するという、なんとも面倒な手順を踏まなければなりません。
multi_index_conteinerではその点が改良されていて、
001 #include <boost/multi_index_container.hpp> 002 #include <boost/multi_index/ordered_index.hpp> 003 #include <boost/multi_index/key_extractors.hpp> 004 #include <string> 005 006 using namespace boost::multi_index; 007 008 struct book { 009 std::string isbn; 010 std::string title; 011 }; 012 013 // 比較用の構造体 014 struct book_comparator { 015 // book同士の比較 016 bool operator()(const book& lhs, const book& rhs) const { 017 return lhs.isbn < rhs.isbn; 018 } 019 // std::stringとの比較1 020 bool operator()(const book& lhs, const std::string& rhs) const { 021 return lhs.isbn < rhs; 022 } 023 // std::stringとの比較2 024 bool operator()(const std::string& lhs, const book& rhs) const { 025 return lhs < rhs.isbn; 026 } 027 }; 028 029 typedef multi_index_container< 030 book, 031 indexed_by< 032 ordered_unique< 033 identity<book>, 034 book_comparator // 比較用の構造体の設定 035 >, 036 ordered_unique< 037 member<book, std::string, &book::title> 038 > // メンバ変数による順序付け 039 > 040 > book_set_t; 041 042 typedef book_set_t::nth_index<0>::type& isbnset_t; 043 typedef book_set_t::nth_index<1>::type& titleset_t; 044 045 int main(void) { 046 book_set_t books; 047 048 isbnset_t isbnset = books.get<0>(); 049 std::string isbn = "4756118089"; 050 isbnset.find(isbn); // std::stringで検索できる 051 052 titleset_t titleset = books.get<1>(); 053 std::string title = "Effective C++"; 054 titleset.find(title); // こっちでも。 055 056 return 0; 057 }
のように、順序付けに使用している型(titlesetのstd::string)でソートしたり、
比較用の構造体にbook型とstd::string型の比較演算子が用意されていれば、
book型をstd::string型で検索することもできるようになります。
同様の機能は、count/upper_bound/lower_bound/equal_rangeなどの検索系関数でも使えます。
ただし、この機能が使えるのは、あくまでも比較構造体にoperator()を複数用意した場合や、
順序付けのキーで直接検索する場合のみで、
以下のように
001 #include <boost/multi_index_container.hpp> 002 #include <boost/multi_index/ordered_index.hpp> 003 #include <boost/multi_index/key_extractors.hpp> 004 #include <string> 005 006 using namespace boost::multi_index; 007 008 struct book { 009 std::string isbn; 010 std::string title; 011 012 bool operator<(const book& r) const { 013 return isbn < r.isbn; 014 } 015 // std::stringとの比較1 016 bool operator<(const std::string& str) const { 017 return isbn < str; 018 } 019 }; 020 021 // std::stringとの比較2 022 bool operator<(const std::string& lhs, const book& rhs) { 023 return lhs < rhs.isbn; 024 } 025 026 typedef multi_index_container< 027 book, 028 indexed_by< 029 ordered_unique<identity<book> >, 030 > 031 > book_set_t; 032 033 typedef book_set_t::nth_index<0>::type& isbnset_t; 034 035 int main(void) { 036 book_set_t books; 037 isbnset_t isbnset = books.get<0>(); 038 std::string isbn = "4756118089"; 039 isbnset.find(isbn); // 動かない！！ っていうかコンパイル通らない！！ 040 041 return 0; 042 }
operator<を直接book型に定義したり、
グローバルスコープに二項operator<を定義したとしても、
残念ながらこの便利な機能は使えません。
set/multisetのもう一つの、そして多分最大の問題点が、
イテレータを通して要素へアクセスすると、要素が勝手にconstになってしまうことでしょう。
ソートキーを勝手に変更されてしまうとソートが崩れてしまうのは判るのですが、
だからといって要素の値が全く変更できないのは困るのです。
boost::multi_indexは、(条件付きですが)要素の変更をサポートします。
ordered_unique<>やoredered_non_unique<>で使用できるコンテナには、
以下のようなメンバ関数が用意されています。
001 bool replace(iterator position,const value_type& x); 002 003 template<typename Modifier> bool modify(iterator position,Modifier mod); 004 005 template<typename Modifier> bool modify_key(iterator position,Modifier mod);
replace関数は、positionの要素をxで置き換えた上で、
xを適切な位置へ移動します。
言い換えれば、positionの要素をeraseした上で、
xをinsertします。
modify関数は、mod(*position)を実行した上で、
positionの要素を適切な位置へ移動します。
modefy_key関数は、mod(key_extractor(*position))を実行した上で、
positionの要素を適切な位置に移動します。
ここで、key_extractor()というのは、要素からソートキーを取得する関数の事です。
ordered_(non_)unique<>の第一引数にidentityを指定しているなら要素への参照が、
memberを指定しているなら比較に使用しているメンバへの参照が、
mem_funを指定しているなら比較用の関数の返り値が、それぞれ返ってきます。
これらの関数はいずれも、操作が成功したかどうかを返します。成功するための条件は、
ordered_uniqueの場合、重複する要素が存在しないことと、
multi_index_container内の他のコンテナが、要素の変更を許可していることです。
ordered_non_uniqueの場合、後者の条件のみが必要となります。
これらの操作に失敗した場合、その要素は削除されてしまいます。すりりんぐですね。
sequenced<>を指定する事で使用できるようになるlist風コンテナも、
std::listとの多少の違いが存在します。
set/multisetと同一の要素を保持している事からくる制限が主となっています。
replace/modify関数を通じてのみ可(前項参照)。このライブラリは古いコンパイラでは動作させるのに一工夫必要です。 実は今までの例は、VC7.0以前、gcc3.1以前のコンパイラでは動作しません。 これらのコンパイラでも動くようにするためには、互換記法を使用する必要があります。
memberの３番目のテンプレート引数にメンバ変数へのポインタを渡しますが、
テンプレートへの対応が不十分なコンパイラでは、これが出来ません。
そのため、以下のような代替記法を使用する必要があります。
001 // これの代わりに 002 member<book, std::string, &book::title> 003 004 // これか 005 #include <stddef.h> 006 member_offset<book, std::string, offsetof(book, title)> 007 008 // これを使うべし 009 #include <stddef.h> 010 BOOST_MULTI_INDEX_MEMBER(book, std::string, title) 011 012 // 参考……offsetof @ <stddef.h> & <cstddef> 013 size_t offsetof(structname, membername) //関数ではなくマクロです 014 // structnameの先頭からmembernameまでのオフセットを返します。
(const_)mem_funもまた、テンプレートへの対応が不十分なコンパイラでは動きません。
代替記法は、以下のようになります。
001 // これの代わりに 002 mem_fun<book, std::string, &book::getTitle> 003 004 // これか 005 mem_fun_explicit<book, std::string, std::string (book::*)(), &book::getTitle> 006 007 // これを使用します。 008 BOOST_MULTI_INDEX_MEM_FUN(book, std::string, getTitle) 009 010 // ちなみに、const_mem_funではこんな感じに 011 const_mem_fun<book, std::string, &book::getTitle> 012 // 第三引数のconstを忘れるなかれ 013 const_mem_fun_explicit<book, std::string, std::string (book::*)() const, &book::getTitle> 014 BOOST_MULTI_INDEX_CONST_MEM_FUN(book, std::string, getTitle)
multi_index_containerの以下のメンバ関数が使えません。
nth_index<books, 1>::typeや
get<1>(books)のようにして、
クラス外に定義されている同名の構造体・関数を利用してください。