1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 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.79.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"> 11</head> 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> 20</tr></table> 21<hr> 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> 24</div> 25<div class="section"> 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> 30<div class="toc"><dl class="toc"> 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> 37</dl></div> 38<div class="section"> 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> 43<p> 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. 52 </p> 53</div> 54<div class="section"> 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 57 mapping framework</a> 58</h4></div></div></div> 59<p> 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. 64 </p> 65<p> 66 <span class="inlinemediaobject"><img src="../../images/bimap/standard.mapping.framework.png" alt="standard.mapping.framework"></span> 67 </p> 68<p> 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 73 containers. 74 </p> 75<div class="table"> 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"> 78<colgroup> 79<col> 80<col> 81<col> 82</colgroup> 83<thead><tr> 84<th> 85 <p> 86 container 87 </p> 88 </th> 89<th> 90 <p> 91 left collection type 92 </p> 93 </th> 94<th> 95 <p> 96 right collection type 97 </p> 98 </th> 99</tr></thead> 100<tbody> 101<tr> 102<td> 103 <p> 104 <code class="computeroutput"><span class="identifier">map</span></code> 105 </p> 106 </td> 107<td> 108 <p> 109 <code class="computeroutput"><span class="identifier">set_of</span></code> 110 </p> 111 </td> 112<td> 113 <p> 114 no constraints 115 </p> 116 </td> 117</tr> 118<tr> 119<td> 120 <p> 121 <code class="computeroutput"><span class="identifier">multimap</span></code> 122 </p> 123 </td> 124<td> 125 <p> 126 <code class="computeroutput"><span class="identifier">multiset_of</span></code> 127 </p> 128 </td> 129<td> 130 <p> 131 no constraints 132 </p> 133 </td> 134</tr> 135<tr> 136<td> 137 <p> 138 <code class="computeroutput"><span class="identifier">unordered_map</span></code> 139 </p> 140 </td> 141<td> 142 <p> 143 <code class="computeroutput"><span class="identifier">unordered_set_of</span></code> 144 </p> 145 </td> 146<td> 147 <p> 148 no constraints 149 </p> 150 </td> 151</tr> 152<tr> 153<td> 154 <p> 155 <code class="computeroutput"><span class="identifier">unordered_multimap</span></code> 156 </p> 157 </td> 158<td> 159 <p> 160 <code class="computeroutput"><span class="identifier">unordered_multiset_of</span></code> 161 </p> 162 </td> 163<td> 164 <p> 165 no constraints 166 </p> 167 </td> 168</tr> 169</tbody> 170</table></div> 171</div> 172<br class="table-break"> 173</div> 174<div class="section"> 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> 179<p> 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. 182 </p> 183<p> 184 <span class="inlinemediaobject"><img src="../../images/bimap/extended.mapping.framework.png" alt="extended.mapping.framework"></span> 185 </p> 186<p> 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. 193 </p> 194<p> 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> 197 </p> 198<p> 199 <span class="inlinemediaobject"><img src="../../images/bimap/relation.and.pair.png" alt="relation.and.pair"></span> 200 </p> 201<p> 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. 213 </p> 214<p> 215 The following code snippet shows the relation between a bimap and standard 216 maps. 217 </p> 218<div class="note"><table border="0" summary="Note"> 219<tr> 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> 222</tr> 223<tr><td align="left" valign="top"> 224<p> 225 You have to used 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: 228</p> 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> 231</pre> 232<p> 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 234 in user code. 235 </p> 236</td></tr> 237</table></div> 238<p> 239 <a href="../../../../example/standard_map_comparison.cpp" target="_top">Go to source code</a> 240 </p> 241<p> 242</p> 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> 250 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> 257 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> 262 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> 267 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> 272 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> 275 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> 280 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> 283 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> 288 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> 291 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> 296 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> 299 300 <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> 301<span class="special">}</span> 302</pre> 303<p> 304 </p> 305</div> 306</div> 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>) 312 </p> 313</div></td> 314</tr></table> 315<hr> 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> 318</div> 319</body> 320</html> 321
