[ceph.git] / ceph / src / boost / libs / bimap / doc / html / boost_bimap / rationale.html

<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Rationale</title>
<link rel="stylesheet" href="../boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="../index.html" title="Chapter&#160;1.&#160;Boost.Bimap">
<link rel="up" href="../index.html" title="Chapter&#160;1.&#160;Boost.Bimap">
<link rel="prev" href="release_notes.html" title="Release notes">
<link rel="next" href="rationale/additional_features.html" title="Additional Features">
</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="release_notes.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.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="rationale/additional_features.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section boost_bimap_rationale">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="boost_bimap.rationale"></a><a class="link" href="rationale.html" title="Rationale">Rationale</a>
</h2></div></div></div>
<div class="toc"><dl>
<dt><span class="section"><a href="rationale.html#boost_bimap.rationale.general_design">General Design</a></span></dt>
<dt><span class="section"><a href="rationale/additional_features.html">Additional
      Features</a></span></dt>
<dt><span class="section"><a href="rationale/code.html">Code</a></span></dt>
<dt><span class="section"><a href="rationale/the_student_and_the_mentor.html">The
      student and the mentor</a></span></dt>
</dl></div>
<p>
      This section assumes that you have read all other sections, the most of important
      of which being <span class="emphasis"><em>tutorial</em></span>, <span class="emphasis"><em>std::set theory</em></span>
      and the <span class="emphasis"><em>reference</em></span>, and that you have tested the library.
      A lot of effort was invested in making the interface as intuitive and clean
      as possible. If you understand, and hopefully like, the interface of this library,
      it will be a lot easier to read this rationale. The following section is little
      more than a rationale. This library was coded in the context of the Google
      SoC 2006 and the student and mentor were in different continents. A great deal
      of email flowed between Joaquin and Matias. The juiciest parts of the conversations
      where extracted and rearranged here.
    </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>
        To browse the code, you can use the <a href="../doxydoc/index.html" target="_top"><span class="emphasis"><em>Bimap
        Complete Reference</em></span></a>, a doxygen-powered document targeted
        at developers.
      </p></td></tr>
</table></div>
<div class="section boost_bimap_rationale_general_design">
<div class="titlepage"><div><div><h3 class="title">
<a name="boost_bimap.rationale.general_design"></a><a class="link" href="rationale.html#boost_bimap.rationale.general_design" title="General Design">General Design</a>
</h3></div></div></div>
<p>
        The initial explanation includes few features. This section aims to describe
        the general design of the library and excludes details of those features
        that are of lesser importance; these features will be introduced later.
      </p>
<p>
        The design of the library is divided into two parts. The first is the construction
        of a <code class="literal">relation</code> class. This will be the object stored and
        managed by the <code class="literal">multi_index_container</code> core. The idea is
        to make this class as easy as possible to use, while making it efficient
        in terms of memory and access time. This is a cornerstone in the design of
        <span class="bold"><strong>Boost.Bimap</strong></span> and, as you will see in this
        rationale, the rest of the design follows easily.
      </p>
<p>
        The following interface is necessary for the <code class="literal">relation</code>
        class:
      </p>
<pre class="programlisting"><span class="keyword">typedef</span> <span class="special">-</span><span class="identifier">unspecified</span><span class="special">-</span> <span class="identifier">TA</span><span class="special">;</span> <span class="keyword">typedef</span> <span class="special">-</span><span class="identifier">unspecified</span><span class="special">-</span> <span class="identifier">TB</span><span class="special">;</span>

<span class="identifier">TA</span> <span class="identifier">a</span><span class="special">,</span> <span class="identifier">ai</span><span class="special">;</span> <span class="identifier">TB</span> <span class="identifier">b</span><span class="special">,</span> <span class="identifier">bi</span><span class="special">;</span>

