1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Rationale</title> 5<link rel="stylesheet" href="../boostbook.css" type="text/css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="../index.html" title="Chapter 1. Boost.Bimap"> 8<link rel="up" href="../index.html" title="Chapter 1. Boost.Bimap"> 9<link rel="prev" href="release_notes.html" title="Release notes"> 10<link rel="next" href="rationale/additional_features.html" title="Additional Features"> 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="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> 24</div> 25<div class="section"> 26<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 27<a name="boost_bimap.rationale"></a><a class="link" href="rationale.html" title="Rationale">Rationale</a> 28</h2></div></div></div> 29<div class="toc"><dl class="toc"> 30<dt><span class="section"><a href="rationale.html#boost_bimap.rationale.general_design">General Design</a></span></dt> 31<dt><span class="section"><a href="rationale/additional_features.html">Additional 32 Features</a></span></dt> 33<dt><span class="section"><a href="rationale/code.html">Code</a></span></dt> 34<dt><span class="section"><a href="rationale/the_student_and_the_mentor.html">The 35 student and the mentor</a></span></dt> 36</dl></div> 37<p> 38 This section assumes that you have read all other sections, the most of important 39 of which being <span class="emphasis"><em>tutorial</em></span>, <span class="emphasis"><em>std::set theory</em></span> 40 and the <span class="emphasis"><em>reference</em></span>, and that you have tested the library. 41 A lot of effort was invested in making the interface as intuitive and clean 42 as possible. If you understand, and hopefully like, the interface of this library, 43 it will be a lot easier to read this rationale. The following section is little 44 more than a rationale. This library was coded in the context of the Google 45 SoC 2006 and the student and mentor were in different continents. A great deal 46 of email flowed between Joaquin and Matias. The juiciest parts of the conversations 47 where extracted and rearranged here. 48 </p> 49<div class="note"><table border="0" summary="Note"> 50<tr> 51<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../../../doc/src/images/note.png"></td> 52<th align="left">Note</th> 53</tr> 54<tr><td align="left" valign="top"><p> 55 To browse the code, you can use the <a href="../doxydoc/index.html" target="_top"><span class="emphasis"><em>Bimap 56 Complete Reference</em></span></a>, a doxygen-powered document targeted 57 at developers. 58 </p></td></tr> 59</table></div> 60<div class="section"> 61<div class="titlepage"><div><div><h3 class="title"> 62<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> 63</h3></div></div></div> 64<p> 65 The initial explanation includes few features. This section aims to describe 66 the general design of the library and excludes details of those features 67 that are of lesser importance; these features will be introduced later. 68 </p> 69<p> 70 The design of the library is divided into two parts. The first is the construction 71 of a <code class="literal">relation</code> class. This will be the object stored and 72 managed by the <code class="literal">multi_index_container</code> core. The idea is 73 to make this class as easy as possible to use, while making it efficient 74 in terms of memory and access time. This is a cornerstone in the design of 75 <span class="bold"><strong>Boost.Bimap</strong></span> and, as you will see in this 76 rationale, the rest of the design follows easily. 77 </p> 78<p> 79 The following interface is necessary for the <code class="literal">relation</code> 80 class: 81 </p> 82<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> 83 84<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> 85 86<span class="keyword">typedef</span> <span class="identifier">relation</span><span class="special"><</span> <span class="identifier">TA</span><span class="special">,</span> <span class="identifier">TB</span> <span class="special">></span> <span class="identifier">rel</span><span class="special">;</span> 87<span class="identifier">STATIC_ASSERT</span><span class="special">(</span> <span class="identifier">is_same</span><span class="special"><</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">>::</span><span class="identifier">value</span> <span class="special">);</span> 88<span class="identifier">STATIC_ASSERT</span><span class="special">(</span> <span class="identifier">is_same</span><span class="special"><</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">>::</span><span class="identifier">value</span> <span class="special">);</span> 89 90<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> 91<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">&&</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> 92 93<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> 94<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">&&</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> 95 96<span class="keyword">typedef</span> <span class="identifier">pair_type_by</span><span class="special"><</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">>::</span><span class="identifier">type</span> <span class="identifier">pba_type</span><span class="special">;</span> 97<span class="identifier">STATIC_ASSERT</span><span class="special">(</span> <span class="identifier">is_same</span><span class="special"><</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">>::</span><span class="identifier">value</span> <span class="special">);</span> 98<span class="identifier">STATIC_ASSERT</span><span class="special">(</span> <span class="identifier">is_same</span><span class="special"><</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">>::</span><span class="identifier">value</span> <span class="special">);</span> 99 100<span class="keyword">typedef</span> <span class="identifier">pair_type_by</span><span class="special"><</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">>::</span><span class="identifier">type</span> <span class="identifier">pbb_type</span><span class="special">;</span> 101<span class="identifier">STATIC_ASSERT</span><span class="special">(</span> <span class="identifier">is_same</span><span class="special"><</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">>::</span><span class="identifier">value</span> <span class="special">);</span> 102<span class="identifier">STATIC_ASSERT</span><span class="special">(</span> <span class="identifier">is_same</span><span class="special"><</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">>::</span><span class="identifier">value</span> <span class="special">);</span> 103 104<span class="identifier">pba_type</span> <span class="identifier">pba</span> <span class="special">=</span> <span class="identifier">pair_by</span><span class="special"><</span> <span class="identifier">member_at</span><span class="special">::</span><span class="identifier">left</span> <span class="special">>(</span><span class="identifier">r</span><span class="special">);</span> 105<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">&&</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> 106 107<span class="identifier">pbb_type</span> <span class="identifier">pbb</span> <span class="special">=</span> <span class="identifier">pair_by</span><span class="special"><</span> <span class="identifier">member_at</span><span class="special">::</span><span class="identifier">right</span> <span class="special">>(</span><span class="identifier">r</span><span class="special">);</span> 108<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">&&</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> 109</pre> 110<p> 111 <span class="inlinemediaobject"><img src="../images/bimap/relation.png" alt="relation"></span> 112 </p> 113<p> 114 Although this seems straightforward, as will be seen later, it is the most 115 difficult code hack of the library. It is indeed very easy if we relax some 116 of the efficiency constraints. For example, it is trivial if we allow a relation 117 to have greater size than the the sum of those of its components. It is equally 118 simple if access speed is not important. One of the first decisions made 119 about <span class="bold"><strong>Boost.Bimap</strong></span> was, however, that, in 120 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 121 constraint that can be relaxed: conformance to C++ standards, but this is 122 quite unacceptable. Let us now suppose that we have coded this class, and 123 it conforms to what was required. 124 </p> 125<p> 126 The second part is based on this <code class="literal">relation</code> class. We can 127 now view the data in any of three ways: <code class="computeroutput"><span class="identifier">pair</span><span class="special"><</span><span class="identifier">A</span><span class="special">,</span><span class="identifier">B</span><span class="special">></span></code>, 128 <code class="computeroutput"><span class="identifier">relation</span><span class="special"><</span><span class="identifier">A</span><span class="special">,</span><span class="identifier">B</span><span class="special">></span></code> and <code class="computeroutput"><span class="identifier">pair</span><span class="special"><</span><span class="identifier">B</span><span class="special">,</span><span class="identifier">A</span><span class="special">></span></code>. 129 Suppose that our bimap supports only one-to-one relations. (Other relation 130 types are considered additional features in this design.) The proposed interface 131 is very simple, and it is based heavily on the concepts of the STL. Given 132 a <code class="computeroutput"><span class="identifier">bimap</span><span class="special"><</span><span class="identifier">A</span><span class="special">,</span><span class="identifier">B</span><span class="special">></span> <span class="identifier">bm</span></code>: 133 </p> 134<div class="orderedlist"><ol class="orderedlist" type="1"> 135<li class="listitem"> 136 <code class="computeroutput"><span class="identifier">bm</span><span class="special">.</span><span class="identifier">left</span></code> is signature-compatible with a 137 <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">map</span><span class="special"><</span><span class="identifier">A</span><span class="special">,</span><span class="identifier">B</span><span class="special">></span></code> 138 </li> 139<li class="listitem"> 140 <code class="computeroutput"><span class="identifier">bm</span><span class="special">.</span><span class="identifier">right</span></code> is signature-compatible with 141 a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">map</span><span class="special"><</span><span class="identifier">B</span><span class="special">,</span><span class="identifier">A</span><span class="special">></span></code> 142 </li> 143<li class="listitem"> 144 <code class="computeroutput"><span class="identifier">bm</span></code> is signature-compatible 145 with a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special"><</span><span class="identifier">relation</span><span class="special"><</span><span class="identifier">A</span><span class="special">,</span><span class="identifier">B</span><span class="special">></span> <span class="special">></span></code> 146 </li> 147</ol></div> 148<p> 149 <span class="inlinemediaobject"><img src="../images/bimap/simple.bimap.png" alt="simple.bimap"></span> 150 </p> 151<p> 152 This interface is easily learned by users who have a STL background, as well 153 as being simple and powerful. This is the general design. 154 </p> 155<h5> 156<a name="boost_bimap.rationale.general_design.h0"></a> 157 <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 158 Implementation</a> 159 </h5> 160<p> 161 This section explains the details of the actual <code class="literal">relation</code> 162 class implementation. 163 </p> 164<p> 165 The first thing that we can imagine is the use of an <code class="literal">union</code>. 166 Regrettably, the current C++ standard only allows unions of POD types. For 167 the views, we can try a wrapper around a <code class="computeroutput"><span class="identifier">relation</span><span class="special"><</span><span class="identifier">A</span><span class="special">,</span><span class="identifier">B</span><span class="special">></span></code> that 168 has two references named first and second that bind to <code class="computeroutput"><span class="identifier">A</span></code> 169 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>. 170 </p> 171<pre class="programlisting"><span class="identifier">relation</span><span class="special"><</span><span class="identifier">TA</span><span class="special">,</span><span class="identifier">TB</span><span class="special">></span> <span class="identifier">r</span><span class="special">;</span> 172 173<span class="identifier">const_reference_pair</span><span class="special"><</span><span class="identifier">A</span><span class="special">,</span><span class="identifier">B</span><span class="special">></span> <span class="identifier">pba</span><span class="special">(</span><span class="identifier">r</span><span class="special">);</span> 174<span class="identifier">const_reference_pair</span><span class="special"><</span><span class="identifier">B</span><span class="special">,</span><span class="identifier">A</span><span class="special">></span> <span class="identifier">pbb</span><span class="special">(</span><span class="identifier">r</span><span class="special">);</span> 175</pre> 176<p> 177 It is not difficult to code the relation class using this, but two references 178 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> 179 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 180 . There is another hidden drawback of using this scheme: it is not iterator-friendly, 181 since the map views iterators must be degraded to <span class="emphasis"><em>Read Write</em></span> 182 instead of <span class="emphasis"><em>LValue</em></span>. This will be explained later. 183 </p> 184<p> 185 At first, this seems to be the best we can do with the current C++ standard. 186 However there is a solution to this problem that does not conform very well 187 to C++ standards but does achieve zero overhead in terms of access time and 188 memory, and additionally allows the view iterators to be upgraded to <span class="emphasis"><em>LValue</em></span> 189 again. 190 </p> 191<p> 192 In order to use this, the compiler must conform to a layout-compatibility 193 clause that is not currently in the standard but is very natural. The additional 194 clause imposes that if we have two classes: 195 </p> 196<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">class_a_b</span> 197<span class="special">{</span> 198 <span class="identifier">Type1</span> <span class="identifier">name_a</span><span class="special">;</span> 199 <span class="identifier">Type2</span> <span class="identifier">name_b</span><span class="special">;</span> 200<span class="special">};</span> 201 202<span class="keyword">struct</span> <span class="identifier">class_b_a</span> 203<span class="special">{</span> 204 <span class="identifier">Type1</span> <span class="identifier">name_b</span><span class="special">;</span> 205 <span class="identifier">Type2</span> <span class="identifier">name_a</span><span class="special">;</span> 206<span class="special">};</span> 207</pre> 208<p> 209 then the storage layout of <code class="literal">class_a_b</code> is equal to the storage 210 layout of <code class="literal">class_b_a</code>. If you are surprised to learn that 211 this does not hold in a standards-compliant C++ compiler, welcome to the 212 club. It is the natural way to implement it from the point of view of the 213 compiler's vendor and is very useful for the developer. Maybe it will be 214 included in the standard some day. Every current compiler conforms to this. 215 </p> 216<p> 217 If we are able to count on this, then we can implement an idiom called <code class="literal">mutant</code>. 218 The idea is to provide a secure wrapper around <code class="literal">reinterpret_cast</code>. 219 A class can declare that it can be viewed using different view classes that 220 are storage-compatible with it. Then we use the free function <code class="literal">mutate<view>(mutant)</code> 221 to get the view. The <code class="computeroutput"><span class="identifier">mutate</span></code> 222 function checks at compile time that the requested view is declared in the 223 mutant views list. We implement a class name <code class="computeroutput"><span class="identifier">structured_pair</span></code> 224 that is signature-compatible with a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span></code>, 225 while the storage layout is configured with a third template parameter. Two 226 instances of this template class will provide the views of the relation. 227 </p> 228<p> 229 The thing is that if we want to be standards-compliant, we cannot use this 230 approach. It is very annoying not to be able to use something that we know 231 will work with every compiler and that is far better than alternatives. So 232 -- and this is an important decision -- we have to find a way to use it and 233 still make the library standards-compliant. 234 </p> 235<p> 236 The idea is very simple. We code both approaches: the const_reference_pair-based 237 and the mutant-based, and use the mutant approach if the compiler is compliant 238 with our new layout-compatible clause. If the compiler really messes things 239 up, we degrade the performance of the bimap a little. The only drawback here 240 is that, while the mutant approach allows to make <span class="emphasis"><em>LValue</em></span> 241 iterators, we have to degrade them to <span class="emphasis"><em>Read Write</em></span> in 242 both cases, because we require that the same code be compilable by any standards-compliant 243 compiler. 244 </p> 245<div class="note"><table border="0" summary="Note"> 246<tr> 247<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../../../doc/src/images/note.png"></td> 248<th align="left">Note</th> 249</tr> 250<tr><td align="left" valign="top"><p> 251 Testing this approach in all the supported compilers indicated that the 252 mutant idiom was always supported. The strictly compliant version was removed 253 from the code because it was never used. 254 </p></td></tr> 255</table></div> 256<h5> 257<a name="boost_bimap.rationale.general_design.h1"></a> 258 <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 259 Implementation</a> 260 </h5> 261<p> 262 The core of bimap will be obviously a <code class="computeroutput"><span class="identifier">multi_index_container</span></code>. 263 The basic idea to tackle the implementation of the bimap class is to use 264 <code class="literal">iterator_adaptor</code> to convert the iterators from Boost.MultiIndex 265 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. 266 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 267 this new transformed iterators and a wrapper around each index of the core 268 container. However, there is a hidden idiom here, that, once coded, will 269 be very useful for other parts of this library and for Boost.MRU library. 270 Following the ideas from <code class="computeroutput"><span class="identifier">iterator_adaptor</span></code>, 271 Boost.Bimap views are implemented using a <code class="literal">container_adaptor</code>. 272 There are several template classes (for example <code class="computeroutput"><span class="identifier">map_adaptor</span></code> 273 and <code class="computeroutput"><span class="identifier">set_adaptor</span></code>) that take 274 a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">map</span></code> signature-conformant class and new 275 iterators, and adapt the container so it now uses this iterators instead 276 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"><</span><span class="keyword">int</span><span class="special">*></span></code>, 277 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"><</span><span class="keyword">int</span><span class="special">></span></code> using 278 <code class="computeroutput"><span class="identifier">set_adaptor</span></code> and <code class="literal">iterator_adaptor</code>. 279 The combined use of this two tools is very powerful. A <code class="literal">container_adaptor</code> 280 can take classes that do not fulfill all the requirements of the adapted 281 container. The new container must define these missing functions. 282 </p> 283</div> 284</div> 285<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 286<td align="left"></td> 287<td align="right"><div class="copyright-footer">Copyright © 2006-2012 Matias Capeletto<p> 288 Distributed under the Boost Software License, Version 1.0. (See accompanying 289 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>) 290 </p> 291</div></td> 292</tr></table> 293<hr> 294<div class="spirit-nav"> 295<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> 296</div> 297</body> 298</html> 299
