devn00b
/
EQ2EMu


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320
							<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Discovering the bimap framework</title>
<link rel="stylesheet" href="../../boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../../index.html" title="Chapter&#160;1.&#160;Boost.Bimap">
<link rel="up" href="../the_tutorial.html" title="The tutorial">
<link rel="prev" href="../the_tutorial.html" title="The tutorial">
<link rel="next" href="controlling_collection_types.html" title="Controlling collection types">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<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>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<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
      the bimap framework</a>
</h3></div></div></div>
<div class="toc"><dl class="toc">
<dt><span class="section"><a href="discovering_the_bimap_framework.html#boost_bimap.the_tutorial.discovering_the_bimap_framework.interpreting_bidirectional_maps">Interpreting
        bidirectional maps</a></span></dt>
<dt><span class="section"><a href="discovering_the_bimap_framework.html#boost_bimap.the_tutorial.discovering_the_bimap_framework.standard_mapping_framework">Standard
        mapping framework</a></span></dt>
<dt><span class="section"><a href="discovering_the_bimap_framework.html#boost_bimap.the_tutorial.discovering_the_bimap_framework.bimap_mapping_framework">Bimap
        mapping framework</a></span></dt>
</dl></div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<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
        bidirectional maps</a>
</h4></div></div></div>
<p>
          One way to interpret bidirectional maps is as a function between two collections
          of data, lets call them the left and the right collection. An element in
          this bimap is a relation between an element from the left collection and
          an element from the right collection. The types of both collections defines
          the bimap behaviour. We can view the stored data from the left side, as
          a mapping between keys from the left collection and data from the right
          one, or from the right side, as a mapping between keys from the right collection
          and data from the left collection.
        </p>
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<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
        mapping framework</a>
</h4></div></div></div>
<p>
          Relationships between data in the STL are represented by maps. A standard
          map is a directed relation of keys from a left collection and data from
          a right unconstrained collection. The following diagram shows the relationship
          represented and the user's viewpoint.
        </p>
<p>
          <span class="inlinemediaobject"><img src="../../images/bimap/standard.mapping.framework.png" alt="standard.mapping.framework"></span>
        </p>
<p>
          The left collection type depends on the selected map type. For example
          if the the map type is <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">multimap</span></code>
          the collection type of X is a <code class="computeroutput"><span class="identifier">multiset_of</span></code>.
          The following table shows the equivalent types for the std associative
          containers.
        </p>
<div class="table">
<a name="boost_bimap.the_tutorial.discovering_the_bimap_framework.standard_mapping_framework.t0"></a><p class="title"><b>Table&#160;1.1.&#160;std associative containers</b></p>
<div class="table-contents"><table class="table" summary="std associative containers">
<colgroup>
<col>
<col>
<col>
</colgroup>
<thead><tr>
<th>
                  <p>
                    container
                  </p>
                </th>
<th>
                  <p>
                    left collection type
                  </p>
                </th>
<th>
                  <p>
                    right collection type
                  </p>
                </th>
</tr></thead>
<tbody>
<tr>
<td>
                  <p>
                    <code class="computeroutput"><span class="identifier">map</span></code>
                  </p>
                </td>
<td>
                  <p>
                    <code class="computeroutput"><span class="identifier">set_of</span></code>
                  </p>
                </td>
<td>
                  <p>
                    no constraints
                  </p>
                </td>
</tr>
<tr>
<td>
                  <p>
                    <code class="computeroutput"><span class="identifier">multimap</span></code>
                  </p>
                </td>
<td>
                  <p>
                    <code class="computeroutput"><span class="identifier">multiset_of</span></code>
                  </p>
                </td>
<td>
                  <p>
                    no constraints
                  </p>
                </td>
</tr>
<tr>
<td>
                  <p>
                    <code class="computeroutput"><span class="identifier">unordered_map</span></code>
                  </p>
                </td>
<td>
                  <p>
                    <code class="computeroutput"><span class="identifier">unordered_set_of</span></code>
                  </p>
                </td>
<td>
                  <p>
                    no constraints
                  </p>
                </td>
</tr>
<tr>
<td>
                  <p>
                    <code class="computeroutput"><span class="identifier">unordered_multimap</span></code>
                  </p>
                </td>
