3 <meta http-equiv=
"Content-Type" content=
"text/html; charset=US-ASCII">
4 <title>Discovering the bimap framework
</title>
5 <link rel=
"stylesheet" href=
"../../boostbook.css" type=
"text/css">
6 <meta name=
"generator" content=
"DocBook XSL Stylesheets V1.77.1">
7 <link rel=
"home" href=
"../../index.html" title=
"Chapter 1. Boost.Bimap">
8 <link rel=
"up" href=
"../the_tutorial.html" title=
"The tutorial">
9 <link rel=
"prev" href=
"../the_tutorial.html" title=
"The tutorial">
10 <link rel=
"next" href=
"controlling_collection_types.html" title=
"Controlling collection types">
12 <body bgcolor=
"white" text=
"black" link=
"#0000FF" vlink=
"#840084" alink=
"#0000FF">
13 <table cellpadding=
"2" width=
"100%"><tr>
14 <td valign=
"top"><img alt=
"Boost C++ Libraries" width=
"277" height=
"86" src=
"../../../../../../boost.png"></td>
15 <td align=
"center"><a href=
"../../../../../../index.html">Home
</a></td>
16 <td align=
"center"><a href=
"../../../../../../libs/libraries.htm">Libraries
</a></td>
17 <td align=
"center"><a href=
"http://www.boost.org/users/people.html">People
</a></td>
18 <td align=
"center"><a href=
"http://www.boost.org/users/faq.html">FAQ
</a></td>
19 <td align=
"center"><a href=
"../../../../../../more/index.htm">More
</a></td>
22 <div class=
"spirit-nav">
23 <a accesskey=
"p" href=
"../the_tutorial.html"><img src=
"../../../../../../doc/src/images/prev.png" alt=
"Prev"></a><a accesskey=
"u" href=
"../the_tutorial.html"><img src=
"../../../../../../doc/src/images/up.png" alt=
"Up"></a><a accesskey=
"h" href=
"../../index.html"><img src=
"../../../../../../doc/src/images/home.png" alt=
"Home"></a><a accesskey=
"n" href=
"controlling_collection_types.html"><img src=
"../../../../../../doc/src/images/next.png" alt=
"Next"></a>
25 <div class=
"section boost_bimap_the_tutorial_discovering_the_bimap_framework">
26 <div class=
"titlepage"><div><div><h3 class=
"title">
27 <a name=
"boost_bimap.the_tutorial.discovering_the_bimap_framework"></a><a class=
"link" href=
"discovering_the_bimap_framework.html" title=
"Discovering the bimap framework">Discovering
28 the bimap framework
</a>
29 </h3></div></div></div>
31 <dt><span class=
"section"><a href=
"discovering_the_bimap_framework.html#boost_bimap.the_tutorial.discovering_the_bimap_framework.interpreting_bidirectional_maps">Interpreting
32 bidirectional maps
</a></span></dt>
33 <dt><span class=
"section"><a href=
"discovering_the_bimap_framework.html#boost_bimap.the_tutorial.discovering_the_bimap_framework.standard_mapping_framework">Standard
34 mapping framework
</a></span></dt>
35 <dt><span class=
"section"><a href=
"discovering_the_bimap_framework.html#boost_bimap.the_tutorial.discovering_the_bimap_framework.bimap_mapping_framework">Bimap
36 mapping framework
</a></span></dt>
38 <div class=
"section boost_bimap_the_tutorial_discovering_the_bimap_framework_interpreting_bidirectional_maps">
39 <div class=
"titlepage"><div><div><h4 class=
"title">
40 <a name=
"boost_bimap.the_tutorial.discovering_the_bimap_framework.interpreting_bidirectional_maps"></a><a class=
"link" href=
"discovering_the_bimap_framework.html#boost_bimap.the_tutorial.discovering_the_bimap_framework.interpreting_bidirectional_maps" title=
"Interpreting bidirectional maps">Interpreting
41 bidirectional maps
</a>
42 </h4></div></div></div>
44 One way to interpret bidirectional maps is as a function between two collections
45 of data, lets call them the left and the right collection. An element in
46 this bimap is a relation between an element from the left collection and
47 an element from the right collection. The types of both collections defines
48 the bimap behaviour. We can view the stored data from the left side, as
49 a mapping between keys from the left collection and data from the right
50 one, or from the right side, as a mapping between keys from the right collection
51 and data from the left collection.
54 <div class=
"section boost_bimap_the_tutorial_discovering_the_bimap_framework_standard_mapping_framework">
55 <div class=
"titlepage"><div><div><h4 class=
"title">
56 <a name=
"boost_bimap.the_tutorial.discovering_the_bimap_framework.standard_mapping_framework"></a><a class=
"link" href=
"discovering_the_bimap_framework.html#boost_bimap.the_tutorial.discovering_the_bimap_framework.standard_mapping_framework" title=
"Standard mapping framework">Standard
58 </h4></div></div></div>
60 Relationships between data in the STL are represented by maps. A standard
61 map is a directed relation of keys from a left collection and data from
62 a right unconstrained collection. The following diagram shows the relationship
63 represented and the user's viewpoint.
66 <span class=
"inlinemediaobject"><img src=
"../../images/bimap/standard.mapping.framework.png" alt=
"standard.mapping.framework"></span>
69 The left collection type depends on the selected map type. For example
70 if the the map type is
<code class=
"computeroutput"><span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">multimap
</span></code>
71 the collection type of X is a
<code class=
"computeroutput"><span class=
"identifier">multiset_of
</span></code>.
72 The following table shows the equivalent types for the std associative
76 <a name=
"boost_bimap.the_tutorial.discovering_the_bimap_framework.standard_mapping_framework.t0"></a><p class=
"title"><b>Table
 1.1.
 std associative containers