<span class="keyword">typedef</span> <span class="identifier">relation</span><span class="special">&lt;</span> <span class="identifier">TA</span><span class="special">,</span> <span class="identifier">TB</span> <span class="special">&gt;</span> <span class="identifier">rel</span><span class="special">;</span>
<span class="identifier">STATIC_ASSERT</span><span class="special">(</span> <span class="identifier">is_same</span><span class="special">&lt;</span> <span class="identifier">rel</span><span class="special">::</span><span class="identifier">left_type</span> <span class="special">,</span> <span class="identifier">TA</span> <span class="special">&gt;::</span><span class="identifier">value</span> <span class="special">);</span>
<span class="identifier">STATIC_ASSERT</span><span class="special">(</span> <span class="identifier">is_same</span><span class="special">&lt;</span> <span class="identifier">rel</span><span class="special">::</span><span class="identifier">right_type</span><span class="special">,</span> <span class="identifier">TB</span> <span class="special">&gt;::</span><span class="identifier">value</span> <span class="special">);</span>

<span class="identifier">rel</span> <span class="identifier">r</span><span class="special">(</span><span class="identifier">ai</span><span class="special">,</span><span class="identifier">bi</span><span class="special">);</span>
<span class="identifier">assert</span><span class="special">(</span> <span class="identifier">r</span><span class="special">.</span><span class="identifier">left</span> <span class="special">==</span> <span class="identifier">ai</span> <span class="special">&amp;&amp;</span> <span class="identifier">r</span><span class="special">.</span><span class="identifier">right</span> <span class="special">==</span> <span class="identifier">bi</span> <span class="special">);</span>

<span class="identifier">r</span><span class="special">.</span><span class="identifier">left</span>  <span class="special">=</span> <span class="identifier">a</span><span class="special">;</span> <span class="identifier">r</span><span class="special">.</span><span class="identifier">right</span> <span class="special">=</span> <span class="identifier">b</span><span class="special">;</span>
<span class="identifier">assert</span><span class="special">(</span> <span class="identifier">r</span><span class="special">.</span><span class="identifier">left</span>  <span class="special">==</span> <span class="identifier">a</span> <span class="special">&amp;&amp;</span> <span class="identifier">r</span><span class="special">.</span><span class="identifier">right</span> <span class="special">==</span> <span class="identifier">b</span> <span class="special">);</span>

<span class="keyword">typedef</span> <span class="identifier">pair_type_by</span><span class="special">&lt;</span> <span class="identifier">member_at</span><span class="special">::</span><span class="identifier">left</span> <span class="special">,</span> <span class="identifier">rel</span> <span class="special">&gt;::</span><span class="identifier">type</span> <span class="identifier">pba_type</span><span class="special">;</span>
<span class="identifier">STATIC_ASSERT</span><span class="special">(</span> <span class="identifier">is_same</span><span class="special">&lt;</span> <span class="identifier">pba_type</span><span class="special">::</span><span class="identifier">first_type</span> <span class="special">,</span> <span class="identifier">TA</span> <span class="special">&gt;::</span><span class="identifier">value</span> <span class="special">);</span>
<span class="identifier">STATIC_ASSERT</span><span class="special">(</span> <span class="identifier">is_same</span><span class="special">&lt;</span> <span class="identifier">pba_type</span><span class="special">::</span><span class="identifier">second_type</span><span class="special">,</span> <span class="identifier">TB</span> <span class="special">&gt;::</span><span class="identifier">value</span> <span class="special">);</span>

<span class="keyword">typedef</span> <span class="identifier">pair_type_by</span><span class="special">&lt;</span> <span class="identifier">member_at</span><span class="special">::</span><span class="identifier">right</span><span class="special">,</span> <span class="identifier">rel</span> <span class="special">&gt;::</span><span class="identifier">type</span> <span class="identifier">pbb_type</span><span class="special">;</span>
<span class="identifier">STATIC_ASSERT</span><span class="special">(</span> <span class="identifier">is_same</span><span class="special">&lt;</span> <span class="identifier">pbb_type</span><span class="special">::</span><span class="identifier">first_type</span> <span class="special">,</span> <span class="identifier">TB</span> <span class="special">&gt;::</span><span class="identifier">value</span> <span class="special">);</span>
<span class="identifier">STATIC_ASSERT</span><span class="special">(</span> <span class="identifier">is_same</span><span class="special">&lt;</span> <span class="identifier">pbb_type</span><span class="special">::</span><span class="identifier">second_type</span><span class="special">,</span> <span class="identifier">TA</span> <span class="special">&gt;::</span><span class="identifier">value</span> <span class="special">);</span>

