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