1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
|
[/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 convinience header is avaiable 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 situtions 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]
|