<span class="identifier">pba_type</span> <span class="identifier">pba</span> <span class="special">=</span> <span class="identifier">pair_by</span><span class="special">&lt;</span> <span class="identifier">member_at</span><span class="special">::</span><span class="identifier">left</span>  <span class="special">&gt;(</span><span class="identifier">r</span><span class="special">);</span>
<span class="identifier">assert</span><span class="special">(</span> <span class="identifier">pba</span><span class="special">.</span><span class="identifier">first</span> <span class="special">==</span> <span class="identifier">r</span><span class="special">.</span><span class="identifier">left</span>  <span class="special">&amp;&amp;</span> <span class="identifier">pba</span><span class="special">.</span><span class="identifier">second</span> <span class="special">==</span> <span class="identifier">r</span><span class="special">.</span><span class="identifier">right</span> <span class="special">);</span>

<span class="identifier">pbb_type</span> <span class="identifier">pbb</span> <span class="special">=</span> <span class="identifier">pair_by</span><span class="special">&lt;</span> <span class="identifier">member_at</span><span class="special">::</span><span class="identifier">right</span> <span class="special">&gt;(</span><span class="identifier">r</span><span class="special">);</span>
<span class="identifier">assert</span><span class="special">(</span> <span class="identifier">pbb</span><span class="special">.</span><span class="identifier">first</span> <span class="special">==</span> <span class="identifier">r</span><span class="special">.</span><span class="identifier">right</span> <span class="special">&amp;&amp;</span> <span class="identifier">pbb</span><span class="special">.</span><span class="identifier">second</span> <span class="special">==</span> <span class="identifier">r</span><span class="special">.</span><span class="identifier">left</span>  <span class="special">);</span>
</pre>
<p>
        <span class="inlinemediaobject"><img src="../images/bimap/relation.png" alt="relation"></span>
      </p>
<p>
        Although this seems straightforward, as will be seen later, it is the most
        difficult code hack of the library. It is indeed very easy if we relax some
        of the efficiency constraints. For example, it is trivial if we allow a relation
        to have greater size than the the sum of those of its components. It is equally
        simple if access speed is not important. One of the first decisions made
        about <span class="bold"><strong>Boost.Bimap</strong></span> was, however, that, in
        order to be useful, it had to achieve zero overhead over the wrapped <span class="bold"><strong>Boost.MultiIndex</strong></span> container. Finally, there is another
        constraint that can be relaxed: conformance to C++ standards, but this is
        quite unacceptable. Let us now suppose that we have coded this class, and
        it conforms to what was required.
      </p>
<p>
        The second part is based on this <code class="literal">relation</code> class. We can
        now view the data in any of three ways: <code class="computeroutput"><span class="identifier">pair</span><span class="special">&lt;</span><span class="identifier">A</span><span class="special">,</span><span class="identifier">B</span><span class="special">&gt;</span></code>,
        <code class="computeroutput"><span class="identifier">relation</span><span class="special">&lt;</span><span class="identifier">A</span><span class="special">,</span><span class="identifier">B</span><span class="special">&gt;</span></code> and <code class="computeroutput"><span class="identifier">pair</span><span class="special">&lt;</span><span class="identifier">B</span><span class="special">,</span><span class="identifier">A</span><span class="special">&gt;</span></code>.
        Suppose that our bimap supports only one-to-one relations. (Other relation
        types are considered additional features in this design.) The proposed interface
        is very simple, and it is based heavily on the concepts of the STL. Given
        a <code class="computeroutput"><span class="identifier">bimap</span><span class="special">&lt;</span><span class="identifier">A</span><span class="special">,</span><span class="identifier">B</span><span class="special">&gt;</span> <span class="identifier">bm</span></code>:
      </p>
<div class="orderedlist"><ol class="orderedlist" type="1">
<li class="listitem">
            <code class="computeroutput"><span class="identifier">bm</span><span class="special">.</span><span class="identifier">left</span></code> is signature-compatible with a
            <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">map</span><span class="special">&lt;</span><span class="identifier">A</span><span class="special">,</span><span class="identifier">B</span><span class="special">&gt;</span></code>
          </li>
<li class="listitem">
            <code class="computeroutput"><span class="identifier">bm</span><span class="special">.</span><span class="identifier">right</span></code> is signature-compatible with
            a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">map</span><span class="special">&lt;</span><span class="identifier">B</span><span class="special">,</span><span class="identifier">A</span><span class="special">&gt;</span></code>
          </li>
