Boost C++ Libraries

One way to interpret bidirectional maps is as a function between two collections of data, lets call them the left and the right collection. An element in this bimap is a relation between an element from the left collection and an element from the right collection. The types of both collections defines the bimap behaviour. We can view the stored data from the left side, as a mapping between keys from the left collection and data from the right one, or from the right side, as a mapping between keys from the right collection and data from the left collection.

Relationships between data in the STL are represented by maps. A standard map is a directed relation of keys from a left collection and data from a right unconstrained collection. The following diagram shows the relationship represented and the user's viewpoint.

The left collection type depends on the selected map type. For example if the the map type is std::multimap the collection type of X is a multiset_of. The following table shows the equivalent types for the std associative containers.

Boost.Bimap design is based on the STL, and extends the framework in a natural way. The following diagram represents the new situation.

Notice that now the std::maps are a particular case of a Boost.Bimap container, where you can view only one side of the relationship and can control the constraints of only one of the collections. Boost.Bimap allows the user to view the relationship from three viewpoints. You can view it from one side, obtaining a std::map compatible container, or you can work directly with the whole relation.

The next diagram shows the layout of the relation and pairs of a bimap. It is the one from the one minute tutorial

Bimap pairs are signature-compatible with standard pairs but are different from them. As you will see in other sections they can be tagged with user defined names and additional information can be attached to them. You can convert from std::pairs to bimap pairs directly but the reverse conversion is not provided. This mean that you can insert elements in a bimap using algorithms like std::copy from containers like std::map, or use std::make_pair to add new elements. However it is best to use bm.left.insert( bm_type::left_value_type(f,s) ) instead of bm.insert( std::make_pair(f,s) ) to avoid an extra call to the copy constructor of each type.

The following code snippet shows the relation between a bimap and standard maps.

	Note
	You have to used references to views, and not directly views object. Views cannot be constructed as separate objects from the container they belong to, so the following: // Wrong: we forgot the & after bm_type::left_type bm_type::left_map lm = bm.left; does not compile, since it is trying to construct the view object lm. This is a common source of errors in user code.

Go to source code

template< class Map, class CompatibleKey, class CompatibleData >
void use_it( Map & m,
             const CompatibleKey  & key,
             const CompatibleData & data )
{
    typedef typename Map::value_type value_type;
    typedef typename Map::const_iterator const_iterator;

    m.insert( value_type(key,data) );
    const_iterator iter = m.find(key);
    if( iter != m.end() )
    {
        assert( iter->first  == key  );
        assert( iter->second == data );

        std::cout << iter->first << " --> " << iter->second;
    }
    m.erase(key);
}

int main()
{
    typedef bimap< set_of<std::string>, set_of<int> > bimap_type;
    bimap_type bm;

    // Standard map
    {
        typedef std::map< std::string, int > map_type;
        map_type m;

        use_it( m, "one", 1 );
    }

    // Left map view
    {
        typedef bimap_type::left_map map_type;
        map_type & m = bm.left;

        use_it( m, "one", 1 );
    }

    // Reverse standard map
    {
        typedef std::map< int, std::string > reverse_map_type;
        reverse_map_type rm;

        use_it( rm, 1, "one" );
    }

    // Right map view
    {
        typedef bimap_type::right_map reverse_map_type;
        reverse_map_type & rm = bm.right;

        use_it( rm, 1, "one" );
    }

    return 0;
}