diff options
Diffstat (limited to 'doc/html/poly_collection/tutorial.html')
| -rw-r--r-- | doc/html/poly_collection/tutorial.html | 1234 |
1 files changed, 1234 insertions, 0 deletions
diff --git a/doc/html/poly_collection/tutorial.html b/doc/html/poly_collection/tutorial.html new file mode 100644 index 0000000000..bcd735395e --- /dev/null +++ b/doc/html/poly_collection/tutorial.html @@ -0,0 +1,1234 @@ +<!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>Tutorial</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="../poly_collection.html" title="Chapter 27. Boost.PolyCollection"> +<link rel="prev" href="an_efficient_polymorphic_data_st.html" title="An efficient polymorphic data structure"> +<link rel="next" href="performance.html" title="Performance"> +</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="an_efficient_polymorphic_data_st.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../poly_collection.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="performance.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> +</div> +<div class="section"> +<div class="titlepage"><div><div><h2 class="title" style="clear: both"> +<a name="poly_collection.tutorial"></a><a class="link" href="tutorial.html" title="Tutorial">Tutorial</a> +</h2></div></div></div> +<div class="toc"><dl class="toc"> +<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.basics">Basics</a></span></dt> +<dt><span class="section"><a href="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="tutorial.html#poly_collection.tutorial.insertion_and_emplacement">Insertion + and emplacement</a></span></dt> +<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.exceptions">Exceptions</a></span></dt> +<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.algorithms">Algorithms</a></span></dt> +</dl></div> +<div class="section"> +<div class="titlepage"><div><div><h3 class="title"> +<a name="poly_collection.tutorial.basics"></a><a class="link" href="tutorial.html#poly_collection.tutorial.basics" title="Basics">Basics</a> +</h3></div></div></div> +<div class="toc"><dl class="toc"> +<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.basics.boost_base_collection"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span></code></a></span></dt> +<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.basics.boost_function_collection"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span></code></a></span></dt> +<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.basics.boost_any_collection"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span></code></a></span></dt> +</dl></div> +<div class="section"> +<div class="titlepage"><div><div><h4 class="title"> +<a name="poly_collection.tutorial.basics.boost_base_collection"></a><a class="link" href="tutorial.html#poly_collection.tutorial.basics.boost_base_collection" title="boost::base_collection"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span></code></a> +</h4></div></div></div> +<p> + (Code samples from <a href="../../../libs/poly_collection/example/basic_base.cpp" target="_top"><code class="computeroutput"><span class="identifier">basic_base</span><span class="special">.</span><span class="identifier">cpp</span></code></a>.) + </p> +<p> + Imagine we are developing a role playing game in C++ where sprites are + rendered on screen; for the purposes of illustration we can model rendering + simply as outputting some information to a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span></code>: + </p> +<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">sprite</span> +<span class="special">{</span> + <span class="identifier">sprite</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">id</span><span class="special">):</span><span class="identifier">id</span><span class="special">(</span><span class="identifier">id</span><span class="special">){}</span> + <span class="keyword">virtual</span> <span class="special">~</span><span class="identifier">sprite</span><span class="special">()=</span><span class="keyword">default</span><span class="special">;</span> + <span class="keyword">virtual</span> <span class="keyword">void</span> <span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&</span> <span class="identifier">os</span><span class="special">)</span><span class="keyword">const</span><span class="special">=</span><span class="number">0</span><span class="special">;</span> + + <span class="keyword">int</span> <span class="identifier">id</span><span class="special">;</span> +<span class="special">};</span> +</pre> +<p> + The game features warriors, juggernauts (a special type of warrior) and + goblins, each represented by its own class derived (directly or indirectly) + from <code class="computeroutput"><span class="identifier">sprite</span></code>: + </p> +<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">warrior</span><span class="special">:</span><span class="identifier">sprite</span> +<span class="special">{</span> + <span class="keyword">using</span> <span class="identifier">sprite</span><span class="special">::</span><span class="identifier">sprite</span><span class="special">;</span> + <span class="identifier">warrior</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="identifier">rank</span><span class="special">,</span><span class="keyword">int</span> <span class="identifier">id</span><span class="special">):</span><span class="identifier">sprite</span><span class="special">{</span><span class="identifier">id</span><span class="special">},</span><span class="identifier">rank</span><span class="special">{</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">move</span><span class="special">(</span><span class="identifier">rank</span><span class="special">)}{}</span> + + <span class="keyword">void</span> <span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&</span> <span class="identifier">os</span><span class="special">)</span><span class="keyword">const</span> <span class="identifier">override</span><span class="special">{</span><span class="identifier">os</span><span class="special"><<</span><span class="identifier">rank</span><span class="special"><<</span><span class="string">" "</span><span class="special"><<</span><span class="identifier">id</span><span class="special">;};</span> + + <span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="identifier">rank</span><span class="special">=</span><span class="string">"warrior"</span><span class="special">;</span> +<span class="special">};</span> + +<span class="keyword">struct</span> <span class="identifier">juggernaut</span><span class="special">:</span><span class="identifier">warrior</span> +<span class="special">{</span> + <span class="identifier">juggernaut</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">id</span><span class="special">):</span><span class="identifier">warrior</span><span class="special">{</span><span class="string">"juggernaut"</span><span class="special">,</span><span class="identifier">id</span><span class="special">}{}</span> +<span class="special">};</span> + +<span class="keyword">struct</span> <span class="identifier">goblin</span><span class="special">:</span><span class="identifier">sprite</span> +<span class="special">{</span> + <span class="keyword">using</span> <span class="identifier">sprite</span><span class="special">::</span><span class="identifier">sprite</span><span class="special">;</span> + <span class="keyword">void</span> <span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&</span> <span class="identifier">os</span><span class="special">)</span><span class="keyword">const</span> <span class="identifier">override</span><span class="special">{</span><span class="identifier">os</span><span class="special"><<</span><span class="string">"goblin "</span><span class="special"><<</span><span class="identifier">id</span><span class="special">;};</span> +<span class="special">};</span> +</pre> +<p> + Let us populate a polymorphic collection with an assortment of sprites: + </p> +<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">poly_collection</span><span class="special">/</span><span class="identifier">base_collection</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> +<span class="special">...</span> + +<span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span><span class="special"><</span><span class="identifier">sprite</span><span class="special">></span> <span class="identifier">c</span><span class="special">;</span> + +<span class="identifier">std</span><span class="special">::</span><span class="identifier">mt19937</span> <span class="identifier">gen</span><span class="special">{</span><span class="number">92748</span><span class="special">};</span> <span class="comment">// some arbitrary random seed</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">discrete_distribution</span><span class="special"><></span> <span class="identifier">rnd</span><span class="special">({</span><span class="number">1</span><span class="special">,</span><span class="number">1</span><span class="special">,</span><span class="number">1</span><span class="special">});</span> +<span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">=</span><span class="number">0</span><span class="special">;</span><span class="identifier">i</span><span class="special"><</span><span class="number">8</span><span class="special">;++</span><span class="identifier">i</span><span class="special">){</span> <span class="comment">// assign each type with 1/3 probability</span> + <span class="keyword">switch</span><span class="special">(</span><span class="identifier">rnd</span><span class="special">(</span><span class="identifier">gen</span><span class="special">)){</span> + <span class="keyword">case</span> <span class="number">0</span><span class="special">:</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">warrior</span><span class="special">{</span><span class="identifier">i</span><span class="special">});</span><span class="keyword">break</span><span class="special">;</span> + <span class="keyword">case</span> <span class="number">1</span><span class="special">:</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">juggernaut</span><span class="special">{</span><span class="identifier">i</span><span class="special">});</span><span class="keyword">break</span><span class="special">;</span> + <span class="keyword">case</span> <span class="number">2</span><span class="special">:</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">goblin</span><span class="special">{</span><span class="identifier">i</span><span class="special">});</span><span class="keyword">break</span><span class="special">;</span> + <span class="special">}</span> +<span class="special">}</span> +</pre> +<p> + There are two aspects to notice here: + </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> does not have a + <code class="computeroutput"><span class="identifier">push_back</span></code> member function + like, say, <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span></code>, as the order in which elements + are stored cannot be freely chosen by the user code —we will + see more about this later. The insertion mechanisms are rather those + of containers like <a href="http://en.cppreference.com/w/cpp/container/unordered_multiset" target="_top"><code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">unordered_multiset</span></code></a>, namely + <code class="computeroutput"><span class="identifier">insert</span></code> and <code class="computeroutput"><span class="identifier">emplace</span></code> with or without a position + <span class="emphasis"><em>hint</em></span>. + </li> +<li class="listitem"> + Elements are not created with <code class="computeroutput"><span class="keyword">new</span></code> + but constructed on the stack and passed directly much like one would + do with a standard non-polymorphic container. + </li> +</ul></div> +<div class="important"><table border="0" summary="Important"> +<tr> +<td rowspan="2" align="center" valign="top" width="25"><img alt="[Important]" src="../../../doc/src/images/important.png"></td> +<th align="left">Important</th> +</tr> +<tr><td align="left" valign="top"><p> + Elements inserted into a <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span></code> + (or the other containers of Boost.PolyCollection) must be copyable and + assignable; strictly speaking, they must at least model <a href="http://en.cppreference.com/w/cpp/concept/MoveConstructible" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">MoveConstructible</span></code></strong></span></a> + and either be <a href="http://en.cppreference.com/w/cpp/concept/MoveAssignable" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">MoveAssignable</span></code></strong></span></a> + or not throw on move construction. This might force you to revisit your + code as it is customary to explicitly forbid copying at the base level + of a virtual hierarchy to avoid <a href="https://en.wikipedia.org/wiki/Object_slicing" target="_top"><span class="emphasis"><em>slicing</em></span></a>. + </p></td></tr> +</table></div> +<p> + Rendering can now be implemented with a simple <code class="computeroutput"><span class="keyword">for</span></code> + loop over <code class="computeroutput"><span class="identifier">c</span></code>: + </p> +<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span> +<span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&</span> <span class="identifier">s</span><span class="special">:</span><span class="identifier">c</span><span class="special">){</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">comma</span><span class="special">;</span> + <span class="identifier">s</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span> + <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span> +<span class="special">}</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="string">"\n"</span><span class="special">;</span> +</pre> +<p> + The output being: + </p> +<pre class="programlisting">juggernaut 0,juggernaut 4,juggernaut 7,goblin 1,goblin 3,goblin 5,warrior 2,warrior 6 +</pre> +<p> + As we have forewarned, the traversal order does not correspond to that + of insertion. Instead, the elements are grouped in <span class="emphasis"><em>segments</em></span> + according to their concrete type. Here we see that juggernauts come first, + followed by goblins and warriors. In general, no assumptions should be + made about segment ordering, which may be different for this very example + in your environment. On the other hand, elements inserted into an already + existing segment always come at the end (except if a hint is provided). + For instance, after inserting a latecomer goblin with <code class="computeroutput"><span class="identifier">id</span><span class="special">==</span><span class="number">8</span></code>: + </p> +<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">goblin</span><span class="special">{</span><span class="number">8</span><span class="special">});</span> +</pre> +<p> + the rendering loop outputs (new element in red): + </p> +<pre class="programlisting">juggernaut 0,juggernaut 4,juggernaut 7,goblin 1,goblin 3,goblin 5,<span class="red">goblin 8</span>,warrior 2,warrior 6 +</pre> +<p> + Deletion can be done in the usual way: + </p> +<pre class="programlisting"><span class="comment">// find element with id==7 and remove it</span> +<span class="keyword">auto</span> <span class="identifier">it</span><span class="special">=</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">find_if</span><span class="special">(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),[](</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&</span> <span class="identifier">s</span><span class="special">){</span><span class="keyword">return</span> <span class="identifier">s</span><span class="special">.</span><span class="identifier">id</span><span class="special">==</span><span class="number">7</span><span class="special">;});</span> +<span class="identifier">c</span><span class="special">.</span><span class="identifier">erase</span><span class="special">(</span><span class="identifier">it</span><span class="special">);</span> +</pre> +<p> + Now rendering emits: + </p> +<pre class="programlisting">juggernaut 0,juggernaut 4,goblin 1,goblin 3,goblin 5,goblin 8,warrior 2,warrior 6 +</pre> +</div> +<div class="section"> +<div class="titlepage"><div><div><h4 class="title"> +<a name="poly_collection.tutorial.basics.boost_function_collection"></a><a class="link" href="tutorial.html#poly_collection.tutorial.basics.boost_function_collection" title="boost::function_collection"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span></code></a> +</h4></div></div></div> +<p> + (Code samples from <a href="../../../libs/poly_collection/example/basic_function.cpp" target="_top"><code class="computeroutput"><span class="identifier">basic_function</span><span class="special">.</span><span class="identifier">cpp</span></code></a>. C++14 <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">make_unique</span></code> + is used.) + </p> +<p> + Well into the development of the game, the product manager requests that + two new types of entities be added to the rendering loop: + </p> +<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> +<li class="listitem"> + Overlaid messages, such as scores, modelled as <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span></code>s. + </li> +<li class="listitem"> + Pop-up windows coming from a third party library that, unfortunately, + do not derive from <code class="computeroutput"><span class="identifier">sprite</span></code> + and use their own <code class="computeroutput"><span class="identifier">display</span></code> + member functon for rendering: + </li> +</ul></div> +<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">window</span> +<span class="special">{</span> + <span class="identifier">window</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="identifier">caption</span><span class="special">):</span><span class="identifier">caption</span><span class="special">{</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">move</span><span class="special">(</span><span class="identifier">caption</span><span class="special">)}{}</span> + + <span class="keyword">void</span> <span class="identifier">display</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&</span> <span class="identifier">os</span><span class="special">)</span><span class="keyword">const</span><span class="special">{</span><span class="identifier">os</span><span class="special"><<</span><span class="string">"["</span><span class="special"><<</span><span class="identifier">caption</span><span class="special"><<</span><span class="string">"]"</span><span class="special">;}</span> + + <span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="identifier">caption</span><span class="special">;</span> +<span class="special">};</span> +</pre> +<p> + We then decide to refactor the code so that sprites, messsages and windows + are stored in dedicated containers: + </p> +<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">unique_ptr</span><span class="special"><</span><span class="identifier">sprite</span><span class="special">>></span> <span class="identifier">sprs</span><span class="special">;</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">></span> <span class="identifier">msgs</span><span class="special">;</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">window</span><span class="special">></span> <span class="identifier">wnds</span><span class="special">;</span> +</pre> +<p> + and define our rendering container as a <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span></code> + of <span class="emphasis"><em>callable entities</em></span> —function pointers or + objects with a function call <code class="computeroutput"><span class="keyword">operator</span><span class="special">()</span></code>— accepting a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&</span></code> as a parameter + </p> +<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">poly_collection</span><span class="special">/</span><span class="identifier">function_collection</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> +<span class="special">...</span> + +<span class="comment">// function signature accepting std::ostream& and returning nothing</span> +<span class="keyword">using</span> <span class="identifier">render_callback</span><span class="special">=</span><span class="keyword">void</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&);</span> + +<span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span><span class="special"><</span><span class="identifier">render_callback</span><span class="special">></span> <span class="identifier">c</span><span class="special">;</span> +</pre> +<p> + which we fill with suitable adaptors for <code class="computeroutput"><span class="identifier">sprite</span></code>s, + <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span></code>s and <code class="computeroutput"><span class="identifier">window</span></code>s, + respectively. Lambda functions allow for a particularly terse code. + </p> +<pre class="programlisting"><span class="keyword">auto</span> <span class="identifier">render_sprite</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&</span> <span class="identifier">s</span><span class="special">){</span> + <span class="keyword">return</span> <span class="special">[&](</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&</span> <span class="identifier">os</span><span class="special">){</span><span class="identifier">s</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">os</span><span class="special">);};</span> +<span class="special">};</span> + +<span class="keyword">auto</span> <span class="identifier">render_message</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">&</span> <span class="identifier">m</span><span class="special">){</span> + <span class="keyword">return</span> <span class="special">[&](</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&</span> <span class="identifier">os</span><span class="special">){</span><span class="identifier">os</span><span class="special"><<</span><span class="identifier">m</span><span class="special">;};</span> +<span class="special">};</span> + +<span class="keyword">auto</span> <span class="identifier">render_window</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">window</span><span class="special">&</span> <span class="identifier">w</span><span class="special">){</span> + <span class="keyword">return</span> <span class="special">[&](</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&</span> <span class="identifier">os</span><span class="special">){</span><span class="identifier">w</span><span class="special">.</span><span class="identifier">display</span><span class="special">(</span><span class="identifier">os</span><span class="special">);};</span> +<span class="special">};</span> +<span class="special">...</span> + +<span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&</span> <span class="identifier">ps</span><span class="special">:</span><span class="identifier">sprs</span><span class="special">)</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">render_sprite</span><span class="special">(*</span><span class="identifier">ps</span><span class="special">));</span> +<span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&</span> <span class="identifier">m</span><span class="special">:</span><span class="identifier">msgs</span><span class="special">)</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">render_message</span><span class="special">(</span><span class="identifier">m</span><span class="special">));</span> +<span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&</span> <span class="identifier">w</span><span class="special">:</span><span class="identifier">wnds</span><span class="special">)</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">render_window</span><span class="special">(</span><span class="identifier">w</span><span class="special">));</span> +</pre> +<p> + The rendering loop now looks like this: + </p> +<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span> +<span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&</span> <span class="identifier">cbk</span><span class="special">:</span><span class="identifier">c</span><span class="special">){</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">comma</span><span class="special">;</span> + <span class="identifier">cbk</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span> + <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span> +<span class="special">}</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="string">"\n"</span><span class="special">;</span> +</pre> +<p> + and produces the following for a particular scenario of sprites, messages + and windows: + </p> +<pre class="programlisting">juggernaut 0,goblin 1,warrior 2,goblin 3,"stamina: 10,000","game over",[pop-up 1],[pop-up 2] +</pre> +<p> + The container we have just created works in many respects like a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">function</span><span class="special"><</span><span class="identifier">render_callback</span><span class="special">>></span></code>, + the main difference being that with <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span></code> + callable entities of the same type are packed together in memory <a href="#ftn.poly_collection.tutorial.basics.boost_function_collection.f0" class="footnote" name="poly_collection.tutorial.basics.boost_function_collection.f0"><sup class="footnote">[6]</sup></a>, thus increasing performance (which is the whole point of using + Boost.PolyCollection), while a vector of <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">function</span></code>s + results in an individual allocation for each entity stored <a href="#ftn.poly_collection.tutorial.basics.boost_function_collection.f1" class="footnote" name="poly_collection.tutorial.basics.boost_function_collection.f1"><sup class="footnote">[7]</sup></a>. In fact, the <code class="computeroutput"><span class="identifier">value_type</span></code> + elements held by a <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span></code> + are actually <span class="emphasis"><em>not</em></span> <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">function</span></code>s, + although they behave analogously and can be converted to <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">function</span></code> if needed: + </p> +<pre class="programlisting"><span class="keyword">auto</span> <span class="identifier">cbk</span><span class="special">=*</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">();</span> +<span class="identifier">cbk</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span> <span class="comment">// renders first element to std::cout</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">function</span><span class="special"><</span><span class="identifier">render_callback</span><span class="special">></span> <span class="identifier">f</span><span class="special">=</span><span class="identifier">cbk</span><span class="special">;</span> +<span class="identifier">f</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span> <span class="comment">// exactly the same</span> +</pre> +<p> + There is a reason for this: elements of a polymorphic collection cannot + be freely assigned to by the user as this could end up trying to insert + an object into a segment of a different type. So, unlike with <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">function</span></code>, this will not work: + </p> +<pre class="programlisting"><span class="special">*</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()=</span><span class="identifier">render_message</span><span class="special">(</span><span class="string">"last minute message"</span><span class="special">);</span> <span class="comment">// compile-time error</span> +</pre> +</div> +<div class="section"> +<div class="titlepage"><div><div><h4 class="title"> +<a name="poly_collection.tutorial.basics.boost_any_collection"></a><a class="link" href="tutorial.html#poly_collection.tutorial.basics.boost_any_collection" title="boost::any_collection"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span></code></a> +</h4></div></div></div> +<p> + (Code samples from <a href="../../../libs/poly_collection/example/basic_any.cpp" target="_top"><code class="computeroutput"><span class="identifier">basic_any</span><span class="special">.</span><span class="identifier">cpp</span></code></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> + Here we just touch on the bare essentials of <a href="../../../libs/type_erasure" target="_top">Boost.TypeErasure</a> + needed to present <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span></code>. + The reader is advised to read Boost.TypeErasure documentation for further + information. + </p></td></tr> +</table></div> +<p> + After measuring the performance of the latest changes, we find that rendering + is too slow and decide to refactor once again: if we could store all the + entities --sprites, messages and windows-- into one single container, that + would eliminate a level of indirection. The problem is that these types + are totally unrelated to each other. + </p> +<p> + <a href="../../../libs/type_erasure" target="_top">Boost.TypeErasure</a> provides + a class template <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">any</span><span class="special"><</span><span class="identifier">Concept</span><span class="special">></span></code> able to hold an object of whatever + type as long as it conforms to the interface specified by <code class="computeroutput"><span class="identifier">Concept</span></code>. In our case, we find it particularly + easy to implement a common interface for rendering by providing overloads + of <code class="computeroutput"><span class="keyword">operator</span><span class="special"><<</span></code> + </p> +<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&</span> <span class="keyword">operator</span><span class="special"><<(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&</span> <span class="identifier">os</span><span class="special">,</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&</span> <span class="identifier">s</span><span class="special">)</span> +<span class="special">{</span> + <span class="identifier">s</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">os</span><span class="special">);</span> + <span class="keyword">return</span> <span class="identifier">os</span><span class="special">;</span> +<span class="special">}</span> + +<span class="comment">// std::string already has a suitable operator<<</span> + +<span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&</span> <span class="keyword">operator</span><span class="special"><<(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&</span> <span class="identifier">os</span><span class="special">,</span><span class="keyword">const</span> <span class="identifier">window</span><span class="special">&</span> <span class="identifier">w</span><span class="special">)</span> +<span class="special">{</span> + <span class="identifier">w</span><span class="special">.</span><span class="identifier">display</span><span class="special">(</span><span class="identifier">os</span><span class="special">);</span> + <span class="keyword">return</span> <span class="identifier">os</span><span class="special">;</span> +<span class="special">}</span> +</pre> +<p> + so that we can use it to specify the interface all entities have to adhere + to: + </p> +<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">poly_collection</span><span class="special">/</span><span class="identifier">any_collection</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> +<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">type_erasure</span><span class="special">/</span><span class="identifier">operators</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> +<span class="special">...</span> + +<span class="keyword">using</span> <span class="identifier">renderable</span><span class="special">=</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">ostreamable</span><span class="special"><>;</span> +<span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span><span class="special"><</span><span class="identifier">renderable</span><span class="special">></span> <span class="identifier">c</span><span class="special">;</span> +</pre> +<p> + The collection just created happily accepts insertion of heterogeneous + entities (since interface conformity is silently checked at compile time) + </p> +<pre class="programlisting"><span class="comment">// populate with sprites</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">mt19937</span> <span class="identifier">gen</span><span class="special">{</span><span class="number">92748</span><span class="special">};</span> <span class="comment">// some arbitrary random seed</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">discrete_distribution</span><span class="special"><></span> <span class="identifier">rnd</span><span class="special">({</span><span class="number">1</span><span class="special">,</span><span class="number">1</span><span class="special">,</span><span class="number">1</span><span class="special">});</span> +<span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">=</span><span class="number">0</span><span class="special">;</span><span class="identifier">i</span><span class="special"><</span><span class="number">4</span><span class="special">;++</span><span class="identifier">i</span><span class="special">){</span> <span class="comment">// assign each type with 1/3 probability</span> + <span class="keyword">switch</span><span class="special">(</span><span class="identifier">rnd</span><span class="special">(</span><span class="identifier">gen</span><span class="special">)){</span> + <span class="keyword">case</span> <span class="number">0</span><span class="special">:</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">warrior</span><span class="special">{</span><span class="identifier">i</span><span class="special">});</span><span class="keyword">break</span><span class="special">;</span> + <span class="keyword">case</span> <span class="number">1</span><span class="special">:</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">juggernaut</span><span class="special">{</span><span class="identifier">i</span><span class="special">});</span><span class="keyword">break</span><span class="special">;</span> + <span class="keyword">case</span> <span class="number">2</span><span class="special">:</span> <span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">goblin</span><span class="special">{</span><span class="identifier">i</span><span class="special">});</span><span class="keyword">break</span><span class="special">;</span> + <span class="special">}</span> +<span class="special">}</span> + +<span class="comment">// populate with messages</span> +<span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">{</span><span class="string">"\"stamina: 10,000\""</span><span class="special">});</span> +<span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">{</span><span class="string">"\"game over\""</span><span class="special">});</span> + +<span class="comment">// populate with windows</span> +<span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">window</span><span class="special">{</span><span class="string">"pop-up 1"</span><span class="special">});</span> +<span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">window</span><span class="special">{</span><span class="string">"pop-up 2"</span><span class="special">});</span> +</pre> +<p> + and rendering becomes + </p> +<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span> +<span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&</span> <span class="identifier">r</span><span class="special">:</span><span class="identifier">c</span><span class="special">){</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">comma</span><span class="special"><<</span><span class="identifier">r</span><span class="special">;</span> + <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span> +<span class="special">}</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="string">"\n"</span><span class="special">;</span> +</pre> +<p> + with output + </p> +<pre class="programlisting">[pop-up 1],[pop-up 2],juggernaut 0,goblin 1,goblin 3,warrior 2,"stamina: 10,000","game over" +</pre> +<p> + As was the case with <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span></code>, + this container is similar to a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">any</span><span class="special"><</span><span class="identifier">Concept</span><span class="special">>></span></code> but has better performance due + to packing of same-type elements. Also, the <code class="computeroutput"><span class="identifier">value_type</span></code> + of a <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span><span class="special"><</span><span class="identifier">Concept</span><span class="special">></span></code> + is <span class="emphasis"><em>not</em></span> <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">any</span><span class="special"><</span><span class="identifier">Concept</span><span class="special">></span></code>, but a similarly behaving entity <a href="#ftn.poly_collection.tutorial.basics.boost_any_collection.f0" class="footnote" name="poly_collection.tutorial.basics.boost_any_collection.f0"><sup class="footnote">[8]</sup></a>. In any case, we are not accessing sprites through an abstract + <code class="computeroutput"><span class="identifier">sprite</span><span class="special">&</span></code> + anymore, so we could as well dismantle the virtual hierarchy and implement + each type autonomously: this is left as an exercise to the reader. + </p> +</div> +</div> +<div class="section"> +<div class="titlepage"><div><div><h3 class="title"> +<a name="poly_collection.tutorial.deeper_into_the_segmented_nature"></a><a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature" title="Deeper into the segmented nature of Boost.PolyCollection">Deeper + into the segmented nature of Boost.PolyCollection</a> +</h3></div></div></div> +<div class="toc"><dl class="toc"> +<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration">Type + registration</a></span></dt> +<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.segment_specific_interface">Segment-specific + interface</a></span></dt> +<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.local_iterators">Local + iterators</a></span></dt> +<dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.reserve">Reserve</a></span></dt> +</dl></div> +<p> + (Code samples from <a href="../../../libs/poly_collection/example/segmented_structure.cpp" target="_top"><code class="computeroutput"><span class="identifier">segmented_structure</span><span class="special">.</span><span class="identifier">cpp</span></code></a>. C++14 <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">make_unique</span></code> + is used.) + </p> +<div class="section"> +<div class="titlepage"><div><div><h4 class="title"> +<a name="poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration"></a><a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration" title="Type registration">Type + registration</a> +</h4></div></div></div> +<p> + Getting back to our <a class="link" href="tutorial.html#poly_collection.tutorial.basics.boost_base_collection" title="boost::base_collection"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span></code></a> example, suppose + we want to refactor the populating code as follows: + </p> +<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">unique_ptr</span><span class="special"><</span><span class="identifier">sprite</span><span class="special">></span> <span class="identifier">make_sprite</span><span class="special">()</span> +<span class="special">{</span> + <span class="keyword">static</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">mt19937</span> <span class="identifier">gen</span><span class="special">{</span><span class="number">92748</span><span class="special">};</span> + <span class="keyword">static</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">discrete_distribution</span><span class="special"><></span> <span class="identifier">rnd</span><span class="special">({</span><span class="number">1</span><span class="special">,</span><span class="number">1</span><span class="special">,</span><span class="number">1</span><span class="special">});</span> + <span class="keyword">static</span> <span class="keyword">int</span> <span class="identifier">id</span><span class="special">=</span><span class="number">0</span><span class="special">;</span> + + <span class="keyword">switch</span><span class="special">(</span><span class="identifier">rnd</span><span class="special">(</span><span class="identifier">gen</span><span class="special">)){</span> + <span class="keyword">case</span> <span class="number">0</span><span class="special">:</span> <span class="keyword">return</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">make_unique</span><span class="special"><</span><span class="identifier">warrior</span><span class="special">>(</span><span class="identifier">id</span><span class="special">++);</span><span class="keyword">break</span><span class="special">;</span> + <span class="keyword">case</span> <span class="number">1</span><span class="special">:</span> <span class="keyword">return</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">make_unique</span><span class="special"><</span><span class="identifier">juggernaut</span><span class="special">>(</span><span class="identifier">id</span><span class="special">++);</span><span class="keyword">break</span><span class="special">;</span> + <span class="keyword">case</span> <span class="number">2</span><span class="special">:</span> <span class="keyword">return</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">make_unique</span><span class="special"><</span><span class="identifier">goblin</span><span class="special">>(</span><span class="identifier">id</span><span class="special">++);</span><span class="keyword">break</span><span class="special">;</span> + <span class="special">}</span> +<span class="special">}</span> +<span class="special">...</span> + +<span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">=</span><span class="number">0</span><span class="special">;</span><span class="identifier">i</span><span class="special"><</span><span class="number">8</span><span class="special">;++</span><span class="identifier">i</span><span class="special">)</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(*</span><span class="identifier">make_sprite</span><span class="special">());</span> +<span class="comment">// throws boost::poly_collection::unregistered_type</span> +</pre> +<p> + Unexpectedly, this piece of code throws an exception of type <a class="link" href="reference.html#poly_collection.reference.header_boost_poly_collection_exc.class_unregistered_type" title="Class unregistered_type"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">unregistered_type</span></code></a>. What has changed + from our original code? + </p> +<p> + Suppose a <code class="computeroutput"><span class="identifier">warrior</span></code> has been + created by <code class="computeroutput"><span class="identifier">make_sprite</span></code>. + The statement <code class="computeroutput"><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(*</span><span class="identifier">make_sprite</span><span class="special">())</span></code> + is passing the object as a <code class="computeroutput"><span class="identifier">sprite</span><span class="special">&</span></code>: even though <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span></code> + is smart enough to know that the object is actually derived from <code class="computeroutput"><span class="identifier">sprite</span></code> (by using <a href="http://en.cppreference.com/w/cpp/language/typeid" target="_top"><code class="computeroutput"><span class="keyword">typeid</span><span class="special">()</span></code></a>) + and <a href="https://en.wikipedia.org/wiki/Object_slicing" target="_top">slicing</a> + is to be avoided, there is no way that a segment for it can be created + without accessing the type <code class="computeroutput"><span class="identifier">warrior</span></code> + <span class="emphasis"><em>at compile time</em></span> for the proper internal class templates + to be instantiated <a href="#ftn.poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration.f0" class="footnote" name="poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration.f0"><sup class="footnote">[9]</sup></a>. This did not happen in the pre-refactoring code because objects + were passed as references to their true types. + </p> +<p> + A type is said to be <span class="emphasis"><em>registered</em></span> into a polymorphic + collection if there is a (potentially empty) segment created for it. This + can be checked with: + </p> +<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">is_registered</span><span class="special"><</span><span class="identifier">warrior</span><span class="special">>()<<</span><span class="string">"\n"</span><span class="special">;</span> <span class="comment">// prints 0</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">is_registered</span><span class="special">(</span><span class="keyword">typeid</span><span class="special">(</span><span class="identifier">warrior</span><span class="special">))<<</span><span class="string">"\n"</span><span class="special">;</span> <span class="comment">// alternate syntax</span> +</pre> +<p> + Registration happens automatically when the object is passed as a reference + to its true type or <a class="link" href="tutorial.html#poly_collection.tutorial.insertion_and_emplacement.emplacement"><code class="computeroutput"><span class="identifier">emplace</span></code></a>'d, and explicitly with + <code class="computeroutput"><span class="identifier">register_types</span></code>: + </p> +<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">register_types</span><span class="special"><</span><span class="identifier">warrior</span><span class="special">,</span><span class="identifier">juggernaut</span><span class="special">,</span><span class="identifier">goblin</span><span class="special">>();</span> +<span class="comment">// everything works fine now</span> +<span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">=</span><span class="number">0</span><span class="special">;</span><span class="identifier">i</span><span class="special"><</span><span class="number">8</span><span class="special">;++</span><span class="identifier">i</span><span class="special">)</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(*</span><span class="identifier">make_sprite</span><span class="special">());</span> +</pre> +<p> + Once <code class="computeroutput"><span class="identifier">T</span></code> has been registered + into a polymorphic collection, it remains so regardless of whether objects + of type <code class="computeroutput"><span class="identifier">T</span></code> are stored or + not, except if the collection is moved from, assigned to, or swapped. + </p> +<p> + As slicing is mainly an issue with OOP, <code class="computeroutput"><span class="identifier">unregistered_type</span></code> + exceptions are expected to be much less frequent with <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span></code> + and <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span></code>. Contrived examples can + be found, though: + </p> +<pre class="programlisting"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span><span class="special"><</span><span class="identifier">renderable</span><span class="special">></span> <span class="identifier">c1</span><span class="special">,</span><span class="identifier">c2</span><span class="special">;</span> +<span class="special">...</span> <span class="comment">// populate c2</span> + +<span class="identifier">c1</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(*</span><span class="identifier">c2</span><span class="special">.</span><span class="identifier">begin</span><span class="special">());</span> <span class="comment">// throws: actual type of *c2.begin() not known by c1</span> +</pre> +</div> +<div class="section"> +<div class="titlepage"><div><div><h4 class="title"> +<a name="poly_collection.tutorial.deeper_into_the_segmented_nature.segment_specific_interface"></a><a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.segment_specific_interface" title="Segment-specific interface">Segment-specific + interface</a> +</h4></div></div></div> +<p> + For most of the interface of a polymorphic collection, it is possible to + only refer to the elements of a given segment by providing either their + type or <code class="computeroutput"><span class="keyword">typeid</span><span class="special">()</span></code>. + For instance: + </p> +<pre class="programlisting"><span class="special">...</span> <span class="comment">// populate c with 8 assorted entities</span> + +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">size</span><span class="special">()<<</span><span class="string">"\n"</span><span class="special">;</span> <span class="comment">// 8 sprites</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">size</span><span class="special"><</span><span class="identifier">juggernaut</span><span class="special">>()<<</span><span class="string">"\n"</span><span class="special">;</span> <span class="comment">// 2 juggernauts</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">size</span><span class="special">(</span><span class="keyword">typeid</span><span class="special">(</span><span class="identifier">juggernaut</span><span class="special">))<<</span><span class="string">"\n"</span><span class="special">;</span> <span class="comment">// alternate syntax</span> +<span class="identifier">c</span><span class="special">.</span><span class="identifier">clear</span><span class="special"><</span><span class="identifier">juggernaut</span><span class="special">>();</span> <span class="comment">// remove juggenauts only</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">empty</span><span class="special"><</span><span class="identifier">juggernaut</span><span class="special">>()<<</span><span class="string">"\n"</span><span class="special">;</span> <span class="comment">// 1 (no juggernauts left)</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">size</span><span class="special">()<<</span><span class="string">"\n"</span><span class="special">;</span> <span class="comment">// 6 sprites remaining</span> +</pre> +<p> + Note that any of these (except <a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.reserve" title="Reserve"><code class="computeroutput"><span class="identifier">reserve</span></code></a>) will throw <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">unregistered_type</span></code> if the type is not + registered. Segment-specific addressability also includes traversal: + </p> +</div> +<div class="section"> +<div class="titlepage"><div><div><h4 class="title"> +<a name="poly_collection.tutorial.deeper_into_the_segmented_nature.local_iterators"></a><a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.local_iterators" title="Local iterators">Local + iterators</a> +</h4></div></div></div> +<p> + The following runs only over the <code class="computeroutput"><span class="identifier">warrior</span></code>s + of the collection: + </p> +<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span> +<span class="keyword">for</span><span class="special">(</span><span class="keyword">auto</span> <span class="identifier">first</span><span class="special">=</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(</span><span class="keyword">typeid</span><span class="special">(</span><span class="identifier">warrior</span><span class="special">)),</span><span class="identifier">last</span><span class="special">=</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span><span class="special">(</span><span class="keyword">typeid</span><span class="special">(</span><span class="identifier">warrior</span><span class="special">));</span> + <span class="identifier">first</span><span class="special">!=</span><span class="identifier">last</span><span class="special">;++</span><span class="identifier">first</span><span class="special">){</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">comma</span><span class="special">;</span> + <span class="identifier">first</span><span class="special">-></span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span> + <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span> +<span class="special">}</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="string">"\n"</span><span class="special">;</span> +</pre> +<p> + Output: + </p> +<pre class="programlisting">warrior 2,warrior 6 +</pre> +<p> + <code class="computeroutput"><span class="identifier">begin</span><span class="special">|</span><span class="identifier">end</span><span class="special">(</span><span class="keyword">typeid</span><span class="special">(</span><span class="identifier">T</span><span class="special">))</span></code> return + objects of type <code class="computeroutput"><span class="identifier">local_base_iterator</span></code> + associated to the segment for <code class="computeroutput"><span class="identifier">T</span></code>. + These iterators dereference to the same value as regular iterators (in + the case of <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span><span class="special"><</span><span class="identifier">base</span><span class="special">></span></code>, + <code class="computeroutput"><span class="identifier">base</span><span class="special">&</span></code>) + but can only be used to traverse a given segment (for instance, <code class="computeroutput"><span class="identifier">local_base_iterator</span></code>'s from different + segments cannot be compared between them). In exchange, <code class="computeroutput"><span class="identifier">local_base_iterator</span></code> + is a <a href="http://en.cppreference.com/w/cpp/concept/RandomAccessIterator" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">RandomAccessIterator</span></code></strong></span></a>, + whereas whole-collection iterators only model <a href="http://en.cppreference.com/w/cpp/concept/ForwardIterator" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">ForwardIterator</span></code></strong></span></a>. + </p> +<p> + A terser range-based <code class="computeroutput"><span class="keyword">for</span></code> loop + can be used with the convenience <code class="computeroutput"><span class="identifier">segment</span></code> + member function: + </p> +<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span> +<span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&</span> <span class="identifier">x</span><span class="special">:</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">segment</span><span class="special">(</span><span class="keyword">typeid</span><span class="special">(</span><span class="identifier">warrior</span><span class="special">))){</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">comma</span><span class="special">;</span> + <span class="identifier">x</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span> + <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span> +<span class="special">}</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="string">"\n"</span><span class="special">;</span> +</pre> +<p> + Even more powerful than <code class="computeroutput"><span class="identifier">local_base_iterator</span></code> + is <code class="computeroutput"><span class="identifier">local_iterator</span><span class="special"><</span><span class="identifier">T</span><span class="special">></span></code>: + </p> +<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span> +<span class="keyword">for</span><span class="special">(</span><span class="keyword">auto</span> <span class="identifier">first</span><span class="special">=</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special"><</span><span class="identifier">warrior</span><span class="special">>(),</span><span class="identifier">last</span><span class="special">=</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span><span class="special"><</span><span class="identifier">warrior</span><span class="special">>();</span> + <span class="identifier">first</span><span class="special">!=</span><span class="identifier">last</span><span class="special">;++</span><span class="identifier">first</span><span class="special">){</span> + <span class="identifier">first</span><span class="special">-></span><span class="identifier">rank</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="number">0</span><span class="special">,</span><span class="string">"super"</span><span class="special">);</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">comma</span><span class="special">;</span> + <span class="identifier">first</span><span class="special">-></span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span> + <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span> +<span class="special">}</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="string">"\n"</span><span class="special">;</span> + +<span class="comment">// range-based for loop alternative</span> + +<span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span> +<span class="keyword">for</span><span class="special">(</span><span class="keyword">auto</span><span class="special">&</span> <span class="identifier">x</span><span class="special">:</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">segment</span><span class="special"><</span><span class="identifier">warrior</span><span class="special">>()){</span> + <span class="identifier">x</span><span class="special">.</span><span class="identifier">rank</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="number">0</span><span class="special">,</span><span class="string">"super"</span><span class="special">);</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">comma</span><span class="special">;</span> + <span class="identifier">x</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span> + <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span> +<span class="special">}</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="string">"\n"</span><span class="special">;</span> +</pre> +<p> + This changes the <code class="computeroutput"><span class="identifier">rank</span></code> data + member of existing warriors to append it a <code class="computeroutput"><span class="string">"super"</span></code> + prefix: + </p> +<pre class="programlisting">superwarrior 2,superwarrior 6 +</pre> +<p> + The observant reader will have noticed that in order to access <code class="computeroutput"><span class="identifier">rank</span></code>, which is a member of <code class="computeroutput"><span class="identifier">warrior</span></code> rather than its base class <code class="computeroutput"><span class="identifier">sprite</span></code>, <code class="computeroutput"><span class="identifier">first</span></code> + (or <code class="computeroutput"><span class="identifier">x</span></code> in the range <code class="computeroutput"><span class="keyword">for</span></code> loop version) has to refer to a <code class="computeroutput"><span class="identifier">warrior</span><span class="special">&</span></code>, + and this is precisely the difference between <code class="computeroutput"><span class="identifier">local_iterator</span><span class="special"><</span><span class="identifier">warrior</span><span class="special">></span></code> (the type returned by <code class="computeroutput"><span class="identifier">begin</span><span class="special"><</span><span class="identifier">warrior</span><span class="special">>()</span></code>) + and <code class="computeroutput"><span class="identifier">local_base_iterator</span></code>. + <code class="computeroutput"><span class="identifier">local_iterator</span><span class="special"><</span><span class="identifier">warrior</span><span class="special">></span></code> + is also a <a href="http://en.cppreference.com/w/cpp/concept/RandomAccessIterator" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">RandomAccessIterator</span></code></strong></span></a>: + for most respects, [<code class="computeroutput"><span class="identifier">begin</span><span class="special"><</span><span class="identifier">T</span><span class="special">>()</span></code>, <code class="computeroutput"><span class="identifier">end</span><span class="special"><</span><span class="identifier">T</span><span class="special">>()</span></code>) can be regarded as a range over + an array of <code class="computeroutput"><span class="identifier">T</span></code> objects. + <code class="computeroutput"><span class="identifier">local_iterator</span><span class="special"><</span><span class="identifier">T</span><span class="special">></span></code>s + can be explicitly converted to <code class="computeroutput"><span class="identifier">local_base_iterator</span></code>s. + Conversely, if a <code class="computeroutput"><span class="identifier">local_base_iterator</span></code> + is associated to a segment for <code class="computeroutput"><span class="identifier">T</span></code>, + it can then be explictly converted to a <code class="computeroutput"><span class="identifier">local_iterator</span><span class="special"><</span><span class="identifier">T</span><span class="special">></span></code> (otherwise the conversion is undefined + behavior). + </p> +<p> + The figure shows the action scopes of all the iterators associated to a + polymorphic collection (<code class="computeroutput"><span class="identifier">const_</span></code> + versions not included): + </p> +<p> + <span class="inlinemediaobject"><img src="img/poly_collection_iterators.png"></span> + </p> +<p> + We have yet to describe the bottom part of the diagram. Whereas <code class="computeroutput"><span class="identifier">segment</span><span class="special">(</span><span class="keyword">typeid</span><span class="special">(</span><span class="identifier">T</span><span class="special">))</span></code> is + used to range over the <span class="emphasis"><em>elements</em></span> of a particular segment, + <code class="computeroutput"><span class="identifier">segment_traversal</span><span class="special">()</span></code> + returns an object for ranging over <span class="emphasis"><em>segments</em></span>, so that + the whole collection can be processed with a nested segment-element <code class="computeroutput"><span class="keyword">for</span></code> loop like the following: + </p> +<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span> +<span class="keyword">for</span><span class="special">(</span><span class="keyword">auto</span> <span class="identifier">seg</span><span class="special">:</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">segment_traversal</span><span class="special">()){</span> + <span class="keyword">for</span><span class="special">(</span><span class="identifier">sprite</span><span class="special">&</span> <span class="identifier">s</span><span class="special">:</span><span class="identifier">seg</span><span class="special">){</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">comma</span><span class="special">;</span> + <span class="identifier">s</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span> + <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span> + <span class="special">}</span> +<span class="special">}</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="string">"\n"</span><span class="special">;</span> +</pre> +<p> + Segment decomposition of traversal loops forms the basis of <a class="link" href="tutorial.html#poly_collection.tutorial.algorithms" title="Algorithms">improved-performance + algorithms</a>. + </p> +</div> +<div class="section"> +<div class="titlepage"><div><div><h4 class="title"> +<a name="poly_collection.tutorial.deeper_into_the_segmented_nature.reserve"></a><a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.reserve" title="Reserve">Reserve</a> +</h4></div></div></div> +<p> + Much like <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span></code>, segments can be made to reserve + memory in advance to minimize reallocations: + </p> +<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">reserve</span><span class="special"><</span><span class="identifier">goblin</span><span class="special">>(</span><span class="number">100</span><span class="special">);</span> <span class="comment">// no reallocation till we exceed 100 goblins</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">capacity</span><span class="special"><</span><span class="identifier">goblin</span><span class="special">>()<<</span><span class="string">"\n"</span><span class="special">;</span> <span class="comment">// prints 100</span> +</pre> +<p> + If there is no segment for the indicated type (here, <code class="computeroutput"><span class="identifier">goblin</span></code>), + one is automatically created. This is in contrast with the rest of segment-specific + member functions, which throw <a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration" title="Type registration"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">unregistered_type</span></code></a>. + </p> +<p> + <code class="computeroutput"><span class="identifier">reserve</span></code> can deal with all + segments at once. The following + </p> +<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">reserve</span><span class="special">(</span><span class="number">1000</span><span class="special">);</span> <span class="comment">// reserve(1000) for each segment</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">capacity</span><span class="special"><</span><span class="identifier">warrior</span><span class="special">>()<<</span><span class="string">", "</span> + <span class="special"><<</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">capacity</span><span class="special"><</span><span class="identifier">juggernaut</span><span class="special">>()<<</span><span class="string">", "</span> + <span class="special"><<</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">capacity</span><span class="special"><</span><span class="identifier">goblin</span><span class="special">>()<<</span><span class="string">"\n"</span><span class="special">;</span> <span class="comment">// prints 1000, 1000, 1000</span> +</pre> +<p> + instructs every <span class="emphasis"><em>existing</em></span> segment to reserve 1,000 + elements. If a segment is created later (through element insertion or with + <a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration" title="Type registration">type + registration</a>), its capacity will be different. + </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> + Unlike standard containers, collection-level <code class="computeroutput"><span class="identifier">capacity</span><span class="special">()</span></code> and <code class="computeroutput"><span class="identifier">max_size</span><span class="special">()</span></code> are not provided because their usual + semantics cannot be applied to Boost.PolyCollection: for instance, <code class="computeroutput"><span class="identifier">capacity</span><span class="special">()</span></code> + is typically used to check how many elements can be inserted without + reallocation, but in a segmented structure that depends on the exact + types of the elements and whether they are registered or not. + </p></td></tr> +</table></div> +</div> +</div> +<div class="section"> +<div class="titlepage"><div><div><h3 class="title"> +<a name="poly_collection.tutorial.insertion_and_emplacement"></a><a class="link" href="tutorial.html#poly_collection.tutorial.insertion_and_emplacement" title="Insertion and emplacement">Insertion + and emplacement</a> +</h3></div></div></div> +<p> + (Code samples from <a href="../../../libs/poly_collection/example/insertion_emplacement.cpp" target="_top"><code class="computeroutput"><span class="identifier">insertion_emplacement</span><span class="special">.</span><span class="identifier">cpp</span></code></a>.) + </p> +<p> + We already know that <code class="computeroutput"><span class="identifier">insert</span><span class="special">(</span><span class="identifier">x</span><span class="special">)</span></code>, + without further positional information, stores <code class="computeroutput"><span class="identifier">x</span></code> + at the end of its associated segment. When a regular iterator <code class="computeroutput"><span class="identifier">it</span></code> is provided, insertion happens at the + position indicated if both <code class="computeroutput"><span class="identifier">it</span></code> + and <code class="computeroutput"><span class="identifier">x</span></code> belong in the same + segment; otherwise, <code class="computeroutput"><span class="identifier">it</span></code> is + ignored. For instance, if our sprite collection has the following entities: + </p> +<pre class="programlisting">juggernaut 0,juggernaut 4,juggernaut 7,goblin 1,goblin 3,goblin 5,warrior 2,warrior 6 +</pre> +<p> + then this code: + </p> +<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">juggernaut</span><span class="special">{</span><span class="number">8</span><span class="special">});</span> +</pre> +<p> + puts the new <code class="computeroutput"><span class="identifier">juggernaut</span></code> at + the beginning: + </p> +<pre class="programlisting"><span class="red">juggernaut 8</span>,juggernaut 0,juggernaut 4,juggernaut 7,goblin 1,... +</pre> +<p> + whereas the position hint at + </p> +<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">goblin</span><span class="special">{</span><span class="number">9</span><span class="special">});</span> +</pre> +<p> + is ignored and the new <code class="computeroutput"><span class="identifier">goblin</span></code> + gets inserted at the end of its segment: + </p> +<pre class="programlisting">juggernaut 8,...,juggernaut 7,goblin 1,goblin 3,goblin 5,<span class="red">goblin 9</span>,warrior 2,... +</pre> +<p> + <a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.local_iterators" title="Local iterators">Local + iterators</a> can also be used to indicate the insertion position: + </p> +<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special"><</span><span class="identifier">juggernaut</span><span class="special">>()+</span><span class="number">2</span><span class="special">,</span><span class="identifier">juggernaut</span><span class="special">{</span><span class="number">10</span><span class="special">});</span> + <span class="comment">// ^^ remember local iterators are random access</span> +</pre> +<pre class="programlisting">juggernaut 8,juggernaut 0,<span class="red">juggernaut 10</span>,juggernaut 4,juggernaut 7,goblin 1,... +</pre> +<p> + There is a caveat, though: when using a local iterator, the element inserted + <span class="emphasis"><em>must belong to the indicated segment</em></span>: + </p> +<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(</span><span class="keyword">typeid</span><span class="special">(</span><span class="identifier">warrior</span><span class="special">)),</span><span class="identifier">juggernaut</span><span class="special">{</span><span class="number">11</span><span class="special">});</span> <span class="comment">// undefined behavior!!</span> +</pre> +<p> + Member functions are provided for range insertion, with and without a position + hint: + </p> +<pre class="programlisting"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span><span class="special"><</span><span class="identifier">sprite</span><span class="special">></span> <span class="identifier">c2</span><span class="special">;</span> + +<span class="identifier">c2</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span> <span class="comment">// read below</span> + +<span class="comment">// add some more warriors</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">array</span><span class="special"><</span><span class="identifier">warrior</span><span class="special">,</span><span class="number">3</span><span class="special">></span> <span class="identifier">aw</span><span class="special">={{</span><span class="number">11</span><span class="special">,</span><span class="number">12</span><span class="special">,</span><span class="number">13</span><span class="special">}};</span> +<span class="identifier">c2</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">aw</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">aw</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span> + +<span class="comment">// add some goblins at the beginning of their segment</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">array</span><span class="special"><</span><span class="identifier">goblin</span><span class="special">,</span><span class="number">3</span><span class="special">></span> <span class="identifier">ag</span><span class="special">={{</span><span class="number">14</span><span class="special">,</span><span class="number">15</span><span class="special">,</span><span class="number">16</span><span class="special">}};</span> +<span class="identifier">c2</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">c2</span><span class="special">.</span><span class="identifier">begin</span><span class="special"><</span><span class="identifier">goblin</span><span class="special">>(),</span><span class="identifier">ag</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">ag</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span> +</pre> +<p> + As <a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration" title="Type registration">already + explained</a>, care must be taken that types be pre-registered into the + collection if they are not passed as references to their actual type. So, + why did not this line + </p> +<pre class="programlisting"><span class="identifier">c2</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span> +</pre> +<p> + throw <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">unregistered_type</span></code>? As it happens, in the + special case where the inserted range belongs to a polymorphic collection + of the same type, registration is done automatically <a href="#ftn.poly_collection.tutorial.insertion_and_emplacement.f0" class="footnote" name="poly_collection.tutorial.insertion_and_emplacement.f0"><sup class="footnote">[10]</sup></a>. + </p> +<p> + <a name="poly_collection.tutorial.insertion_and_emplacement.emplacement"></a>Emplacement + is slightly different for Boost.PolyCollection than with standard containers. + Consider this attempt at emplacing a <code class="computeroutput"><span class="identifier">goblin</span></code>: + </p> +<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">emplace</span><span class="special">(</span><span class="number">11</span><span class="special">);</span> <span class="comment">// does not compile</span> +</pre> +<p> + If examined carefully, it is only natural that the code above not compile: + Boost.PolyCollection cannot possibly know that it is precisely a <code class="computeroutput"><span class="identifier">goblin</span></code> that we want to emplace and not + some other type constructible from an <code class="computeroutput"><span class="keyword">int</span></code> + (like <code class="computeroutput"><span class="identifier">warrior</span></code>, <code class="computeroutput"><span class="identifier">juggernaut</span></code> or an unrelated class). So, + the type of the emplaced element has to be specified explicitly: + </p> +<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">emplace</span><span class="special"><</span><span class="identifier">goblin</span><span class="special">>(</span><span class="number">11</span><span class="special">);</span> <span class="comment">// now it works</span> +</pre> +<p> + As with <code class="computeroutput"><span class="identifier">insert</span></code>, a position + can be indicated for emplacing: + </p> +<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">emplace_hint</span><span class="special"><</span><span class="identifier">juggernaut</span><span class="special">>(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="number">12</span><span class="special">);</span> <span class="comment">// at the beginning if possible</span> +<span class="identifier">c</span><span class="special">.</span><span class="identifier">emplace_pos</span><span class="special"><</span><span class="identifier">goblin</span><span class="special">>(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special"><</span><span class="identifier">goblin</span><span class="special">>()+</span><span class="number">2</span><span class="special">,</span><span class="number">13</span><span class="special">);</span> <span class="comment">// amidst the goblins</span> +<span class="identifier">c</span><span class="special">.</span><span class="identifier">emplace_pos</span><span class="special"><</span><span class="identifier">warrior</span><span class="special">>(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(</span><span class="keyword">typeid</span><span class="special">(</span><span class="identifier">warrior</span><span class="special">)),</span><span class="number">14</span><span class="special">);</span> <span class="comment">// local_base_iterator</span> +</pre> +<p> + Note the naming here: <code class="computeroutput"><span class="identifier">emplace_hint</span></code> + is used when the position is indicated with a regular iterator, and for local + iterators it is <code class="computeroutput"><span class="identifier">emplace_pos</span></code>. + </p> +</div> +<div class="section"> +<div class="titlepage"><div><div><h3 class="title"> +<a name="poly_collection.tutorial.exceptions"></a><a class="link" href="tutorial.html#poly_collection.tutorial.exceptions" title="Exceptions">Exceptions</a> +</h3></div></div></div> +<p> + (Code samples from <a href="../../../libs/poly_collection/example/exceptions.cpp" target="_top"><code class="computeroutput"><span class="identifier">exceptions</span><span class="special">.</span><span class="identifier">cpp</span></code></a>.) + </p> +<p> + Besides the usual exceptions like <a href="http://en.cppreference.com/w/cpp/memory/new/bad_alloc" target="_top"><code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">bad_alloc</span></code></a> + and those generated by user-provided types, polymorphic collections can throw + the following: + </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">poly_collection</span><span class="special">::</span><span class="identifier">unregistered_type</span></code> + </li> +<li class="listitem"> + <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">not_copy_constructible</span></code> + </li> +<li class="listitem"> + <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">not_equality_comparable</span></code> + </li> +</ul></div> +<p> + The situations in which the first is raised have been <a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration" title="Type registration">already + discussed</a>; let us focus on the other two. + </p> +<p> + We have a new type of sprite in our game defined by the non-copyable class + <code class="computeroutput"><span class="identifier">elf</span></code>: + </p> +<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">elf</span><span class="special">:</span><span class="identifier">sprite</span> +<span class="special">{</span> + <span class="keyword">using</span> <span class="identifier">sprite</span><span class="special">::</span><span class="identifier">sprite</span><span class="special">;</span> + <span class="identifier">elf</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">elf</span><span class="special">&)=</span><span class="keyword">delete</span><span class="special">;</span> <span class="comment">// not copyable</span> + <span class="identifier">elf</span><span class="special">(</span><span class="identifier">elf</span><span class="special">&&)=</span><span class="keyword">default</span><span class="special">;</span> <span class="comment">// but moveable</span> + <span class="keyword">void</span> <span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&</span> <span class="identifier">os</span><span class="special">)</span><span class="keyword">const</span> <span class="identifier">override</span><span class="special">{</span><span class="identifier">os</span><span class="special"><<</span><span class="string">"elf "</span><span class="special"><<</span><span class="identifier">id</span><span class="special">;};</span> +<span class="special">};</span> +</pre> +<p> + and we use it without problems until we write this: + </p> +<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">insert</span><span class="special">(</span><span class="identifier">elf</span><span class="special">{</span><span class="number">0</span><span class="special">});</span> <span class="comment">// no problem</span> +<span class="special">...</span> + +<span class="identifier">c2</span><span class="special">=</span><span class="identifier">c</span><span class="special">;</span> <span class="comment">// throws boost::poly_collection::not_copy_constructible</span> +</pre> +<p> + The first insertion works because the <code class="computeroutput"><span class="identifier">elf</span></code> + object passed is <span class="emphasis"><em>temporary</em></span> and can be <span class="emphasis"><em>moved</em></span> + into the container, but the second statement actually needs to <span class="emphasis"><em>copy</em></span> + the <code class="computeroutput"><span class="identifier">elf</span></code> elements in <code class="computeroutput"><span class="identifier">c</span></code> to <code class="computeroutput"><span class="identifier">c2</span></code>, + hence the exception. + </p> +<p> + The potentially surprising aspect of this behavior is that standard containers + signal this kind of problems by <span class="emphasis"><em>failing at compile time</em></span>. + Here we cannot afford this luxury because the exact types contained in a + polymorphic collection are not known until run time (for instance, if <code class="computeroutput"><span class="identifier">elf</span></code> elements had been erased before copying + <code class="computeroutput"><span class="identifier">c</span></code> to <code class="computeroutput"><span class="identifier">c2</span></code> + everything would have worked): basically, the deferral of errors from compile + time to run time is an intrinsic feature of dynamic polymorphism. + </p> +<p> + In the same vein, equality comparison requires that elements themselves be + equality comparable: + </p> +<pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">clear</span><span class="special"><</span><span class="identifier">elf</span><span class="special">>();</span> <span class="comment">// get rid of non-copyable elfs</span> +<span class="identifier">c2</span><span class="special">=</span><span class="identifier">c</span><span class="special">;</span> <span class="comment">// now it works</span> +<span class="comment">// check that the two are indeed equal</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<(</span><span class="identifier">c</span><span class="special">==</span><span class="identifier">c2</span><span class="special">)<<</span><span class="string">"\n"</span><span class="special">;</span> + <span class="comment">// throws boost::poly_collection::not_equality_comparable</span> +</pre> +<p> + The above is unremarkable once we notice we have not defined <code class="computeroutput"><span class="keyword">operator</span><span class="special">==</span></code> + for any <code class="computeroutput"><span class="identifier">sprite</span></code>. The problem + may go unnoticed for quite some time, however, because determining that two + polymorphic collections are equal (i.e. all their non-empty segments are + equal) can return <code class="computeroutput"><span class="keyword">false</span></code> without + comparing anything at all (for instance, if segment sizes differ), in which + case no exception is thrown. + </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> + Operators for <code class="computeroutput"><span class="special"><</span></code>, <code class="computeroutput"><span class="special"><=</span></code>, <code class="computeroutput"><span class="special">></span></code> + and <code class="computeroutput"><span class="special">>=</span></code> comparison are not + provided because <span class="emphasis"><em>segment</em></span> order is not fixed and may + vary across otherwise identical collections. The situation is similar to + that of standard <a href="http://en.cppreference.com/w/cpp/concept/UnorderedAssociativeContainer" target="_top">unordered + associative containers.</a> + </p></td></tr> +</table></div> +<p> + These three are all the intrinsic exceptions thrown by Boost.PolyCollection. + The implication is that if a type is <a href="http://en.cppreference.com/w/cpp/concept/CopyConstructible" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">CopyConstructible</span></code></strong></span></a>, + <a href="http://en.cppreference.com/w/cpp/concept/MoveAssignable" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">MoveAssignable</span></code></strong></span></a> + (or move construction does not throw) and <a href="http://en.cppreference.com/w/cpp/concept/EqualityComparable" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">EqualityComparable</span></code></strong></span></a>, + then the entire interface of Boost.PolyCollection is unrestrictedly available + for it <a href="#ftn.poly_collection.tutorial.exceptions.f0" class="footnote" name="poly_collection.tutorial.exceptions.f0"><sup class="footnote">[11]</sup></a>. + </p> +</div> +<div class="section"> +<div class="titlepage"><div><div><h3 class="title"> +<a name="poly_collection.tutorial.algorithms"></a><a class="link" href="tutorial.html#poly_collection.tutorial.algorithms" title="Algorithms">Algorithms</a> +</h3></div></div></div> +<div class="toc"><dl class="toc"><dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.algorithms.type_restitution">Type + restitution</a></span></dt></dl></div> +<p> + (Code samples from <a href="../../../libs/poly_collection/example/algorithms.cpp" target="_top"><code class="computeroutput"><span class="identifier">algorithms</span><span class="special">.</span><span class="identifier">cpp</span></code></a>. C++14 generic lambda expressions + are used.) + </p> +<p> + The ultimate purpose of Boost.PolyCollection is to speed up the processing + of large quantities of polymorphic entities, in particular for those operations + that involve linear traversal as implemented with a <code class="computeroutput"><span class="keyword">for</span></code>-loop + or using the quintessential <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> + algorithm. + </p> +<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">for_each</span><span class="special">(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),[&](</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&</span> <span class="identifier">s</span><span class="special">){</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">comma</span><span class="special">;</span> + <span class="identifier">s</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span> + <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span> +<span class="special">});</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="string">"\n"</span><span class="special">;</span> +</pre> +<p> + Replacing the container used in the program from classic alternatives to + Boost.PolyCollection: + </p> +<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> +<li class="listitem"> + <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">base</span><span class="special">*></span></code> + (or similar) → <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span><span class="special"><</span><span class="identifier">base</span><span class="special">></span></code> + </li> +<li class="listitem"> + <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">function</span><span class="special"><</span><span class="identifier">signature</span><span class="special">>></span></code> + → <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span><span class="special"><</span><span class="identifier">signature</span><span class="special">></span></code> + </li> +<li class="listitem"> + <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">any</span><span class="special"><</span><span class="identifier">concept_</span><span class="special">>></span></code> + → <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span><span class="special"><</span><span class="identifier">concept_</span><span class="special">></span></code> + </li> +</ul></div> +<p> + is expected to increase performance due to better caching and branch prediction + behavior. But there is still room for improvement. + </p> +<p> + Consider this transformation of the code above using a double segment-element + loop (based on the <a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.local_iterators" title="Local iterators">local + iterator</a> capabilities of Boost.PolyCollection): + </p> +<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span> +<span class="keyword">for</span><span class="special">(</span><span class="keyword">auto</span> <span class="identifier">seg_info</span><span class="special">:</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">segment_traversal</span><span class="special">()){</span> + <span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&</span> <span class="identifier">s</span><span class="special">:</span><span class="identifier">seg_info</span><span class="special">){</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">comma</span><span class="special">;</span> + <span class="identifier">s</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span> + <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span> + <span class="special">}</span> +<span class="special">};</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="string">"\n"</span><span class="special">;</span> +</pre> +<p> + Although not obvious at first sight, this version of the same basic operation + is actually <span class="emphasis"><em>faster</em></span> than the first one: for a segmented + structure such as used by Boost.PolyCollection, each iteration with the non-local + iterator passed to <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">for_each</span></code> involves: + </p> +<div class="orderedlist"><ol class="orderedlist" type="1"> +<li class="listitem"> + hopping to next position in the segment, + </li> +<li class="listitem"> + checking for <span class="emphasis"><em>end of segment</em></span> (always), + </li> +<li class="listitem"> + if at end (infrequent), selecting the next segment, + </li> +<li class="listitem"> + checking for <span class="emphasis"><em>end of range</em></span> (always), + </li> +</ol></div> +<p> + whereas in the second version, iteration on the inner loop, where most processing + happens, is a simple increment-and-check operation, that is, there is one + less check (which happens at the much shorter outer loop). When the workload + of the algorithm (the actually useful stuff done with the elements themselves) + is relatively light, the overhead of looping can be very significant. + </p> +<p> + To make it easier for the user to take advantage of faster segment-element + looping, Boost.PolyCollection provides its own version of <code class="computeroutput"><span class="identifier">for_each</span></code> + based on that technique: + </p> +<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">poly_collection</span><span class="special">/</span><span class="identifier">algorithm</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> +<span class="special">...</span> + +<span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span> +<span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">for_each</span><span class="special">(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),[&](</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&</span> <span class="identifier">s</span><span class="special">){</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">comma</span><span class="special">;</span> + <span class="identifier">s</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span> + <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span> +<span class="special">});</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="string">"\n"</span><span class="special">;</span> +</pre> +<p> + <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">for_each</span></code> has the same interface and behavior + as <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">for_each</span></code> except for the fact that it only + works for (non-local) iterators of a polymorphic container <a href="#ftn.poly_collection.tutorial.algorithms.f0" class="footnote" name="poly_collection.tutorial.algorithms.f0"><sup class="footnote">[12]</sup></a>. Versions of other standard algorithms are provided as well: + </p> +<pre class="programlisting"><span class="keyword">auto</span> <span class="identifier">n</span><span class="special">=</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">count_if</span><span class="special">(</span> + <span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),[](</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&</span> <span class="identifier">s</span><span class="special">){</span><span class="keyword">return</span> <span class="identifier">s</span><span class="special">.</span><span class="identifier">id</span><span class="special">%</span><span class="number">2</span><span class="special">==</span><span class="number">0</span><span class="special">;});</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">n</span><span class="special"><<</span><span class="string">" sprites with even id\n"</span><span class="special">;</span> +</pre> +<p> + In fact, variants are given of most (though not all) of the algorithms in + <a href="http://en.cppreference.com/w/cpp/algorithm" target="_top"><code class="computeroutput"><span class="special"><</span><span class="identifier">algorithm</span><span class="special">></span></code></a> + among those that are compatible with polymorphic collections <a href="#ftn.poly_collection.tutorial.algorithms.f1" class="footnote" name="poly_collection.tutorial.algorithms.f1"><sup class="footnote">[13]</sup></a>. Check the <a class="link" href="reference.html#poly_collection.reference.header_boost_poly_collection_alg" title='Header "boost/poly_collection/algorithm.hpp" synopsis'>reference</a> + for details. + </p> +<div class="section"> +<div class="titlepage"><div><div><h4 class="title"> +<a name="poly_collection.tutorial.algorithms.type_restitution"></a><a class="link" href="tutorial.html#poly_collection.tutorial.algorithms.type_restitution" title="Type restitution">Type + restitution</a> +</h4></div></div></div> +<p> + By <span class="emphasis"><em>type restitution</em></span> we mean the generic process of + getting a concrete entity from an abstract one by providing missing type + information: + </p> +<pre class="programlisting"><span class="identifier">sprite</span><span class="special">*</span> <span class="identifier">ps</span><span class="special">=</span><span class="keyword">new</span> <span class="identifier">warrior</span><span class="special">{</span><span class="number">5</span><span class="special">};</span> +<span class="comment">// sprite -> warrior</span> +<span class="identifier">warrior</span><span class="special">*</span> <span class="identifier">pw</span><span class="special">=</span><span class="keyword">static_cast</span><span class="special"><</span><span class="identifier">warrior</span><span class="special">*>(</span><span class="identifier">ps</span><span class="special">);</span> + +<span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">any</span><span class="special"><</span><span class="identifier">renderable</span><span class="special">></span> <span class="identifier">r</span><span class="special">=</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">{</span><span class="string">"hello"</span><span class="special">};</span> +<span class="comment">// renderable -> std::string</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">&</span> <span class="identifier">str</span><span class="special">=</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">any_cast</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">&>(</span><span class="identifier">r</span><span class="special">);</span> +</pre> +<p> + Type restitution has the potential to increase performance. Consider for + instance the following: + </p> +<pre class="programlisting"><span class="comment">// render r with std::string restitution</span> +<span class="keyword">if</span><span class="special">(</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">typeid_of</span><span class="special">(</span><span class="identifier">r</span><span class="special">)==</span><span class="keyword">typeid</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">)){</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">&</span> <span class="identifier">str</span><span class="special">=</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">any_cast</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">&>(</span><span class="identifier">r</span><span class="special">);</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">str</span><span class="special"><<</span><span class="string">"\n"</span><span class="special">;</span> +<span class="special">}</span> +<span class="keyword">else</span><span class="special">{</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">r</span><span class="special"><<</span><span class="string">"\n"</span><span class="special">;</span> +<span class="special">}</span> +</pre> +<p> + Behaviorwise this code is equivalent to simply executing <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">r</span><span class="special"><<</span><span class="string">"\n"</span></code>, but when type restitution + succeeds the statement <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">str</span><span class="special"><<</span><span class="string">"\n"</span></code> + is skipping a virtual-like call that would have happened if <code class="computeroutput"><span class="identifier">r</span></code> were used instead. From a general point + of view, supplying the compiler with extra type information allows it to + perform more optimizations than in the abstract case, inlining being the + prime example. + </p> +<p> + All Boost.PolyCollection algorithms accept an optional list of types for + restitution. Let us use the <a class="link" href="tutorial.html#poly_collection.tutorial.basics.boost_any_collection" title="boost::any_collection"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span></code></a> scenario to illustrate + this point: + </p> +<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span> +<span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">for_each</span> + <span class="special"><</span><span class="identifier">warrior</span><span class="special">,</span><span class="identifier">juggernaut</span><span class="special">,</span><span class="identifier">goblin</span><span class="special">>(</span> <span class="comment">// restituted types</span> + <span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),[&](</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&</span> <span class="identifier">x</span><span class="special">){</span> <span class="comment">// loop traverses *all* elements</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">comma</span><span class="special"><<</span><span class="identifier">x</span><span class="special">;</span> + <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span> + <span class="special">});</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="string">"\n"</span><span class="special">;</span> +</pre> +<p> + Output: + </p> +<pre class="programlisting">warrior 2,warrior 6,[pop-up 1],[pop-up 2],juggernaut 0,juggernaut 4, +juggernaut 7,goblin 1,goblin 3,goblin 5,"stamina: 10,000","game over" +</pre> +<p> + This rendering loop differs from the non-restituting one in two aspects: + </p> +<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> +<li class="listitem"> + A list of types is provided as template arguments to the algorithm. + This is an indication that the types <span class="emphasis"><em>may</em></span> be actually + present in the collection, not a promise. Also, the list of types need + not be exhaustive, that is, some unlisted types could be present in + the collection —in the example above, the loop traverses <span class="bold"><strong>all</strong></span> elements (including <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span></code>s + and <code class="computeroutput"><span class="identifier">window</span></code>s), not only + those corresponding to restituted types. In general, the more types + are restituted, the greater the potential improvement in performance. + </li> +<li class="listitem"> + The lambda function passed is a generic one accepting its argument + as <code class="computeroutput"><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&</span></code> <a href="#ftn.poly_collection.tutorial.algorithms.type_restitution.f0" class="footnote" name="poly_collection.tutorial.algorithms.type_restitution.f0"><sup class="footnote">[14]</sup></a>. + </li> +</ul></div> +<p> + Internally, <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">for_each</span></code> checks for each segment if its + type, say <code class="computeroutput"><span class="identifier">T</span></code>, belongs in + the type restitution list: if this is the case, the lambda function is + passed a <code class="computeroutput"><span class="keyword">const</span> <span class="identifier">T</span><span class="special">&</span></code> rather than the generic <code class="computeroutput"><span class="keyword">const</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">&</span></code>. For each restituted type we are saving + indirection calls and possibly getting inlining optimizations, etc. As + we see in the <a class="link" href="performance.html" title="Performance">performance section</a>, + the speedup can be very significant. + </p> +<p> + Type restitution works equally for the rest of collections of Boost.PolyCollection. + When using <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span></code>, though, the case of + improved performance is more tricky: + </p> +<pre class="programlisting"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span> <span class="identifier">comma</span><span class="special">=</span><span class="string">""</span><span class="special">;</span> +<span class="identifier">boost</span><span class="special">::</span><span class="identifier">poly_collection</span><span class="special">::</span><span class="identifier">for_each</span><span class="special"><</span><span class="identifier">warrior</span><span class="special">,</span><span class="identifier">juggernaut</span><span class="special">,</span><span class="identifier">goblin</span><span class="special">>(</span> + <span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),[&](</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&</span> <span class="identifier">s</span><span class="special">){</span> + <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="identifier">comma</span><span class="special">;</span> + <span class="identifier">s</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">);</span> + <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span> + <span class="special">});</span> +<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special"><<</span><span class="string">"\n"</span><span class="special">;</span> +</pre> +<p> + The problem here is that, even though the argument to the lambda function + will be restituted (when appropriate) to <code class="computeroutput"><span class="identifier">warrior</span><span class="special">&</span></code>, <code class="computeroutput"><span class="identifier">juggernaut</span><span class="special">&</span></code> or <code class="computeroutput"><span class="identifier">goblin</span><span class="special">&</span></code>, using it still involves doing a virtual + function call in <code class="computeroutput"><span class="identifier">s</span><span class="special">.</span><span class="identifier">render</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">)</span></code>. + Whether this call is resolved to a non-virtual one depends on the quality + of implementation of the compiler: + </p> +<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> +<li class="listitem"> + If the concrete class is marked as <a href="http://en.cppreference.com/w/cpp/language/final" target="_top"><code class="computeroutput"><span class="identifier">final</span></code></a>, the compiler <span class="emphasis"><em>in + principle</em></span> has enough information to get rid of the virtual + function call. + </li> +<li class="listitem"> + Other than this, <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> + capabilities <span class="emphasis"><em>may</em></span> be able to figure out that the + type restitution scenario is actually casting the element to its true + type, in which case, again, virtual calls are not needed. + </li> +</ul></div> +</div> +</div> +<div class="footnotes"> +<br><hr style="width:100; text-align:left;margin-left: 0"> +<div id="ftn.poly_collection.tutorial.basics.boost_function_collection.f0" class="footnote"><p><a href="#poly_collection.tutorial.basics.boost_function_collection.f0" class="para"><sup class="para">[6] </sup></a> + Note that all <code class="computeroutput"><span class="identifier">sprite</span></code>s + come into one segment: this is why goblins #1 and #3 are not adjacent. + Exercise for the reader: change the code of the example so that sprites + are further segmented according to their concrete type. + </p></div> +<div id="ftn.poly_collection.tutorial.basics.boost_function_collection.f1" class="footnote"><p><a href="#poly_collection.tutorial.basics.boost_function_collection.f1" class="para"><sup class="para">[7] </sup></a> + Except when small buffer optimization applies. + </p></div> +<div id="ftn.poly_collection.tutorial.basics.boost_any_collection.f0" class="footnote"><p><a href="#poly_collection.tutorial.basics.boost_any_collection.f0" class="para"><sup class="para">[8] </sup></a> + Actually, it is <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">any</span><span class="special"><</span><span class="identifier">Concept2</span><span class="special">,</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">type_erasure</span><span class="special">::</span><span class="identifier">_self</span><span class="special">&></span></code> for some internally defined + <code class="computeroutput"><span class="identifier">Concept2</span></code> that extends + <code class="computeroutput"><span class="identifier">Concept</span></code>. + </p></div> +<div id="ftn.poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration.f0" class="footnote"><p><a href="#poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration.f0" class="para"><sup class="para">[9] </sup></a> + If this is conceptually difficult to grasp, consider the potentially + more obvious case where <code class="computeroutput"><span class="identifier">warrior</span></code> + is defined in a dynamic module linked to the main program: the code of + <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span></code>, which has been compiled + before linking, cannot even know the size of this as-of-yet unseen class, + so hardly can it allocate a segment for the received object. + </p></div> +<div id="ftn.poly_collection.tutorial.insertion_and_emplacement.f0" class="footnote"><p><a href="#poly_collection.tutorial.insertion_and_emplacement.f0" class="para"><sup class="para">[10] </sup></a> + That is, Boost.PolyCollection has enough static information to do type + registration without further assistance from the user. + </p></div> +<div id="ftn.poly_collection.tutorial.exceptions.f0" class="footnote"><p><a href="#poly_collection.tutorial.exceptions.f0" class="para"><sup class="para">[11] </sup></a> + Provided, of course, that the type has the <span class="emphasis"><em>right</em></span> to + be in the collection, that is, it is derived from the specified base, or + callable with the specified signature, etc. + </p></div> +<div id="ftn.poly_collection.tutorial.algorithms.f0" class="footnote"><p><a href="#poly_collection.tutorial.algorithms.f0" class="para"><sup class="para">[12] </sup></a> + For any other type of iterator, it is guaranteed not to compile. + </p></div> +<div id="ftn.poly_collection.tutorial.algorithms.f1" class="footnote"><p><a href="#poly_collection.tutorial.algorithms.f1" class="para"><sup class="para">[13] </sup></a> + For example, algorithms requiring bidrectional iterators or a higher category + are not provided because polymorphic collections have forward-only iterators. + </p></div> +<div id="ftn.poly_collection.tutorial.algorithms.type_restitution.f0" class="footnote"><p><a href="#poly_collection.tutorial.algorithms.type_restitution.f0" class="para"><sup class="para">[14] </sup></a> + This requires C++14, but the same effect can be achieved in C++11 + providing an equivalent, if more cumbersome, functor with a templatized + call operator. + </p></div> +</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 © 2016, 2017 Joaquín M López Muñoz<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="an_efficient_polymorphic_data_st.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../poly_collection.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="performance.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> +</div> +</body> +</html> |