5 Copyright (c) 2006-2007 Matias Capeletto
7 Distributed under the Boost Software License, Version 1.0.
8 (See accompanying file LICENSE_1_0.txt or copy at
9 http://www.boost.org/LICENSE_1_0.txt)
13 [/ QuickBook Document version 1.4 ]
15 [section One minute tutorial]
17 [heading What is a bimap?]
19 A Bimap is a data structure that represents bidirectional relations between
20 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]).
22 The following code creates an empty bimap container:
24 typedef bimap<X,Y> bm_type;
27 Given this code, the following is the complete description of the resulting bimap.
28 [footnote A type is ['signature-compatible] with other type if it has the same
29 signature for functions and metadata. Preconditions, postconditions and the order
30 of operations need not be the same.
33 * `bm.left` is signature-compatible with `std::map<X,Y>`
34 * `bm.right` is signature-compatible with `std::map<Y,X>`
35 * `bm` is signature-compatible with `std::set< relation<X,Y> >`
39 You can see how a bimap container offers three views over the same collection of bidirectional relations.
41 If we have any generic function that work with maps
43 template< class MapType >
44 void print_map(const MapType & m)
46 typedef typename MapType::const_iterator const_iterator;
47 for( const_iterator iter = m.begin(), iend = m.end(); iter != iend; ++iter )
49 std::cout << iter->first << "-->" << iter->second << std::endl;
53 We can use the ['left map view] and the ['right map view] with it
55 bimap< int, std::string > bm;
58 print_map( bm.right );
60 And the output will be
71 [heading Layout of the relation and the pairs of a bimap]
73 The `relation` class represents two related elements. The two values are
74 named left and right to express the symmetry of this type.
75 The bimap pair classes are signature-compatible with `std::pairs`.
79 [heading Step by step]
81 [import ../example/step_by_step.cpp]
83 A convenience header is available in the boost directory:
85 #include <boost/bimap.hpp>
87 Lets define a bidirectional map between integers and strings:
89 [code_step_by_step_definition]
91 [heading The collection of relations view]
93 Remember that `bm` alone can be used as a set of relations.
94 We can insert elements or iterate over them using this view.
96 [code_step_by_step_set_of_relations_view]
98 [heading The left map view]
100 `bm.left` works like a `std::map< int, std::string >`. We use it
101 in the same way we will use a standard map.
103 [code_step_by_step_left_map_view]
105 [heading The right map view]
107 `bm.right` works like a `std::map< std::string, int >`. It is
108 important to note that the key is the first type and the data
109 is the second one, exactly as with standard maps.
111 [code_step_by_step_right_map_view]
113 [heading Differences with std::map]
115 The main difference between bimap views and their standard containers counterparts
116 is that, because of the bidirectional nature of a bimap, the values stored in
117 it can not be modified directly using iterators.
118 For example, when a `std::map<X,Y>` iterator is dereferenced the return type is
119 `std::pair<const X, Y>`, so the following code is valid:
120 `m.begin()->second = new_value;`.
121 However dereferencing a `bimap<X,Y>::left_iterator` returns a type that is
122 ['signature-compatible] with a `std::pair<const X, const Y>`
124 bm.left.find(1)->second = "1"; // Compilation error
126 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
130 bm.insert( bm_type::value_type( 1, "one" ) );
132 bm.insert( bm_type::value_type( 1, "1" ) ); // No effect!
133 bm.insert( bm_type::value_type( 2, "one" ) ); // No effect!
135 assert( bm.size() == 1 );
137 [heading A simple example]
139 Look how you can reuse code that is intend to be used with std::maps, like the
140 print_map function in this example.
142 [@../../example/simple_bimap.cpp Go to source code]
146 The output of this program will be the following:
148 [^The number of countries is 4]
150 [^The winner is Argentina]
152 [^Countries names ordered by their final position:]
158 [^Countries names ordered alphabetically along with their final position:]
159 [^Argentina ends in position 1]
160 [^France ends in position 4]
161 [^Germany ends in position 3]
162 [^Spain ends in position 2]
166 [heading Continuing the journey]
168 For information on function signatures, see any standard library
169 documentation or read the [link boost_bimap.reference reference] section of
173 Be aware that a bidirectional map is only signature-compatible with standard
174 containers. Some functions may give different results, such as in the case of
175 inserting a pair into the left map where the second value conflicts with a
176 stored relation in the container. The functions may be slower in a bimap
177 because of the duplicated constraints. It is strongly recommended that
178 you read [link boost_bimap.the_tutorial The full tutorial] if you intend to
179 use a bimap in a serious project.