libs/bimap/doc/html/boost_bimap/the_tutorial/discovering_the_bimap_framework.html

   1 <html>
   2 <head>
   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.76.1">
   7 <link rel="home" href="../../index.html" title="Chapter&#160;1.&#160;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>
  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="id774525"></a><p class="title"><b>Table&#160;1.1.&#160;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 &amp; after bm_type::left_type
 230 </span><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
 243 </p>
 244 <pre class="programlisting"><span class="keyword">template</span><span class="special">&lt;</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">&gt;</span>
 245 <span class="keyword">void</span> <span class="identifier">use_it</span><span class="special">(</span> <span class="identifier">Map</span> <span class="special">&amp;</span> <span class="identifier">m</span><span class="special">,</span>
 246              <span class="keyword">const</span> <span class="identifier">CompatibleKey</span>  <span class="special">&amp;</span> <span class="identifier">key</span><span class="special">,</span>
 247              <span class="keyword">const</span> <span class="identifier">CompatibleData</span> <span class="special">&amp;</span> <span class="identifier">data</span> <span class="special">)</span>
 248 <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">value_type</span> <span class="identifier">value_type</span><span class="special">;</span>
 250     <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
 252     <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>
 253     <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>
 254     <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>
 255     <span class="special">{</span>
 256         <span class="identifier">assert</span><span class="special">(</span> <span class="identifier">iter</span><span class="special">-&gt;</span><span class="identifier">first</span>  <span class="special">==</span> <span class="identifier">key</span>  <span class="special">);</span>
 257         <span class="identifier">assert</span><span class="special">(</span> <span class="identifier">iter</span><span class="special">-&gt;</span><span class="identifier">second</span> <span class="special">==</span> <span class="identifier">data</span> <span class="special">);</span>
 258
 259         <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="identifier">iter</span><span class="special">-&gt;</span><span class="identifier">first</span> <span class="special">&lt;&lt;</span> <span class="string">" --&gt; "</span> <span class="special">&lt;&lt;</span> <span class="identifier">iter</span><span class="special">-&gt;</span><span class="identifier">second</span><span class="special">;</span>
 260     <span class="special">}</span>
 261     <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>
 262 <span class="special">}</span>
 263
 264 <span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span>
 265 <span class="special">{</span>
 266     <span class="keyword">typedef</span> <span class="identifier">bimap</span><span class="special">&lt;</span> <span class="identifier">set_of</span><span class="special">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">&gt;,</span> <span class="identifier">set_of</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">&gt;</span> <span class="special">&gt;</span> <span class="identifier">bimap_type</span><span class="special">;</span>
 267     <span class="identifier">bimap_type</span> <span class="identifier">bm</span><span class="special">;</span>
 268
 269     <span class="comment">// Standard map
 270 </span>    <span class="special">{</span>
 271         <span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">map</span><span class="special">&lt;</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">&gt;</span> <span class="identifier">map_type</span><span class="special">;</span>
 272         <span class="identifier">map_type</span> <span class="identifier">m</span><span class="special">;</span>
 273
 274         <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>
 275     <span class="special">}</span>
 276
 277     <span class="comment">// Left map view
 278 </span>    <span class="special">{</span>
 279         <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>
 280         <span class="identifier">map_type</span> <span class="special">&amp;</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
 282         <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>
 283     <span class="special">}</span>
 284
 285     <span class="comment">// Reverse standard map
 286 </span>    <span class="special">{</span>
 287         <span class="keyword">typedef</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">map</span><span class="special">&lt;</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">&gt;</span> <span class="identifier">reverse_map_type</span><span class="special">;</span>
 288         <span class="identifier">reverse_map_type</span> <span class="identifier">rm</span><span class="special">;</span>
 289
 290         <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>
 291     <span class="special">}</span>
 292
 293     <span class="comment">// Right map view
 294 </span>    <span class="special">{</span>
 295         <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>
 296         <span class="identifier">reverse_map_type</span> <span class="special">&amp;</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
 298         <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>
 299     <span class="special">}</span>
 300
 301     <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span>
 302 <span class="special">}</span>
 303 </pre>
 304 <p>
 305         </p>
 306 </div>
 307 </div>
 308 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 309 <td align="left"></td>
 310 <td align="right"><div class="copyright-footer">Copyright &#169; 2006 -2007 Matias Capeletto<p>
 311         Distributed under the Boost Software License, Version 1.0. (See accompanying
 312         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>)
 313       </p>
 314 </div></td>
 315 </tr></table>
 316 <hr>
 317 <div class="spirit-nav">
 318 <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>
 319 </div>
 320 </body>
 321 </html>