doc/html/poly_collection.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
   2 <html>
   3 <head>
   4 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   5 <title>Chapter&#160;28.&#160;Boost.PolyCollection</title>
   6 <link rel="stylesheet" href="../../doc/src/boostbook.css" type="text/css">
   7 <meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
   8 <link rel="home" href="index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
   9 <link rel="up" href="libraries.html" title="Part&#160;I.&#160;The Boost C++ Libraries (BoostBook Subset)">
  10 <link rel="prev" href="auxiliary.html" title="Auxiliary Components">
  11 <link rel="next" href="poly_collection/an_efficient_polymorphic_data_st.html" title="An efficient polymorphic data structure">
  12 </head>
  13 <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
  14 <table cellpadding="2" width="100%"><tr>
  15 <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../boost.png"></td>
  16 <td align="center"><a href="../../index.html">Home</a></td>
  17 <td align="center"><a href="../../libs/libraries.htm">Libraries</a></td>
  18 <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
  19 <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
  20 <td align="center"><a href="../../more/index.htm">More</a></td>
  21 </tr></table>
  22 <hr>
  23 <div class="spirit-nav">
  24 <a accesskey="p" href="auxiliary.html"><img src="../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="libraries.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="poly_collection/an_efficient_polymorphic_data_st.html"><img src="../../doc/src/images/next.png" alt="Next"></a>
  25 </div>
  26 <div class="chapter">
  27 <div class="titlepage"><div>
  28 <div><h2 class="title">
  29 <a name="poly_collection"></a>Chapter&#160;28.&#160;Boost.PolyCollection</h2></div>
  30 <div><div class="author"><h3 class="author">
  31 <span class="firstname">Joaqu&#237;n M</span> <span class="surname">L&#243;pez Mu&#241;oz</span>
  32 </h3></div></div>
  33 <div><p class="copyright">Copyright &#169; 2016-2019 Joaqu&#237;n
  34       M L&#243;pez Mu&#241;oz</p></div>
  35 <div><div class="legalnotice">
  36 <a name="poly_collection.legal"></a><p>
  37         Distributed under the Boost Software License, Version 1.0. (See accompanying
  38         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>)
  39       </p>
  40 </div></div>
  41 </div></div>
  42 <div class="toc">
  43 <p><b>Table of Contents</b></p>
  44 <dl class="toc">
  45 <dt><span class="section"><a href="poly_collection.html#poly_collection.introduction">Introduction</a></span></dt>
  46 <dt><span class="section"><a href="poly_collection/an_efficient_polymorphic_data_st.html">An efficient
  47     polymorphic data structure</a></span></dt>
  48 <dt><span class="section"><a href="poly_collection/tutorial.html">Tutorial</a></span></dt>
  49 <dd><dl>
  50 <dt><span class="section"><a href="poly_collection/tutorial.html#poly_collection.tutorial.basics">Basics</a></span></dt>
  51 <dt><span class="section"><a href="poly_collection/tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature">Deeper
  52       into the segmented nature of Boost.PolyCollection</a></span></dt>
  53 <dt><span class="section"><a href="poly_collection/tutorial.html#poly_collection.tutorial.insertion_and_emplacement">Insertion
  54       and emplacement</a></span></dt>
  55 <dt><span class="section"><a href="poly_collection/tutorial.html#poly_collection.tutorial.exceptions">Exceptions</a></span></dt>
  56 <dt><span class="section"><a href="poly_collection/tutorial.html#poly_collection.tutorial.algorithms">Algorithms</a></span></dt>
  57 </dl></dd>
  58 <dt><span class="section"><a href="poly_collection/performance.html">Performance</a></span></dt>
  59 <dd><dl>
  60 <dt><span class="section"><a href="poly_collection/performance.html#poly_collection.performance.container_definitions">Container
  61       definitions</a></span></dt>
  62 <dt><span class="section"><a href="poly_collection/performance.html#poly_collection.performance.insertion_tests">Insertion
  63       tests</a></span></dt>
  64 <dt><span class="section"><a href="poly_collection/performance.html#poly_collection.performance.processing_tests">Processing
  65       tests</a></span></dt>
  66 </dl></dd>
  67 <dt><span class="section"><a href="poly_collection/reference.html">Reference</a></span></dt>
  68 <dd><dl>
  69 <dt><span class="section"><a href="poly_collection/reference.html#poly_collection.reference.polymorphism_models">Polymorphism
  70       models</a></span></dt>
  71 <dt><span class="section"><a href="poly_collection/reference.html#poly_collection.reference.polymorphic_containers">Polymorphic
  72       containers</a></span></dt>
  73 <dt><span class="section"><a href="poly_collection/reference.html#poly_collection.reference.header_boost_poly_collection_exc">Header
  74       <code class="computeroutput"><span class="string">"boost/poly_collection/exception.hpp"</span></code>
  75       synopsis</a></span></dt>
  76 <dt><span class="section"><a href="poly_collection/reference.html#poly_collection.reference.header_boost_poly_collection_bas">Header
  77       <code class="computeroutput"><span class="string">"boost/poly_collection/base_collection_fwd.hpp"</span></code>
  78       synopsis</a></span></dt>
  79 <dt><span class="section"><a href="poly_collection/reference.html#poly_collection.reference.header_boost_poly_collection_ba0">Header
  80       <code class="computeroutput"><span class="string">"boost/poly_collection/base_collection.hpp"</span></code>
  81       synopsis</a></span></dt>
  82 <dt><span class="section"><a href="poly_collection/reference.html#poly_collection.reference.header_boost_poly_collection_fun">Header
  83       <code class="computeroutput"><span class="string">"boost/poly_collection/function_collection_fwd.hpp"</span></code>
  84       synopsis</a></span></dt>
  85 <dt><span class="section"><a href="poly_collection/reference.html#poly_collection.reference.header_boost_poly_collection_fu0">Header
  86       <code class="computeroutput"><span class="string">"boost/poly_collection/function_collection.hpp"</span></code>
  87       synopsis</a></span></dt>
  88 <dt><span class="section"><a href="poly_collection/reference.html#poly_collection.reference.header_boost_poly_collection_any">Header
  89       <code class="computeroutput"><span class="string">"boost/poly_collection/any_collection_fwd.hpp"</span></code>
  90       synopsis</a></span></dt>
  91 <dt><span class="section"><a href="poly_collection/reference.html#poly_collection.reference.header_boost_poly_collection_an0">Header
  92       <code class="computeroutput"><span class="string">"boost/poly_collection/any_collection.hpp"</span></code>
  93       synopsis</a></span></dt>
  94 <dt><span class="section"><a href="poly_collection/reference.html#poly_collection.reference.header_boost_poly_collection_alg">Header
  95       <code class="computeroutput"><span class="string">"boost/poly_collection/algorithm.hpp"</span></code>
  96       synopsis</a></span></dt>
  97 </dl></dd>
  98 <dt><span class="section"><a href="poly_collection/future_work.html">Future work</a></span></dt>
  99 <dd><dl>
 100 <dt><span class="section"><a href="poly_collection/future_work.html#poly_collection.future_work.alternative_rtti_systems">Alternative
 101       RTTI systems</a></span></dt>
 102 <dt><span class="section"><a href="poly_collection/future_work.html#poly_collection.future_work.copy_traits">Copy traits</a></span></dt>
 103 <dt><span class="section"><a href="poly_collection/future_work.html#poly_collection.future_work.parallel_algorithms">Parallel
 104       algorithms</a></span></dt>
 105 <dt><span class="section"><a href="poly_collection/future_work.html#poly_collection.future_work.variant_collection"><code class="computeroutput"><span class="identifier">variant_collection</span></code></a></span></dt>
 106 <dt><span class="section"><a href="poly_collection/future_work.html#poly_collection.future_work.ordered_polymorphic_collections">Ordered
 107       polymorphic collections</a></span></dt>
 108 </dl></dd>
 109 <dt><span class="section"><a href="poly_collection/release_notes.html">Release notes</a></span></dt>
 110 <dd><dl>
 111 <dt><span class="section"><a href="poly_collection/release_notes.html#poly_collection.release_notes.boost_1_72">Boost 1.72</a></span></dt>
 112 <dt><span class="section"><a href="poly_collection/release_notes.html#poly_collection.release_notes.boost_1_71">Boost 1.71</a></span></dt>
 113 <dt><span class="section"><a href="poly_collection/release_notes.html#poly_collection.release_notes.boost_1_70">Boost 1.70</a></span></dt>
 114 <dt><span class="section"><a href="poly_collection/release_notes.html#poly_collection.release_notes.boost_1_69">Boost 1.69</a></span></dt>
 115 <dt><span class="section"><a href="poly_collection/release_notes.html#poly_collection.release_notes.boost_1_67">Boost 1.67</a></span></dt>
 116 <dt><span class="section"><a href="poly_collection/release_notes.html#poly_collection.release_notes.boost_1_66">Boost 1.66</a></span></dt>
 117 <dt><span class="section"><a href="poly_collection/release_notes.html#poly_collection.release_notes.boost_1_65">Boost 1.65</a></span></dt>
 118 </dl></dd>
 119 <dt><span class="section"><a href="poly_collection/acknowledgments.html">Acknowledgments</a></span></dt>
 120 </dl>
 121 </div>
 122 <div class="section">
 123 <div class="titlepage"><div><div><h2 class="title" style="clear: both">
 124 <a name="poly_collection.introduction"></a><a class="link" href="poly_collection.html#poly_collection.introduction" title="Introduction">Introduction</a>
 125 </h2></div></div></div>
 126 <p>
 127       Dynamic polymorphism in C++ requires that objects (such as instances of classes
 128       derived from an abstract base) be accessed through an indirection pointer because
 129       their actual <span class="emphasis"><em>type</em></span> and <span class="emphasis"><em>size</em></span> are not
 130       known at the point of usage. As a consequence, regular containers cannot store
 131       polymorphic objects directly: the usual workaround is to have containers of
 132       pointers to heap-allocated elements. In modern computer architectures this
 133       pattern incurs two types of inefficiency:
 134     </p>
 135 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
 136 <li class="listitem">
 137           The lack of memory contiguity produced by heap allocation degrades CPU
 138           cache performance.
 139         </li>
 140 <li class="listitem">
 141           Executing virtual operations on a sequence of polymorphic objects whose
 142           actual types differ from one to the next results in failures in <a href="https://en.wikipedia.org/wiki/Branch_predictor" target="_top">branch prediction</a>
 143           and a lower execution speed.
 144         </li>
 145 </ul></div>
 146 <p>
 147       When the particular traversal order is not relevant to the user application,
 148       Boost.PolyCollection proposes an alternative data structure that restores memory
 149       contiguity and packs elements according to their concrete type. Three container
 150       class templates are provided:
 151     </p>
 152 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
 153 <li class="listitem">
 154           <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span></code>
 155         </li>
 156 <li class="listitem">
 157           <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span></code>
 158         </li>
 159 <li class="listitem">
 160           <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span></code>
 161         </li>
 162 </ul></div>
 163 <p>
 164       respectively dealing with three different types of dynamic polymorphism available
 165       in C++:
 166     </p>
 167 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
 168 <li class="listitem">
 169           Classic base/derived or OOP polymorphism.
 170         </li>
 171 <li class="listitem">
 172           Function wrapping in the spirit of <a href="http://en.cppreference.com/w/cpp/utility/functional/function" target="_top"><code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">function</span></code></a>.
 173         </li>
 174 <li class="listitem">
 175           So-called <a href="https://en.wikipedia.org/wiki/Duck_typing" target="_top"><span class="emphasis"><em>duck
 176           typing</em></span></a> as implemented by <a href="../../libs/type_erasure" target="_top">Boost.TypeErasure</a>.
 177         </li>
 178 </ul></div>
 179 <p>
 180       The interface of these containers closely follows that of standard containers.
 181       Additionally, the library provides versions of many of the standard library
 182       algorithms (including <a href="http://en.cppreference.com/w/cpp/algorithm/for_each" target="_top"><code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">for_each</span></code></a>)
 183       with improved performance and a special feature called <span class="emphasis"><em>type restitution</em></span>
 184       that allows user code to provide clues on the concrete types of the elements
 185       stored for further opportunities of increased efficiency related to inlining
 186       and <a href="http://hubicka.blogspot.com.es/2014/01/devirtualization-in-c-part-1.html" target="_top"><span class="emphasis"><em>devirtualization</em></span></a>.
 187     </p>
 188 <div class="note"><table border="0" summary="Note">
 189 <tr>
 190 <td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../doc/src/images/note.png"></td>
 191 <th align="left">Note</th>
 192 </tr>
 193 <tr><td align="left" valign="top"><p>
 194         Boost.PolyCollection is a header-only library. C++11 support is required.
 195         The library has been verified to work with Visual Studio 2015, GCC 4.8 and
 196         Clang 3.3.
 197       </p></td></tr>
 198 </table></div>
 199 </div>
 200 </div>
 201 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 202 <td align="left"><p><small>Last revised: December 10, 2019 at 00:26:27 GMT</small></p></td>
 203 <td align="right"><div class="copyright-footer"></div></td>
 204 </tr></table>
 205 <hr>
 206 <div class="spirit-nav">
 207 <a accesskey="p" href="auxiliary.html"><img src="../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="libraries.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="poly_collection/an_efficient_polymorphic_data_st.html"><img src="../../doc/src/images/next.png" alt="Next"></a>
 208 </div>
 209 </body>
 210 </html>