<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.75.2">
<link rel="home" href="../../index.html" title="Chapter 1. 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>
<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="id765312"></a><p class="title"><b>Table 1.1. 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 & 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"><</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>
<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>
<span class="keyword">const</span> <span class="identifier">CompatibleKey</span> <span class="special">&</span> <span class="identifier">key</span><span class="special">,</span>
<span class="keyword">const</span> <span class="identifier">CompatibleData</span> <span class="special">&</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">-></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">-></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"><<</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>
<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"><</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>
<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"><</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>
<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">&</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"><</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>
<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">&</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 © 2006 -2007 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>