<li class="listitem">
            <code class="computeroutput"><span class="identifier">bm</span></code> is signature-compatible
            with a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special">&lt;</span><span class="identifier">relation</span><span class="special">&lt;</span><span class="identifier">A</span><span class="special">,</span><span class="identifier">B</span><span class="special">&gt;</span> <span class="special">&gt;</span></code>
          </li>
</ol></div>
<p>
        <span class="inlinemediaobject"><img src="../images/bimap/simple.bimap.png" alt="simple.bimap"></span>
      </p>
<p>
        This interface is easily learned by users who have a STL background, as well
        as being simple and powerful. This is the general design.
      </p>
<h5>
<a name="boost_bimap.rationale.general_design.h0"></a>
        <span class="phrase"><a name="boost_bimap.rationale.general_design.relation_implementation"></a></span><a class="link" href="rationale.html#boost_bimap.rationale.general_design.relation_implementation">Relation
        Implementation</a>
      </h5>
<p>
        This section explains the details of the actual <code class="literal">relation</code>
        class implementation.
      </p>
<p>
        The first thing that we can imagine is the use of an <code class="literal">union</code>.
        Regrettably, the current C++ standard only allows unions of POD types. For
        the views, we can try a wrapper around a <code class="computeroutput"><span class="identifier">relation</span><span class="special">&lt;</span><span class="identifier">A</span><span class="special">,</span><span class="identifier">B</span><span class="special">&gt;</span></code> that
        has two references named first and second that bind to <code class="computeroutput"><span class="identifier">A</span></code>
        and <code class="computeroutput"><span class="identifier">B</span></code>, or to <code class="computeroutput"><span class="identifier">B</span></code> and <code class="computeroutput"><span class="identifier">A</span></code>.
      </p>
<pre class="programlisting"><span class="identifier">relation</span><span class="special">&lt;</span><span class="identifier">TA</span><span class="special">,</span><span class="identifier">TB</span><span class="special">&gt;</span> <span class="identifier">r</span><span class="special">;</span>

<span class="identifier">const_reference_pair</span><span class="special">&lt;</span><span class="identifier">A</span><span class="special">,</span><span class="identifier">B</span><span class="special">&gt;</span> <span class="identifier">pba</span><span class="special">(</span><span class="identifier">r</span><span class="special">);</span>
<span class="identifier">const_reference_pair</span><span class="special">&lt;</span><span class="identifier">B</span><span class="special">,</span><span class="identifier">A</span><span class="special">&gt;</span> <span class="identifier">pbb</span><span class="special">(</span><span class="identifier">r</span><span class="special">);</span>
</pre>
<p>
        It is not difficult to code the relation class using this, but two references
        are initialized at every access and using of <code class="computeroutput"><span class="identifier">pba</span><span class="special">.</span><span class="identifier">first</span></code>
        will be slower in most compilers than using <code class="computeroutput"><span class="identifier">r</span><span class="special">.</span><span class="identifier">left</span></code> directly
        . There is another hidden drawback of using this scheme: it is not iterator-friendly,
        since the map views iterators must be degraded to <span class="emphasis"><em>Read Write</em></span>
        instead of <span class="emphasis"><em>LValue</em></span>. This will be explained later.
      </p>
<p>
        At first, this seems to be the best we can do with the current C++ standard.
        However there is a solution to this problem that does not conform very well
        to C++ standards but does achieve zero overhead in terms of access time and
        memory, and additionally allows the view iterators to be upgraded to <span class="emphasis"><em>LValue</em></span>
        again.
      </p>
<p>
        In order to use this, the compiler must conform to a layout-compatibility
        clause that is not currently in the standard but is very natural. The additional
        clause imposes that if we have two classes:
      </p>
<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">class_a_b</span>
<span class="special">{</span>
    <span class="identifier">Type1</span> <span class="identifier">name_a</span><span class="special">;</span>
    <span class="identifier">Type2</span> <span class="identifier">name_b</span><span class="special">;</span>
<span class="special">};</span>

