Representing bidirectional relationship with boost::bimap

In C++, std maps and hash-maps are perfect choice for storing key-value pairs of elements. We use key to lookup related value(s). Quite often I manipulate key-value relationships where both keys and values are unique and usually there is a one-to-one relationships between keys and values. Example of this is a translation tables between two sets of symbols (strings).

I ended up coding my own class with two internal maps, or hash-maps, plus getters and setters to populate and access values for two way lookups.

A while ago I stumbled upon boost's bimap. Here is an example how to use it.

Boost bimap - a two way map

#include <boost/bimap.hpp>

typedef boost::bimap< string, string > map_type;

map_type m;
m.insert( map_type::value_type("ABC","ABC.X.Y") );
m.insert( map_type::value_type("DEF","DEF.X.Y") );
m.insert( map_type::value_type("GHI","GHI.X.Y") );

The above typedef defines a two way map where both keys and values are of type std::string. You could use other types, for example <int,string> and so on. By default the resulting bimap will internally store data in two std::map equivalent data structures with string as key and string value type.

To use boost::bimap you need to only include headers and add path to header file to your compiler include path.

Data in those two internal structures are accessible through left and right accessors. They are both signature equivalent to std::map<string,string> and std::map<string,string>. Additionally there is a way to access the relationship between those two structures which is not shown here.

You can access data via:

map_type::left_map& view_type = m.left;

or

map_type::right_map& view_type = m.right;

Iterating over bimap using each side as key

We can create a method that takes a collection, and uses collection's iterator to access key-value pairs using standard std notation:

template < class MapType > void dump( const MapType& m)
{
    typedef typename MapType::const_iterator const_iterator;
    for ( const_iterator iter(m.begin()),
                         iend(m.end());
         iter != iend;
         ++iter )
    {
        std::cout << iter->first << "-->" << iter->second
                  << std::endl;
    }
}

We call the above method with either left or right collection from the bimap created before. Once again, the left collection uses the original key to access values.

The right collecton is the reverse map using values from the first collection to access keys. The code looks like this:

dump( m.left );
dump( m.right );

Output looks like this:

// using left collection key --> value
ABC-->ABC.X.Y
DEF-->DEF.X.Y
GHI-->GHI.X.Y

// using right collection 'value' --> 'key'
ABC.X.Y-->ABC
DEF.X.Y-->DEF
GHI.X.Y-->GHI

Another way of iterating over one or the other side looks like this, substitute left for right to get the reverse mapping:

map_type::left_map& map_view = m.left;
for (map_type::left_map::const_iterator it(map_view.begin()),
                                        end(map_view.end());
     it != end;
     ++it)
{
    cout << (*it).first << " --> " << (*it).second << endl;
}

Output:

ABC --> ABC.X.Y
DEF --> DEF.X.Y
GHI --> GHI.X.Y

Additionally, you can access the relationship which is not shown here but you can find examples in boost::bimap documentation.

Specify different types of collection in bimap

There are many options how to construct boost::bimap. You can specify what type of data structure should be used for each of collections and even what type of mapping to use for the relationship between left and right side.

In my case I have unique strings with one-to-one mapping on each side. I create the bimap on startup and then only use for lookup by either key. hash-maps seem like perfect candidate here, in bimap they are specified by unordered_set_of type.

See boost::bimap examples and reference for more explanation and examples.

To use hash-maps use appropriate parts above with the following code:

• Add another header file

  #include <boost/bimap.hpp>
  #include <boost/bimap/unordered_set_of.hpp>
  

• Use appropriate namespace so you don't have to prefix everything with boost:: for readability

  using namespace boost::bimaps;
  

• Define map_type using hash_maps, or unordered_set_of as they are called in boost::bimap;

  typedef boost::bimap< unordered_set_of< string >
                      , unordered_set_of< string >
                      > map_type;
  

The rest of the code works the same way.

This shows some very basic usage of boost::bimaps. You can use them whenever you need to access collection in c++ by key, value or by mapping relationship. Boost's bimap provides options to configure each type of internal structures to fit your requirements.