<td>
                  <p>
                    <code class="computeroutput"><span class="identifier">unordered_multiset_of</span></code>
                  </p>
                </td>
<td>
                  <p>
                    no constraints
                  </p>
                </td>
</tr>
</tbody>
</table></div>
</div>
<br class="table-break">
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<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
        mapping framework</a>
</h4></div></div></div>
<p>
          Boost.Bimap design is based on the STL, and extends the framework in a
          natural way. The following diagram represents the new situation.
        </p>
<p>
          <span class="inlinemediaobject"><img src="../../images/bimap/extended.mapping.framework.png" alt="extended.mapping.framework"></span>
        </p>
<p>
          Notice that now the <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">maps</span></code>
          are a particular case of a Boost.Bimap container, where you can view only
          one side of the relationship and can control the constraints of only one
          of the collections. Boost.Bimap allows the user to view the relationship
          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
          work directly with the whole relation.
        </p>
<p>
          The next diagram shows the layout of the relation and pairs of a bimap.
          It is the one from the <span class="emphasis"><em>one minute tutorial</em></span>
        </p>
<p>
          <span class="inlinemediaobject"><img src="../../images/bimap/relation.and.pair.png" alt="relation.and.pair"></span>
        </p>
<p>
          Bimap pairs are signature-compatible with standard pairs but are different
          from them. As you will see in other sections they can be tagged with user
          defined names and additional information can be attached to them. You can
          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
          reverse conversion is not provided. This mean that you can insert elements
          in a bimap using algorithms like <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">copy</span></code>
          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>,
          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
          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
          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
          an extra call to the copy constructor of each type.
        </p>
<p>
          The following code snippet shows the relation between a bimap and standard
          maps.
        </p>
<div class="note"><table border="0" summary="Note">
<tr>
<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../../../../doc/src/images/note.png"></td>
<th align="left">Note</th>
</tr>
<tr><td align="left" valign="top">
<p>
            You have to used references to views, and not directly views object.
            Views cannot be constructed as separate objects from the container they
            belong to, so the following:
</p>
<pre class="programlisting"><span class="comment">// Wrong: we forgot the &amp; after bm_type::left_type</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>
</pre>
<p>
            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
            in user code.
          </p>
</td></tr>
</table></div>
<p>
          <a href="../../../../example/standard_map_comparison.cpp" target="_top">Go to source code</a>
        </p>
<p>
</p>
<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>
<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>
             <span class="keyword">const</span> <span class="identifier">CompatibleKey</span>  <span class="special">&amp;</span> <span class="identifier">key</span><span class="special">,</span>
             <span class="keyword">const</span> <span class="identifier">CompatibleData</span> <span class="special">&amp;</span> <span class="identifier">data</span> <span class="special">)</span>
<span class="special">{</span>
    <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>
    <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>

    <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>
    <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>
    <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>
    <span class="special">{</span>
        <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>
        <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>

        <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>
    <span class="special">}</span>
    <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>
<span class="special">}</span>

<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span>
<span class="special">{</span>
    <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>
    <span class="identifier">bimap_type</span> <span class="identifier">bm</span><span class="special">;</span>

    <span class="comment">// Standard map</span>
    <span class="special">{</span>
        <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>
        <span class="identifier">map_type</span> <span class="identifier">m</span><span class="special">;</span>

        <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>
    <span class="special">}</span>

    <span class="comment">// Left map view</span>
    <span class="special">{</span>
        <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>
        <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>

        <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>
    <span class="special">}</span>

    <span class="comment">// Reverse standard map</span>
    <span class="special">{</span>
        <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>
        <span class="identifier">reverse_map_type</span> <span class="identifier">rm</span><span class="special">;</span>

        <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>
    <span class="special">}</span>

    <span class="comment">// Right map view</span>
    <span class="special">{</span>
        <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>
        <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>

        <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>
    <span class="special">}</span>

    <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span>
<span class="special">}</span>
</pre>
<p>
        </p>
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright &#169; 2006-2012 Matias Capeletto<p>
        Distributed under the Boost Software License, Version 1.0. (See accompanying
        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>)
      </p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<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>
</div>
</body>
</html>