</b></p>
77 <div class=
"table-contents"><table class=
"table" summary=
"std associative containers">
104 <code class=
"computeroutput"><span class=
"identifier">map
</span></code>
109 <code class=
"computeroutput"><span class=
"identifier">set_of
</span></code>
121 <code class=
"computeroutput"><span class=
"identifier">multimap
</span></code>
126 <code class=
"computeroutput"><span class=
"identifier">multiset_of
</span></code>
138 <code class=
"computeroutput"><span class=
"identifier">unordered_map
</span></code>
143 <code class=
"computeroutput"><span class=
"identifier">unordered_set_of
</span></code>
155 <code class=
"computeroutput"><span class=
"identifier">unordered_multimap
</span></code>
160 <code class=
"computeroutput"><span class=
"identifier">unordered_multiset_of
</span></code>
172 <br class=
"table-break">
174 <div class=
"section boost_bimap_the_tutorial_discovering_the_bimap_framework_bimap_mapping_framework">
175 <div class=
"titlepage"><div><div><h4 class=
"title">
176 <a name=
"boost_bimap.the_tutorial.discovering_the_bimap_framework.bimap_mapping_framework"></a><a class=
"link" href=
"discovering_the_bimap_framework.html#boost_bimap.the_tutorial.discovering_the_bimap_framework.bimap_mapping_framework" title=
"Bimap mapping framework">Bimap
177 mapping framework
</a>
178 </h4></div></div></div>
180 Boost.Bimap design is based on the STL, and extends the framework in a
181 natural way. The following diagram represents the new situation.
184 <span class=
"inlinemediaobject"><img src=
"../../images/bimap/extended.mapping.framework.png" alt=
"extended.mapping.framework"></span>
187 Notice that now the
<code class=
"computeroutput"><span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">maps
</span></code>
188 are a particular case of a Boost.Bimap container, where you can view only
189 one side of the relationship and can control the constraints of only one
190 of the collections. Boost.Bimap allows the user to view the relationship
191 from three viewpoints. You can view it from one side, obtaining a
<code class=
"computeroutput"><span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">map
</span></code> compatible container, or you can
192 work directly with the whole relation.
195 The next diagram shows the layout of the relation and pairs of a bimap.
196 It is the one from the
<span class=
"emphasis"><em>one minute tutorial
</em></span>
199 <span class=
"inlinemediaobject"><img src=
"../../images/bimap/relation.and.pair.png" alt=
"relation.and.pair"></span>
202 Bimap pairs are signature-compatible with standard pairs but are different
203 from them. As you will see in other sections they can be tagged with user
204 defined names and additional information can be attached to them. You can
205 convert from
<code class=
"computeroutput"><span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">pairs
</span></code> to bimap pairs directly but the
206 reverse conversion is not provided. This mean that you can insert elements
207 in a bimap using algorithms like
<code class=
"computeroutput"><span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">copy
</span></code>
208 from containers
<code class=
"computeroutput"><span class=
"identifier">like
</span> <span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">map
</span></code>,
209 or use
<code class=
"computeroutput"><span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">make_pair
</span></code> to add new elements. However
210 it is best to use
<code class=
"computeroutput"><span class=
"identifier">bm
</span><span class=
"special">.
</span><span class=
"identifier">left
</span><span class=
"special">.
</span><span class=
"identifier">insert
</span><span class=
"special">(
</span> <span class=
"identifier">bm_type
</span><span class=
"special">::
</span><span class=
"identifier">left_value_type
</span><span class=
"special">(
</span><span class=
"identifier">f
</span><span class=
"special">,
</span><span class=
"identifier">s
</span><span class=
"special">)
</span> <span class=
"special">)
</span></code> instead
211 of
<code class=
"computeroutput"><span class=
"identifier">bm
</span><span class=
"special">.
</span><span class=
"identifier">insert
</span><span class=
"special">(
</span> <span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">make_pair
</span><span class=
"special">(
</span><span class=
"identifier">f
</span><span class=
"special">,
</span><span class=
"identifier">s
</span><span class=
"special">)
</span> <span class=
"special">)
</span></code> to avoid
212 an extra call to the copy constructor of each type.
215 The following code snippet shows the relation between a bimap and standard
218 <div class=
"note"><table border=
"0" summary=
"Note">
220 <td rowspan=
"2" align=
"center" valign=
"top" width=
"25"><img alt=
"[Note]" src=
"../../../../../../doc/src/images/note.png"></td>
221 <th align=
"left">Note
</th>
223 <tr><td align=
"left" valign=
"top">
225 You have to use references to views, and not directly views object.
226 Views cannot be constructed as separate objects from the container they
227 belong to, so the following:
229 <pre class=
"programlisting"><span class=
"comment">// Wrong: we forgot the
& after bm_type::left_type
</span>
230 <span class=
"identifier">bm_type
</span><span class=
"special">::
</span><span class=
"identifier">left_map
</span> <span class=
"identifier">lm
</span> <span class=
"special">=
</span> <span class=
"identifier">bm
</span><span class=
"special">.
</span><span class=
"identifier">left
</span><span class=
"special">;
</span>
233 does not compile, since it is trying to construct the view object
<code class=
"computeroutput"><span class=
"identifier">lm
</span></code>. This is a common source of errors
239 <a href=
"../../../../example/standard_map_comparison.cpp" target=
"_top">Go to source code
</a>
243 <pre class=
"programlisting"><span class=
"keyword">template
</span><span class=
"special"><</span> <span class=
"keyword">class
</span> <span class=
"identifier">Map
</span><span class=
"special">,
</span> <span class=
"keyword">class
</span> <span class=
"identifier">CompatibleKey
</span><span class=
"special">,
</span> <span class=
"keyword">class
</span> <span class=
"identifier">CompatibleData
</span> <span class=
"special">></span>
244 <span class=
"keyword">void
</span> <span class=
"identifier">use_it
</span><span class=
"special">(
</span> <span class=
"identifier">Map
</span> <span class=
"special">&</span> <span class=
"identifier">m
</span><span class=
"special">,
</span>
245 <span class=
"keyword">const
</span> <span class=
"identifier">CompatibleKey
</span> <span class=
"special">&</span> <span class=
"identifier">key
</span><span class=
"special">,
</span>
246 <span class=
"keyword">const
</span> <span class=
"identifier">CompatibleData
</span> <span class=
"special">&</span> <span class=
"identifier">data
</span> <span class=
"special">)
</span>
247 <span class=
"special">{
</span>
248 <span class=
"keyword">typedef
</span> <span class=
"keyword">typename
</span> <span class=
"identifier">Map
</span><span class=
"special">::
</span><span class=
"identifier">value_type
</span> <span class=
"identifier">value_type
</span><span class=
"special">;
</span>
249 <span class=
"keyword">typedef
</span> <span class=
"keyword">typename
</span> <span class=
"identifier">Map
</span><span class=
"special">::
</span><span class=
"identifier">const_iterator
</span> <span class=
"identifier">const_iterator
</span><span class=
"special">;
</span>
251 <span class=
"identifier">m
</span><span class=
"special">.
</span><span class=
"identifier">insert
</span><span class=
"special">(
</span> <span class=
"identifier">value_type
</span><span class=
"special">(
</span><span class=
"identifier">key
</span><span class=
"special">,
</span><span class=
"identifier">data
</span><span class=
"special">)
</span> <span class=
"special">);
</span>
252 <span class=
"identifier">const_iterator
</span> <span class=
"identifier">iter
</span> <span class=
"special">=
</span> <span class=
"identifier">m
</span><span class=
"special">.
</span><span class=
"identifier">find
</span><span class=
"special">(
</span><span class=
"identifier">key
</span><span class=
"special">);
</span>
253 <span class=
"keyword">if
</span><span class=
"special">(
</span> <span class=
"identifier">iter
</span> <span class=
"special">!=
</span> <span class=
"identifier">m
</span><span class=
"special">.
</span><span class=
"identifier">end
</span><span class=
"special">()
</span> <span class=
"special">)
</span>
254 <span class=
"special">{
</span>
255 <span class=
"identifier">assert
</span><span class=
"special">(
</span> <span class=
"identifier">iter
</span><span class=
"special">-
></span><span class=
"identifier">first
</span> <span class=
"special">==
</span> <span class=
"identifier">key
</span> <span class=
"special">);
</span>
256 <span class=
"identifier">assert
</span><span class=
"special">(
</span> <span class=
"identifier">iter
</span><span class=
"special">-
></span><span class=
"identifier">second
</span> <span class=
"special">==
</span> <span class=
"identifier">data
</span> <span class=
"special">);
</span>
258 <span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">cout
</span> <span class=
"special"><<</span> <span class=
"identifier">iter
</span><span class=
"special">-
></span><span class=
"identifier">first
</span> <span class=
"special"><<</span> <span class=
"string">" --> "</span> <span class=
"special"><<</span> <span class=
"identifier">iter
</span><span class=
"special">-
></span><span class=
"identifier">second
</span><span class=
"special">;
</span>
259 <span class=
"special">}
</span>
260 <span class=
"identifier">m
</span><span class=
"special">.
</span><span class=
"identifier">erase
</span><span class=
"special">(
</span><span class=
"identifier">key
</span><span class=
"special">);
</span>
261 <span class=
"special">}
</span>
263 <span class=
"keyword">int
</span> <span class=
"identifier">main
</span><span class=
"special">()
</span>
264 <span class=
"special">{
</span>
265 <span class=
"keyword">typedef
</span> <span class=
"identifier">bimap
</span><span class=
"special"><</span> <span class=
"identifier">set_of
</span><span class=
"special"><</span><span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">string
</span><span class=
"special">>,
</span> <span class=
"identifier">set_of
</span><span class=
"special"><</span><span class=
"keyword">int
</span><span class=
"special">></span> <span class=
"special">></span> <span class=
"identifier">bimap_type
</span><span class=
"special">;
</span>
266 <span class=
"identifier">bimap_type
</span> <span class=
"identifier">bm
</span><span class=
"special">;
</span>
268 <span class=
"comment">// Standard map
</span>
269 <span class=
"special">{
</span>
270 <span class=
"keyword">typedef
</span> <span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">map
</span><span class=
"special"><</span> <span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">string
</span><span class=
"special">,
</span> <span class=
"keyword">int
</span> <span class=
"special">></span> <span class=
"identifier">map_type
</span><span class=
"special">;
</span>
271 <span class=
"identifier">map_type
</span> <span class=
"identifier">m
</span><span class=
"special">;
</span>
273 <span class=
"identifier">use_it
</span><span class=
"special">(
</span> <span class=
"identifier">m
</span><span class=
"special">,
</span> <span class=
"string">"one"</span><span class=
"special">,
</span> <span class=
"number">1</span> <span class=
"special">);
</span>
274 <span class=
"special">}
</span>
276 <span class=
"comment">// Left map view
</span>
277 <span class=
"special">{
</span>
278 <span class=
"keyword">typedef
</span> <span class=
"identifier">bimap_type
</span><span class=
"special">::
</span><span class=
"identifier">left_map
</span> <span class=
"identifier">map_type
</span><span class=
"special">;
</span>
279 <span class=
"identifier">map_type
</span> <span class=
"special">&</span> <span class=
"identifier">m
</span> <span class=
"special">=
</span> <span class=
"identifier">bm
</span><span class=
"special">.
</span><span class=
"identifier">left
</span><span class=
"special">;
</span>
281 <span class=
"identifier">use_it
</span><span class=
"special">(
</span> <span class=
"identifier">m
</span><span class=
"special">,
</span> <span class=
"string">"one"</span><span class=
"special">,
</span> <span class=
"number">1</span> <span class=
"special">);
</span>
282 <span class=
"special">}
</span>
284 <span class=
"comment">// Reverse standard map
</span>
285 <span class=
"special">{
</span>
286 <span class=
"keyword">typedef
</span> <span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">map
</span><span class=
"special"><</span> <span class=
"keyword">int
</span><span class=
"special">,
</span> <span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">string
</span> <span class=
"special">></span> <span class=
"identifier">reverse_map_type
</span><span class=
"special">;
</span>
287 <span class=
"identifier">reverse_map_type
</span> <span class=
"identifier">rm
</span><span class=
"special">;
</span>
289 <span class=
"identifier">use_it
</span><span class=
"special">(
</span> <span class=
"identifier">rm
</span><span class=
"special">,
</span> <span class=
"number">1</span><span class=
"special">,
</span> <span class=
"string">"one"</span> <span class=
"special">);
</span>
290 <span class=
"special">}
</span>
292 <span class=
"comment">// Right map view
</span>
293 <span class=
"special">{
</span>
294 <span class=
"keyword">typedef
</span> <span class=
"identifier">bimap_type
</span><span class=
"special">::
</span><span class=
"identifier">right_map
</span> <span class=
"identifier">reverse_map_type
</span><span class=
"special">;
</span>
295 <span class=
"identifier">reverse_map_type
</span> <span class=
"special">&</span> <span class=
"identifier">rm
</span> <span class=
"special">=
</span> <span class=
"identifier">bm
</span><span class=
"special">.
</span><span class=
"identifier">right
</span><span class=
"special">;
</span>
297 <span class=
"identifier">use_it
</span><span class=
"special">(
</span> <span class=
"identifier">rm
</span><span class=
"special">,
</span> <span class=
"number">1</span><span class=
"special">,
</span> <span class=
"string">"one"</span> <span class=
"special">);
</span>
298 <span class=
"special">}
</span>
300 <span class=
"keyword">return
</span> <span class=
"number">0</span><span class=
"special">;
</span>
301 <span class=
"special">}
</span>
307 <table xmlns:
rev=
"http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width=
"100%"><tr>
308 <td align=
"left"></td>
309 <td align=
"right"><div class=
"copyright-footer">Copyright
© 2006-
2012 Matias Capeletto
<p>
310 Distributed under the Boost Software License, Version
1.0. (See accompanying
311 file LICENSE_1_0.txt or copy at
<a href=
"http://www.boost.org/LICENSE_1_0.txt" target=
"_top">http://www.boost.org/LICENSE_1_0.txt
</a>)
316 <div class=
"spirit-nav">
317 <a accesskey=
"p" href=
"../the_tutorial.html"><img src=
"../../../../../../doc/src/images/prev.png" alt=
"Prev"></a><a accesskey=
"u" href=
"../the_tutorial.html"><img src=
"../../../../../../doc/src/images/up.png" alt=
"Up"></a><a accesskey=
"h" href=
"../../index.html"><img src=
"../../../../../../doc/src/images/home.png" alt=
"Home"></a><a accesskey=
"n" href=
"controlling_collection_types.html"><img src=
"../../../../../../doc/src/images/next.png" alt=
"Next"></a>