Discovering the bimap framework

| Home | Libraries | People | FAQ | More

### Discovering the bimap framework

#### Interpreting bidirectional maps

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.

#### Standard mapping framework

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.

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

#### Bimap mapping framework

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