<span class="keyword">struct</span> <span class="identifier">class_b_a</span>
<span class="special">{</span>
    <span class="identifier">Type1</span> <span class="identifier">name_b</span><span class="special">;</span>
    <span class="identifier">Type2</span> <span class="identifier">name_a</span><span class="special">;</span>
<span class="special">};</span>
</pre>
<p>
        then the storage layout of <code class="literal">class_a_b</code> is equal to the storage
        layout of <code class="literal">class_b_a</code>. If you are surprised to learn that
        this does not hold in a standards-compliant C++ compiler, welcome to the
        club. It is the natural way to implement it from the point of view of the
        compiler's vendor and is very useful for the developer. Maybe it will be
        included in the standard some day. Every current compiler conforms to this.
      </p>
<p>
        If we are able to count on this, then we can implement an idiom called <code class="literal">mutant</code>.
        The idea is to provide a secure wrapper around <code class="literal">reinterpret_cast</code>.
        A class can declare that it can be viewed using different view classes that
        are storage-compatible with it. Then we use the free function <code class="literal">mutate&lt;view&gt;(mutant)</code>
        to get the view. The <code class="computeroutput"><span class="identifier">mutate</span></code>
        function checks at compile time that the requested view is declared in the
        mutant views list. We implement a class name <code class="computeroutput"><span class="identifier">structured_pair</span></code>
        that is signature-compatible with a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span></code>,
        while the storage layout is configured with a third template parameter. Two
        instances of this template class will provide the views of the relation.
      </p>
<p>
        The thing is that if we want to be standards-compliant, we cannot use this
        approach. It is very annoying not to be able to use something that we know
        will work with every compiler and that is far better than alternatives. So
        -- and this is an important decision -- we have to find a way to use it and
        still make the library standards-compliant.
      </p>
<p>
        The idea is very simple. We code both approaches: the const_reference_pair-based
        and the mutant-based, and use the mutant approach if the compiler is compliant
        with our new layout-compatible clause. If the compiler really messes things
        up, we degrade the performance of the bimap a little. The only drawback here
        is that, while the mutant approach allows to make <span class="emphasis"><em>LValue</em></span>
        iterators, we have to degrade them to <span class="emphasis"><em>Read Write</em></span> in
        both cases, because we require that the same code be compilable by any standards-compliant
        compiler.
      </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>
          Testing this approach in all the supported compilers indicated that the
          mutant idiom was always supported. The strictly compliant version was removed
          from the code because it was never used.
        </p></td></tr>
</table></div>
<h5>
<a name="boost_bimap.rationale.general_design.h1"></a>
        <span class="phrase"><a name="boost_bimap.rationale.general_design.bimap_implementation"></a></span><a class="link" href="rationale.html#boost_bimap.rationale.general_design.bimap_implementation">Bimap
        Implementation</a>
      </h5>
<p>
        The core of bimap will be obviously a <code class="computeroutput"><span class="identifier">multi_index_container</span></code>.
        The basic idea to tackle the implementation of the bimap class is to use
        <code class="literal">iterator_adaptor</code> to convert the iterators from Boost.MultiIndex
        to the <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">map</span></code> and <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span></code> behaviour.
        The <code class="computeroutput"><span class="identifier">map_view</span></code> and the <code class="computeroutput"><span class="identifier">set_view</span></code> can be implemented directly using
        this new transformed iterators and a wrapper around each index of the core
        container. However, there is a hidden idiom here, that, once coded, will
        be very useful for other parts of this library and for Boost.MRU library.
        Following the ideas from <code class="computeroutput"><span class="identifier">iterator_adaptor</span></code>,
        Boost.Bimap views are implemented using a <code class="literal">container_adaptor</code>.
        There are several template classes (for example <code class="computeroutput"><span class="identifier">map_adaptor</span></code>
        and <code class="computeroutput"><span class="identifier">set_adaptor</span></code>) that take
        a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">map</span></code> signature-conformant class and new
        iterators, and adapt the container so it now uses this iterators instead
        of the originals. For example, if you have a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">*&gt;</span></code>,
        you can build other container that behaves exactly as a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">&gt;</span></code> using
        <code class="computeroutput"><span class="identifier">set_adaptor</span></code> and <code class="literal">iterator_adaptor</code>.
        The combined use of this two tools is very powerful. A <code class="literal">container_adaptor</code>
        can take classes that do not fulfil all the requirements of the adapted container.
        The new container must define these missing functions.
      </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="release_notes.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.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="rationale/additional_features.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>