Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

PrevUpHomeNext

Discovering the bimap framework

Interpreting bidirectional maps
Standard mapping framework
Bimap mapping framework

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.

standard.mapping.framework

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.

Table 1.1. std associative containers

container

left collection type

right collection type

map

set_of

no constraints

multimap

multiset_of

no constraints

unordered_map

unordered_set_of

no constraints

unordered_multimap

unordered_multiset_of

no constraints


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

extended.mapping.framework

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

relation.and.pair

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] 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;
}


PrevUpHomeNext