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