C++ 双方向マップ boost::bimaps 覚え書き
双方向のからアクセス可能なmapとしてboost::bimapsがあります。
今回はそのboost::bimapsの覚え書きです。
まずは単純な1対1の双方向mapとして使う場合
#include <string> #include <iostream> #include <boost/bimap/bimap.hpp> int main() { // int : string の1対1のmap typedef boost::bimaps::bimap<int,std::string> bimap_t; typedef bimap_t::value_type bimap_value_t; bimap_t bm; // 要素の挿入 bm.insert( bimap_value_t( 1, "one" ) ); bm.insert( bimap_value_t( 2, "two" ) ); bm.insert( bimap_value_t( 3, "three" ) ); bm.insert( bimap_value_t( 4, "four" ) ); // サイズを確認 std::cout << "size : " << bm.size() << std::endl; // [output] size: 4 // 左側をkey,右側をvalueとして参照 std::cout << "left.at(2) : " << bm.left.at( 2 ) << std::endl; // [output] left.at(2) : two // 右側をkey,左側をvalueとして参照 std::cout << "right.at(¥"three¥") : " << bm.right.at( "three" ) << std::endl; // [output] right.at("three") : 3 // 要素の無いkeyを参照した場合 std::out_of_range例外が発生する try { bm.left.at(5); } catch( const std::out_of_range &e ) { std::cout << "Out of range exception occured. CAUSE = " << e.what() << std::endl; } // 要素があるかどうかはstd::mapと同様にfind(key)の戻り値のイテレータをend()との比較することで確認できる std::cout << std::boolalpha; std::cout << "left contains 4 : " << ( bm.left.find(4) != bm.left.end() ) << std::endl; // [output] left contains 4 : true std::cout << "left contains 5 : " << ( bm.left.find(5) != bm.left.end() ) << std::endl; // [output] left contains 5 : false // 既に同じ要素がある場合、挿入しても何も変化しない(更新されない) bm.insert( bimap_value_t( 2, "2" ) ); bm.insert( bimap_value_t( 5, "three" ) ); // 前と同じ結果 std::cout << "size : " << bm.size() << std::endl; // [output] size: 4 std::cout << "left.at(2) : " << bm.left.at( 2 ) << std::endl; // [output] left.at(2) : two std::cout << "right.at(¥"three¥") : " << bm.right.at( "three" ) << std::endl; // [output] right.at("three") : 3 std::cout << "left contains 5 : " << ( bm.left.find(5) != bm.left.end() ) << std::endl; // [output] left contains 5 : false // 要素の置き換え { // 成功パターン: (1, "one") -> (1, "ONE") へ置き換え bimap_t::right_iterator itr = bm.right.find( bm.left.at( 1 ) ); const bool successful_replace = bm.right.replace_key( itr, "ONE" ); std::cout << "replace (1, ¥"one¥") -> (1, ¥"ONE¥") successful : " << successful_replace << std::endl; std::cout << "left.at(1) : " << bm.left.at( 1 ) << std::endl; // [output] left.at(1) : ONE } { // 失敗パターン: (1, "ONE") -> (1, "two") へ置き換え bimap_t::right_iterator itr = bm.right.find( bm.left.at( 1 ) ); const bool successful_replace = bm.right.replace_key( itr, "two" ); std::cout << "replace (1, ¥"ONE¥") -> (1, ¥"two¥") successful : " << successful_replace << std::endl; std::cout << "left.at(1) : " << bm.left.at( 1 ) << std::endl; // [output] left.at(1) : ONE } return 0; }
実行結果
size : 4 left.at(2) : two right.at("three") : 3 Out of range exception occured. CAUSE = bimap<>: invalid key left contains 4 : true left contains 5 : false size : 4 left.at(2) : two right.at("three") : 3 left contains 5 : false replace (1, "one") -> (1, "ONE") successful : true left.at(1) : ONE replace (1, "ONE") -> (1, "two") successful : false left.at(1) : ONE
多対1の双方向mapとして使う場合
#include <string> #include <iostream> #include <boost/bimap/bimap.hpp> #include <boost/bimap/multiset_of.hpp> #include <boost/foreach.hpp> #include <boost/range.hpp> int main() { // int : string の多対1のmap typedef boost::bimaps::multiset_of<int> int_set_t; typedef boost::bimaps::bimap<int_set_t,std::string> bimap_t; typedef bimap_t::value_type bimap_value_t; bimap_t bm; // 要素の挿入 bm.insert( bimap_value_t( 1, "one" ) ); bm.insert( bimap_value_t( 2, "two" ) ); bm.insert( bimap_value_t( 3, "three" ) ); bm.insert( bimap_value_t( 4, "four" ) ); bm.insert( bimap_value_t( 1, "uno" ) ); bm.insert( bimap_value_t( 2, "due" ) ); bm.insert( bimap_value_t( 3, "tre" ) ); bm.insert( bimap_value_t( 4, "quattro" ) ); // サイズを確認 std::cout << "size : " << bm.size() << std::endl; // [output] size: 8 // 右側をkeyとしてならat(key)で参照できる std::cout << "right.at(¥"three¥") : " << bm.right.at( "three" ) << std::endl; // [output] right.at("three") : 3 std::cout << "right.at(¥"tre¥") : " << bm.right.at( "tre" ) << std::endl; // [output] right.at("tre") : 3 // 左側をkeyとしては参照できない // bm.left.at( 2 ); // Compile Error!! // 左側の要素が2のものをカウント std::cout << "left.equal_range(2) count : " << boost::distance( bm.left.equal_range(2) ) << std::endl; // [output] left.equal_range(2) count : 2 // 左側の要素が2のものを全て参照する { { // BOOST_FOREACHを使う場合 std::cout << "left.equal_range(2) with BOOST_FOREACH :" << std::endl; BOOST_FOREACH( bimap_t::left_const_reference x, bm.left.equal_range( 2 ) ) { std::cout << " " << x.second << std::endl; } } { // BOOST_FOREACHを使わない場合 std::cout << "left.equal_range(2) without BOOST_FOREACH :" << std::endl; typedef bimap_t::left_const_iterator l_itr_t; typedef std::pair<l_itr_t,l_itr_t> l_itr_range_t; const l_itr_range_t &range = bm.left.equal_range( 2 ); const l_itr_t end_itr = range.second; for( l_itr_t itr = range.first; itr != end_itr; ++itr ) { bimap_t::left_const_reference x = *itr; std::cout << " " << x.second << std::endl; } } } return 0; }
実行結果
size : 8 right.at("three") : 3 right.at("tre") : 3 left.equal_range(2) count : 2 left.equal_range(2) with BOOST_FOREACH : two due left.equal_range(2) without BOOST_FOREACH : two due
要素に情報を付加する
要素の挿入時にあとで参照可能な付加情報をつけることができます。
#include <string> #include <iostream> #include <boost/bimap/bimap.hpp> #include <boost/bimap/multiset_of.hpp> #include <boost/foreach.hpp> int main() { // int : string の多対1のmapにstringでinfoを付加 typedef boost::bimaps::multiset_of<int> int_set_t; typedef boost::bimaps::with_info<std::string> language_info_t; typedef boost::bimaps::bimap<int_set_t,std::string,language_info_t> bimap_t; typedef bimap_t::value_type bimap_value_t; const std::string LANG_ENGLISH( "English" ); const std::string LANG_ITALIAN( "Italian" ); const std::string LANG_JAPANESE( "Japanese" ); bimap_t bm; // 要素の挿入 bm.insert( bimap_value_t( 1, "one", LANG_ENGLISH ) ); bm.insert( bimap_value_t( 2, "two", LANG_ENGLISH ) ); bm.insert( bimap_value_t( 3, "three", LANG_ENGLISH ) ); bm.insert( bimap_value_t( 4, "four", LANG_ENGLISH ) ); bm.insert( bimap_value_t( 1, "uno", LANG_ITALIAN ) ); bm.insert( bimap_value_t( 2, "due", LANG_ITALIAN ) ); bm.insert( bimap_value_t( 3, "tre", LANG_ITALIAN ) ); bm.insert( bimap_value_t( 4, "quattro", LANG_ITALIAN ) ); bm.insert( bimap_value_t( 1, "ichi", LANG_JAPANESE ) ); bm.insert( bimap_value_t( 2, "ni", LANG_JAPANESE ) ); bm.insert( bimap_value_t( 3, "san", LANG_JAPANESE ) ); bm.insert( bimap_value_t( 4, "yon", LANG_JAPANESE ) ); // サイズを確認 std::cout << "size : " << bm.size() << std::endl; // [output] size: 8 // 右側をkeyにしてその要素のinfoを参照 std::cout << "lang of ¥"quattro¥" : " << bm.right.info_at("quattro") << std::endl; // 左側の要素が2のものを全て参照してinfoも参照する std::cout << "left.equal_range(2) :" << std::endl; BOOST_FOREACH( bimap_t::left_const_reference x, bm.left.equal_range( 2 ) ) { std::cout << " value : " << x.second << ", lang : " << x.info << std::endl; } return 0; }
実行結果
size : 12 lang of "quattro" : Italian left.equal_range(2) : value : two, lang : English value : due, lang : Italian value : ni, lang : Japanese
要素の型をtag付きの型にする
要素の参照等でleft, right などで指定するのではなくtagによって指定できるようになる。
#include <string> #include <iostream> #include <boost/bimap/bimap.hpp> // tag struct number_tag{}; struct string_tag{}; struct language_tag{}; int main() { typedef boost::bimaps::tagged<int,number_tag> tagged_number_t; typedef boost::bimaps::tagged<std::string,string_tag> tagged_string_t; typedef boost::bimaps::tagged<std::string,language_tag> tagged_language_t; typedef boost::bimaps::with_info<tagged_language_t> taggged_language_info_t; // int : string の1対1でstringの付加情報有りのtag付きmap typedef boost::bimaps::bimap<tagged_number_t,tagged_string_t,taggged_language_info_t> bimap_t; typedef bimap_t::value_type bimap_value_t; const std::string LANG_ENGLISH( "English" ); const std::string LANG_ITALIAN( "Italian" ); const std::string LANG_JAPANESE( "Japanese" ); bimap_t bm; // 要素の挿入 bm.insert( bimap_value_t( 1, "one", LANG_ENGLISH ) ); bm.insert( bimap_value_t( 2, "due", LANG_ITALIAN ) ); bm.insert( bimap_value_t( 3, "san", LANG_JAPANESE ) ); // サイズを確認 std::cout << "size : " << bm.size() << std::endl; // [output] size: 4 // tagで指定して参照 std::cout << "by<number_tag>().at(2) : " << bm.by<number_tag>().at(2) << std::endl; // [output] by<number_tag>().at(2) : due std::cout << "by<string_tag>().at(¥"one¥") : " << bm.by<string_tag>().at( "one" ) << std::endl; // [output] by<string_tag>().at("one") : 1 { // イテレータからもtagで要素を参照できる const bimap_t::map_by<number_tag>::const_iterator itr = bm.by<number_tag>().find(3); std::cout << "number : " << itr->get<number_tag>() << ", " << "string : " << itr->get<string_tag>() << ", " << "langage : " << itr->get<language_tag>() << std::endl; } return 0; }
実行結果
size : 3 by<number_tag>().at(2) : due by<string_tag>().at("one") : 1 number : 3, string : san, langage : Japanese
参考
Chapter 1. Boost.Bimap - 1.53.0
letsboost::bimaps
boost::bimapsのメモ - NO!と言えるようになりたい