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 の多対１の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 の多対１の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でｓtringの付加情報有りの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!と言えるようになりたい