[/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]