[/license

Boost.Bimap

Copyright (c) 2006-2007 Matias Capeletto

Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at
http://www.boost.org/LICENSE_1_0.txt)

]

[/ QuickBook Document version 1.4 ]

[section One minute tutorial]

[heading What is a bimap?]

A Bimap is a data structure that represents bidirectional relations between
elements of two collections. The container is designed to work as two opposed STL maps. A bimap between a collection `X` and a collection `Y` can be viewed as a map from `X` to `Y` (this view will be called the ['left map view]) or as a map from `Y` to `X` (known as the ['right map view]). Additionally, the bimap can also be viewed as a set of relations between `X` and `Y` (named the ['collection of relations view]).

The following code creates an empty bimap container:

    typedef bimap<X,Y> bm_type;
    bm_type bm;

Given this code, the following is the complete description of the resulting bimap.
[footnote A type is ['signature-compatible] with other type if it has the same
signature for functions and metadata. Preconditions, postconditions and the order
of operations need not be the same.
]

* `bm.left` is signature-compatible with `std::map<X,Y>`
* `bm.right` is signature-compatible with `std::map<Y,X>`
* `bm` is signature-compatible with `std::set< relation<X,Y> >`

__SIMPLE_BIMAP__

You can see how a bimap container offers three views over the same collection of bidirectional relations. 

If we have any generic function that work with maps

    template< class MapType >
    void print_map(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 can use the ['left map view] and the ['right map view] with it

    bimap< int, std::string > bm;
    ...
    print_map( bm.left  );
    print_map( bm.right );

And the output will be

[pre
[^1 --> one]
[^2 --> two]
...
[^one --> 1]
[^two --> 2]
...
]

[heading Layout of the relation and the pairs of a bimap]

The `relation` class represents two related elements. The two values are
named left and right to express the symmetry of this type.
The bimap pair classes are signature-compatible with `std::pairs`.

__RELATION_AND_PAIR__

[heading Step by step]

[import ../example/step_by_step.cpp]

A convenience header is available in the boost directory:

    #include <boost/bimap.hpp>

Lets define a bidirectional map between integers and strings:

[code_step_by_step_definition]

[heading The collection of relations view]

Remember that `bm` alone can be used as a set of relations.
We can insert elements or iterate over them using this view.

[code_step_by_step_set_of_relations_view]

[heading The left map view]

`bm.left` works like a `std::map< int, std::string >`. We use it
in the same way we will use a standard map.

[code_step_by_step_left_map_view]

[heading The right map view]

`bm.right` works like a `std::map< std::string, int >`. It is
important to note that the key is the first type and the data
is the second one, exactly as with standard maps.

[code_step_by_step_right_map_view]

[heading Differences with std::map]

The main difference between bimap views and their standard containers counterparts
is that, because of the bidirectional nature of a bimap, the values stored in
it can not be modified directly using iterators.
For example, when a `std::map<X,Y>` iterator is dereferenced the return type is
`std::pair<const X, Y>`, so the following code is valid:
`m.begin()->second = new_value;`.
However dereferencing a `bimap<X,Y>::left_iterator` returns a type that is 
['signature-compatible] with a `std::pair<const X, const Y>` 

    bm.left.find(1)->second = "1"; // Compilation error

If you insert `(1,"one")` and `(1,"1")` in a `std::map<int,std::string>` the second insertion will have no effect. In a `bimap<X,Y>` both keys have to remain unique. The insertion may fail in other situations too. Lets see an example

    bm.clear();

    bm.insert( bm_type::value_type( 1, "one" ) );

    bm.insert( bm_type::value_type( 1, "1"   ) ); // No effect!
    bm.insert( bm_type::value_type( 2, "one" ) ); // No effect!

    assert( bm.size() == 1 );

[heading A simple example]

Look how you can reuse code that is intend to be used with std::maps, like the
print_map function in this example.

[@../../example/simple_bimap.cpp Go to source code]

[code_simple_bimap]

The output of this program will be the following:
[pre
[^The number of countries is 4]

[^The winner is Argentina]

[^Countries names ordered by their final position:]
[^1) Argentina]
[^2) Spain]
[^3) Germany]
[^4) France]

[^Countries names ordered alphabetically along with their final position:]
[^Argentina ends in position 1]
[^France ends in position 4]
[^Germany ends in position 3]
[^Spain ends in position 2]
]


[heading Continuing the journey]

For information on function signatures, see any standard library
documentation or read the [link boost_bimap.reference reference] section of
this documentation.

[caution
Be aware that a bidirectional map is only signature-compatible with standard
containers. Some functions may give different results, such as in the case of
inserting a pair into the left map where the second value conflicts with a
stored relation in the container. The functions may be slower in a bimap
because of the duplicated constraints. It is strongly recommended that
you read [link boost_bimap.the_tutorial The full tutorial] if you intend to
use a bimap in a serious project.
]

[endsect]