doc/html/poly_collection/tutorial.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
   2 <html>
   3 <head>
   4 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   5 <title>Tutorial</title>
   6 <link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css">
   7 <meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
   8 <link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
   9 <link rel="up" href="../poly_collection.html" title="Chapter&#160;28.&#160;Boost.PolyCollection">
  10 <link rel="prev" href="an_efficient_polymorphic_data_st.html" title="An efficient polymorphic data structure">
  11 <link rel="next" href="performance.html" title="Performance">
  12 </head>
  13 <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
  14 <table cellpadding="2" width="100%"><tr>
  15 <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td>
  16 <td align="center"><a href="../../../index.html">Home</a></td>
  17 <td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td>
  18 <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
  19 <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
  20 <td align="center"><a href="../../../more/index.htm">More</a></td>
  21 </tr></table>
  22 <hr>
  23 <div class="spirit-nav">
  24 <a accesskey="p" href="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>
  25 </div>
  26 <div class="section">
  27 <div class="titlepage"><div><div><h2 class="title" style="clear: both">
  28 <a name="poly_collection.tutorial"></a><a class="link" href="tutorial.html" title="Tutorial">Tutorial</a>
  29 </h2></div></div></div>
  30 <div class="toc"><dl class="toc">
  31 <dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.basics">Basics</a></span></dt>
  32 <dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature">Deeper
  33       into the segmented nature of Boost.PolyCollection</a></span></dt>
  34 <dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.insertion_and_emplacement">Insertion
  35       and emplacement</a></span></dt>
  36 <dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.exceptions">Exceptions</a></span></dt>
  37 <dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.algorithms">Algorithms</a></span></dt>
  38 </dl></div>
  39 <div class="section">
  40 <div class="titlepage"><div><div><h3 class="title">
  41 <a name="poly_collection.tutorial.basics"></a><a class="link" href="tutorial.html#poly_collection.tutorial.basics" title="Basics">Basics</a>
  42 </h3></div></div></div>
  43 <div class="toc"><dl class="toc">
  44 <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>
  45 <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>
  46 <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>
  47 </dl></div>
  48 <div class="section">
  49 <div class="titlepage"><div><div><h4 class="title">
  50 <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>
  51 </h4></div></div></div>
  52 <p>
  53           (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>.)
  54         </p>
  55 <p>
  56           Imagine we are developing a role playing game in C++ where sprites are
  57           rendered on screen; for the purposes of illustration we can model rendering
  58           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>:
  59         </p>
  60 <pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">sprite</span>
  61 <span class="special">{</span>
  62   <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>
  63   <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>
  64   <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">&amp;</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>
  65
  66   <span class="keyword">int</span> <span class="identifier">id</span><span class="special">;</span>
  67 <span class="special">};</span>
  68 </pre>
  69 <p>
  70           The game features warriors, juggernauts (a special type of warrior) and
  71           goblins, each represented by its own class derived (directly or indirectly)
  72           from <code class="computeroutput"><span class="identifier">sprite</span></code>:
  73         </p>
  74 <pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">warrior</span><span class="special">:</span><span class="identifier">sprite</span>
  75 <span class="special">{</span>
  76   <span class="keyword">using</span> <span class="identifier">sprite</span><span class="special">::</span><span class="identifier">sprite</span><span class="special">;</span>
  77   <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>
  78
  79   <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">&amp;</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">&lt;&lt;</span><span class="identifier">rank</span><span class="special">&lt;&lt;</span><span class="string">" "</span><span class="special">&lt;&lt;</span><span class="identifier">id</span><span class="special">;}</span>
  80
  81   <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>
  82 <span class="special">};</span>
  83
  84 <span class="keyword">struct</span> <span class="identifier">juggernaut</span><span class="special">:</span><span class="identifier">warrior</span>
  85 <span class="special">{</span>
  86   <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>
  87 <span class="special">};</span>
  88
  89 <span class="keyword">struct</span> <span class="identifier">goblin</span><span class="special">:</span><span class="identifier">sprite</span>
  90 <span class="special">{</span>
  91   <span class="keyword">using</span> <span class="identifier">sprite</span><span class="special">::</span><span class="identifier">sprite</span><span class="special">;</span>
  92   <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">&amp;</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">&lt;&lt;</span><span class="string">"goblin "</span><span class="special">&lt;&lt;</span><span class="identifier">id</span><span class="special">;}</span>
  93 <span class="special">};</span>
  94 </pre>
  95 <p>
  96           Let us populate a polymorphic collection with an assortment of sprites:
  97         </p>
  98 <pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</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">&gt;</span>
  99 <span class="special">...</span>
 100
 101 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span><span class="special">&lt;</span><span class="identifier">sprite</span><span class="special">&gt;</span> <span class="identifier">c</span><span class="special">;</span>
 102
 103 <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>
 104 <span class="identifier">std</span><span class="special">::</span><span class="identifier">discrete_distribution</span><span class="special">&lt;&gt;</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>
 105 <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">&lt;</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>
 106   <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>
 107     <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>
 108     <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>
 109     <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>
 110   <span class="special">}</span>
 111 <span class="special">}</span>
 112 </pre>
 113 <p>
 114           There are two aspects to notice here:
 115         </p>
 116 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
 117 <li class="listitem">
 118               <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span></code> does not have a
 119               <code class="computeroutput"><span class="identifier">push_back</span></code> member function
 120               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
 121               are stored cannot be freely chosen by the user code &#8212;we will
 122               see more about this later. The insertion mechanisms are rather those
 123               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
 124               <code class="computeroutput"><span class="identifier">insert</span></code> and <code class="computeroutput"><span class="identifier">emplace</span></code> with or without a position
 125               <span class="emphasis"><em>hint</em></span>.
 126             </li>
 127 <li class="listitem">
 128               Elements are not created with <code class="computeroutput"><span class="keyword">new</span></code>
 129               but constructed on the stack and passed directly much like one would
 130               do with a standard non-polymorphic container.
 131             </li>
 132 </ul></div>
 133 <div class="important"><table border="0" summary="Important">
 134 <tr>
 135 <td rowspan="2" align="center" valign="top" width="25"><img alt="[Important]" src="../../../doc/src/images/important.png"></td>
 136 <th align="left">Important</th>
 137 </tr>
 138 <tr><td align="left" valign="top"><p>
 139             Elements inserted into a <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span></code>
 140             (or the other containers of Boost.PolyCollection) must be copyable and
 141             assignable; strictly speaking, they must at least model <a href="http://en.cppreference.com/w/cpp/named_req/MoveConstructible" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">MoveConstructible</span></code></strong></span></a>
 142             and either be <a href="http://en.cppreference.com/w/cpp/named_req/MoveAssignable" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">MoveAssignable</span></code></strong></span></a>
 143             or not throw on move construction. This might force you to revisit your
 144             code as it is customary to explicitly forbid copying at the base level
 145             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>.
 146           </p></td></tr>
 147 </table></div>
 148 <p>
 149           Rendering can now be implemented with a simple <code class="computeroutput"><span class="keyword">for</span></code>
 150           loop over <code class="computeroutput"><span class="identifier">c</span></code>:
 151         </p>
 152 <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>
 153 <span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&amp;</span> <span class="identifier">s</span><span class="special">:</span><span class="identifier">c</span><span class="special">){</span>
 154   <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
 155   <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>
 156   <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
 157 <span class="special">}</span>
 158 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
 159 </pre>
 160 <p>
 161           The output being:
 162         </p>
 163 <pre class="programlisting">juggernaut 0,juggernaut 4,juggernaut 7,goblin 1,goblin 3,goblin 5,warrior 2,warrior 6
 164 </pre>
 165 <p>
 166           As we have forewarned, the traversal order does not correspond to that
 167           of insertion. Instead, the elements are grouped in <span class="emphasis"><em>segments</em></span>
 168           according to their concrete type. Here we see that juggernauts come first,
 169           followed by goblins and warriors. In general, no assumptions should be
 170           made about segment ordering, which may be different for this very example
 171           in your environment. On the other hand, elements inserted into an already
 172           existing segment always come at the end (except if a hint is provided).
 173           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>:
 174         </p>
 175 <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>
 176 </pre>
 177 <p>
 178           the rendering loop outputs (new element in red):
 179         </p>
 180 <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
 181 </pre>
 182 <p>
 183           Deletion can be done in the usual way:
 184         </p>
 185 <pre class="programlisting"><span class="comment">// find element with id==7 and remove it</span>
 186 <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">&amp;</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>
 187 <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>
 188 </pre>
 189 <p>
 190           Now rendering emits:
 191         </p>
 192 <pre class="programlisting">juggernaut 0,juggernaut 4,goblin 1,goblin 3,goblin 5,goblin 8,warrior 2,warrior 6
 193 </pre>
 194 </div>
 195 <div class="section">
 196 <div class="titlepage"><div><div><h4 class="title">
 197 <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>
 198 </h4></div></div></div>
 199 <p>
 200           (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>
 201           is used.)
 202         </p>
 203 <p>
 204           Well into the development of the game, the product manager requests that
 205           two new types of entities be added to the rendering loop:
 206         </p>
 207 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
 208 <li class="listitem">
 209               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.
 210             </li>
 211 <li class="listitem">
 212               Pop-up windows coming from a third party library that, unfortunately,
 213               do not derive from <code class="computeroutput"><span class="identifier">sprite</span></code>
 214               and use their own <code class="computeroutput"><span class="identifier">display</span></code>
 215               member functon for rendering:
 216             </li>
 217 </ul></div>
 218 <pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">window</span>
 219 <span class="special">{</span>
 220   <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>
 221
 222   <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">&amp;</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">&lt;&lt;</span><span class="string">"["</span><span class="special">&lt;&lt;</span><span class="identifier">caption</span><span class="special">&lt;&lt;</span><span class="string">"]"</span><span class="special">;}</span>
 223
 224   <span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span> <span class="identifier">caption</span><span class="special">;</span>
 225 <span class="special">};</span>
 226 </pre>
 227 <p>
 228           We then decide to refactor the code so that sprites, messsages and windows
 229           are stored in dedicated containers:
 230         </p>
 231 <pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">unique_ptr</span><span class="special">&lt;</span><span class="identifier">sprite</span><span class="special">&gt;&gt;</span> <span class="identifier">sprs</span><span class="special">;</span>
 232 <span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">&gt;</span>             <span class="identifier">msgs</span><span class="special">;</span>
 233 <span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">window</span><span class="special">&gt;</span>                  <span class="identifier">wnds</span><span class="special">;</span>
 234 </pre>
 235 <p>
 236           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>
 237           of <span class="emphasis"><em>callable entities</em></span> &#8212;function pointers or
 238           objects with a function call <code class="computeroutput"><span class="keyword">operator</span><span class="special">()</span></code>&#8212; accepting a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span></code> as a parameter
 239         </p>
 240 <pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</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">&gt;</span>
 241 <span class="special">...</span>
 242
 243 <span class="comment">// function signature accepting std::ostream&amp; and returning nothing</span>
 244 <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">&amp;);</span>
 245
 246 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span><span class="special">&lt;</span><span class="identifier">render_callback</span><span class="special">&gt;</span> <span class="identifier">c</span><span class="special">;</span>
 247 </pre>
 248 <p>
 249           which we fill with suitable adaptors for <code class="computeroutput"><span class="identifier">sprite</span></code>s,
 250           <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,
 251           respectively. Lambda functions allow for a particularly terse code.
 252         </p>
 253 <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">&amp;</span> <span class="identifier">s</span><span class="special">){</span>
 254   <span class="keyword">return</span> <span class="special">[&amp;](</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</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>
 255 <span class="special">}</span>
 256
 257 <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">&amp;</span> <span class="identifier">m</span><span class="special">){</span>
 258   <span class="keyword">return</span> <span class="special">[&amp;](</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="identifier">os</span><span class="special">){</span><span class="identifier">os</span><span class="special">&lt;&lt;</span><span class="identifier">m</span><span class="special">;};</span>
 259 <span class="special">}</span>
 260
 261 <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">&amp;</span> <span class="identifier">w</span><span class="special">){</span>
 262   <span class="keyword">return</span> <span class="special">[&amp;](</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</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>
 263 <span class="special">}</span>
 264 <span class="special">...</span>
 265
 266 <span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&amp;</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>
 267 <span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&amp;</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>
 268 <span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&amp;</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>
 269 </pre>
 270 <p>
 271           The rendering loop now looks like this:
 272         </p>
 273 <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>
 274 <span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&amp;</span> <span class="identifier">cbk</span><span class="special">:</span><span class="identifier">c</span><span class="special">){</span>
 275   <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
 276   <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>
 277   <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
 278 <span class="special">}</span>
 279 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
 280 </pre>
 281 <p>
 282           and produces the following for a particular scenario of sprites, messages
 283           and windows:
 284         </p>
 285 <pre class="programlisting">juggernaut 0,goblin 1,warrior 2,goblin 3,"stamina: 10,000","game over",[pop-up 1],[pop-up 2]
 286 </pre>
 287 <p>
 288           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">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">function</span><span class="special">&lt;</span><span class="identifier">render_callback</span><span class="special">&gt;&gt;</span></code>,
 289           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>
 290           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">[12]</sup></a>, thus increasing performance (which is the whole point of using
 291           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
 292           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">[13]</sup></a>. In fact, the <code class="computeroutput"><span class="identifier">value_type</span></code>
 293           elements held by a <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span></code>
 294           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,
 295           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:
 296         </p>
 297 <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>
 298 <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>
 299 <span class="identifier">std</span><span class="special">::</span><span class="identifier">function</span><span class="special">&lt;</span><span class="identifier">render_callback</span><span class="special">&gt;</span> <span class="identifier">f</span><span class="special">=</span><span class="identifier">cbk</span><span class="special">;</span>
 300 <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>
 301 </pre>
 302 <p>
 303           There is a reason for this: elements of a polymorphic collection cannot
 304           be freely assigned to by the user as this could end up trying to insert
 305           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:
 306         </p>
 307 <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>
 308 </pre>
 309 </div>
 310 <div class="section">
 311 <div class="titlepage"><div><div><h4 class="title">
 312 <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>
 313 </h4></div></div></div>
 314 <p>
 315           (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>.)
 316         </p>
 317 <div class="note"><table border="0" summary="Note">
 318 <tr>
 319 <td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../doc/src/images/note.png"></td>
 320 <th align="left">Note</th>
 321 </tr>
 322 <tr><td align="left" valign="top"><p>
 323             Here we just touch on the bare essentials of <a href="../../../libs/type_erasure" target="_top">Boost.TypeErasure</a>
 324             needed to present <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span></code>.
 325             The reader is advised to read Boost.TypeErasure documentation for further
 326             information.
 327           </p></td></tr>
 328 </table></div>
 329 <p>
 330           After measuring the performance of the latest changes, we find that rendering
 331           is too slow and decide to refactor once again: if we could store all the
 332           entities --sprites, messages and windows-- into one single container, that
 333           would eliminate a level of indirection. The problem is that these types
 334           are totally unrelated to each other.
 335         </p>
 336 <p>
 337           <a href="../../../libs/type_erasure" target="_top">Boost.TypeErasure</a> provides
 338           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">&lt;</span><span class="identifier">Concept</span><span class="special">&gt;</span></code> able to hold an object of whatever
 339           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
 340           easy to implement a common interface for rendering by providing overloads
 341           of <code class="computeroutput"><span class="keyword">operator</span><span class="special">&lt;&lt;</span></code>
 342         </p>
 343 <pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="keyword">operator</span><span class="special">&lt;&lt;(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="identifier">os</span><span class="special">,</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&amp;</span> <span class="identifier">s</span><span class="special">)</span>
 344 <span class="special">{</span>
 345   <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>
 346   <span class="keyword">return</span> <span class="identifier">os</span><span class="special">;</span>
 347 <span class="special">}</span>
 348
 349 <span class="comment">// std::string already has a suitable operator&lt;&lt;</span>
 350
 351 <span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="keyword">operator</span><span class="special">&lt;&lt;(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream</span><span class="special">&amp;</span> <span class="identifier">os</span><span class="special">,</span><span class="keyword">const</span> <span class="identifier">window</span><span class="special">&amp;</span> <span class="identifier">w</span><span class="special">)</span>
 352 <span class="special">{</span>
 353   <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>
 354   <span class="keyword">return</span> <span class="identifier">os</span><span class="special">;</span>
 355 <span class="special">}</span>
 356 </pre>
 357 <p>
 358           so that we can use it to specify the interface all entities have to adhere
 359           to:
 360         </p>
 361 <pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</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">&gt;</span>
 362 <span class="preprocessor">#include</span> <span class="special">&lt;</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">&gt;</span>
 363 <span class="special">...</span>
 364
 365 <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">&lt;&gt;;</span>
 366 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span><span class="special">&lt;</span><span class="identifier">renderable</span><span class="special">&gt;</span> <span class="identifier">c</span><span class="special">;</span>
 367 </pre>
 368 <p>
 369           The collection just created happily accepts insertion of heterogeneous
 370           entities (since interface conformity is silently checked at compile time)
 371         </p>
 372 <pre class="programlisting"><span class="comment">// populate with sprites</span>
 373 <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>
 374 <span class="identifier">std</span><span class="special">::</span><span class="identifier">discrete_distribution</span><span class="special">&lt;&gt;</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>
 375 <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">&lt;</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>
 376   <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>
 377     <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>
 378     <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>
 379     <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>
 380   <span class="special">}</span>
 381 <span class="special">}</span>
 382
 383 <span class="comment">// populate with messages</span>
 384 <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>
 385 <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>
 386
 387 <span class="comment">// populate with windows</span>
 388 <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>
 389 <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>
 390 </pre>
 391 <p>
 392           and rendering becomes
 393         </p>
 394 <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>
 395 <span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&amp;</span> <span class="identifier">r</span><span class="special">:</span><span class="identifier">c</span><span class="special">){</span>
 396   <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">&lt;&lt;</span><span class="identifier">r</span><span class="special">;</span>
 397   <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
 398 <span class="special">}</span>
 399 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
 400 </pre>
 401 <p>
 402           with output
 403         </p>
 404 <pre class="programlisting">[pop-up 1],[pop-up 2],juggernaut 0,goblin 1,goblin 3,warrior 2,"stamina: 10,000","game over"
 405 </pre>
 406 <p>
 407           As was the case with <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span></code>,
 408           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">&lt;</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">&lt;</span><span class="identifier">Concept</span><span class="special">&gt;&gt;</span></code> but has better performance due
 409           to packing of same-type elements. Also, the <code class="computeroutput"><span class="identifier">value_type</span></code>
 410           of a <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span><span class="special">&lt;</span><span class="identifier">Concept</span><span class="special">&gt;</span></code>
 411           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">&lt;</span><span class="identifier">Concept</span><span class="special">&gt;</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">[14]</sup></a>. In any case, we are not accessing sprites through an abstract
 412           <code class="computeroutput"><span class="identifier">sprite</span><span class="special">&amp;</span></code>
 413           anymore, so we could as well dismantle the virtual hierarchy and implement
 414           each type autonomously: this is left as an exercise to the reader.
 415         </p>
 416 </div>
 417 </div>
 418 <div class="section">
 419 <div class="titlepage"><div><div><h3 class="title">
 420 <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
 421       into the segmented nature of Boost.PolyCollection</a>
 422 </h3></div></div></div>
 423 <div class="toc"><dl class="toc">
 424 <dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration">Type
 425         registration</a></span></dt>
 426 <dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.segment_specific_interface">Segment-specific
 427         interface</a></span></dt>
 428 <dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.local_iterators">Local
 429         iterators</a></span></dt>
 430 <dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.reserve">Reserve</a></span></dt>
 431 </dl></div>
 432 <p>
 433         (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>
 434         is used.)
 435       </p>
 436 <div class="section">
 437 <div class="titlepage"><div><div><h4 class="title">
 438 <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
 439         registration</a>
 440 </h4></div></div></div>
 441 <p>
 442           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
 443           we want to refactor the populating code as follows:
 444         </p>
 445 <pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">unique_ptr</span><span class="special">&lt;</span><span class="identifier">sprite</span><span class="special">&gt;</span> <span class="identifier">make_sprite</span><span class="special">()</span>
 446 <span class="special">{</span>
 447   <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>
 448   <span class="keyword">static</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">discrete_distribution</span><span class="special">&lt;&gt;</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>
 449   <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>
 450
 451   <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>
 452     <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">&lt;</span><span class="identifier">warrior</span><span class="special">&gt;(</span><span class="identifier">id</span><span class="special">++);</span><span class="keyword">break</span><span class="special">;</span>
 453     <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">&lt;</span><span class="identifier">juggernaut</span><span class="special">&gt;(</span><span class="identifier">id</span><span class="special">++);</span><span class="keyword">break</span><span class="special">;</span>
 454     <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">&lt;</span><span class="identifier">goblin</span><span class="special">&gt;(</span><span class="identifier">id</span><span class="special">++);</span><span class="keyword">break</span><span class="special">;</span>
 455   <span class="special">}</span>
 456 <span class="special">}</span>
 457 <span class="special">...</span>
 458
 459 <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">&lt;</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>
 460 <span class="comment">// throws boost::poly_collection::unregistered_type</span>
 461 </pre>
 462 <p>
 463           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
 464           from our original code?
 465         </p>
 466 <p>
 467           Suppose a <code class="computeroutput"><span class="identifier">warrior</span></code> has been
 468           created by <code class="computeroutput"><span class="identifier">make_sprite</span></code>.
 469           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>
 470           is passing the object as a <code class="computeroutput"><span class="identifier">sprite</span><span class="special">&amp;</span></code>: even though <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span></code>
 471           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>)
 472           and <a href="https://en.wikipedia.org/wiki/Object_slicing" target="_top">slicing</a>
 473           is to be avoided, there is no way that a segment for it can be created
 474           without accessing the type <code class="computeroutput"><span class="identifier">warrior</span></code>
 475           <span class="emphasis"><em>at compile time</em></span> for the proper internal class templates
 476           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">[15]</sup></a>. This did not happen in the pre-refactoring code because objects
 477           were passed as references to their true types.
 478         </p>
 479 <p>
 480           A type is said to be <span class="emphasis"><em>registered</em></span> into a polymorphic
 481           collection if there is a (potentially empty) segment created for it. This
 482           can be checked with:
 483         </p>
 484 <pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">is_registered</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">&gt;()&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>       <span class="comment">// prints 0</span>
 485 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</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">))&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span> <span class="comment">// alternate syntax</span>
 486 </pre>
 487 <p>
 488           Registration happens automatically when the object is passed as a reference
 489           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
 490           <code class="computeroutput"><span class="identifier">register_types</span></code>:
 491         </p>
 492 <pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">register_types</span><span class="special">&lt;</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">&gt;();</span>
 493 <span class="comment">// everything works fine now</span>
 494 <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">&lt;</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>
 495 </pre>
 496 <p>
 497           Once <code class="computeroutput"><span class="identifier">T</span></code> has been registered
 498           into a polymorphic collection, it remains so regardless of whether objects
 499           of type <code class="computeroutput"><span class="identifier">T</span></code> are stored or
 500           not, except if the collection is moved from, assigned to, or swapped.
 501         </p>
 502 <p>
 503           As slicing is mainly an issue with OOP, <code class="computeroutput"><span class="identifier">unregistered_type</span></code>
 504           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>
 505           and <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span></code>. Contrived examples can
 506           be found, though:
 507         </p>
 508 <pre class="programlisting"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span><span class="special">&lt;</span><span class="identifier">renderable</span><span class="special">&gt;</span> <span class="identifier">c1</span><span class="special">,</span><span class="identifier">c2</span><span class="special">;</span>
 509 <span class="special">...</span> <span class="comment">// populate c2</span>
 510
 511 <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>
 512 </pre>
 513 </div>
 514 <div class="section">
 515 <div class="titlepage"><div><div><h4 class="title">
 516 <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
 517         interface</a>
 518 </h4></div></div></div>
 519 <p>
 520           For most of the interface of a polymorphic collection, it is possible to
 521           only refer to the elements of a given segment by providing either their
 522           type or <code class="computeroutput"><span class="keyword">typeid</span><span class="special">()</span></code>.
 523           For instance:
 524         </p>
 525 <pre class="programlisting"><span class="special">...</span> <span class="comment">// populate c with 8 assorted entities</span>
 526
 527 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">size</span><span class="special">()&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>                    <span class="comment">// 8 sprites</span>
 528 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">size</span><span class="special">&lt;</span><span class="identifier">juggernaut</span><span class="special">&gt;()&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>        <span class="comment">// 2 juggernauts</span>
 529 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</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">))&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>  <span class="comment">// alternate syntax</span>
 530 <span class="identifier">c</span><span class="special">.</span><span class="identifier">clear</span><span class="special">&lt;</span><span class="identifier">juggernaut</span><span class="special">&gt;();</span>                        <span class="comment">// remove juggenauts only</span>
 531 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">empty</span><span class="special">&lt;</span><span class="identifier">juggernaut</span><span class="special">&gt;()&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>       <span class="comment">// 1 (no juggernauts left)</span>
 532 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">size</span><span class="special">()&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>                    <span class="comment">// 6 sprites remaining</span>
 533 </pre>
 534 <p>
 535           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
 536           registered. Segment-specific addressability also includes traversal:
 537         </p>
 538 </div>
 539 <div class="section">
 540 <div class="titlepage"><div><div><h4 class="title">
 541 <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
 542         iterators</a>
 543 </h4></div></div></div>
 544 <p>
 545           The following runs only over the <code class="computeroutput"><span class="identifier">warrior</span></code>s
 546           of the collection:
 547         </p>
 548 <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>
 549 <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>
 550     <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>
 551   <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
 552   <span class="identifier">first</span><span class="special">-&gt;</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>
 553   <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
 554 <span class="special">}</span>
 555 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
 556 </pre>
 557 <p>
 558           Output:
 559         </p>
 560 <pre class="programlisting">warrior 2,warrior 6
 561 </pre>
 562 <p>
 563           <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
 564           objects of type <code class="computeroutput"><span class="identifier">local_base_iterator</span></code>
 565           associated to the segment for <code class="computeroutput"><span class="identifier">T</span></code>.
 566           These iterators dereference to the same value as regular iterators (in
 567           the case of <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span><span class="special">&lt;</span><span class="identifier">base</span><span class="special">&gt;</span></code>,
 568           <code class="computeroutput"><span class="identifier">base</span><span class="special">&amp;</span></code>)
 569           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
 570           segments cannot be compared between them). In exchange, <code class="computeroutput"><span class="identifier">local_base_iterator</span></code>
 571           is a <a href="http://en.cppreference.com/w/cpp/named_req/RandomAccessIterator" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">RandomAccessIterator</span></code></strong></span></a>,
 572           whereas whole-collection iterators only model <a href="http://en.cppreference.com/w/cpp/named_req/ForwardIterator" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">ForwardIterator</span></code></strong></span></a>.
 573         </p>
 574 <p>
 575           A terser range-based <code class="computeroutput"><span class="keyword">for</span></code> loop
 576           can be used with the convenience <code class="computeroutput"><span class="identifier">segment</span></code>
 577           member function:
 578         </p>
 579 <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>
 580 <span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&amp;</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>
 581   <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
 582   <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>
 583   <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
 584 <span class="special">}</span>
 585 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
 586 </pre>
 587 <p>
 588           Even more powerful than <code class="computeroutput"><span class="identifier">local_base_iterator</span></code>
 589           is <code class="computeroutput"><span class="identifier">local_iterator</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span></code>:
 590         </p>
 591 <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>
 592 <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">&lt;</span><span class="identifier">warrior</span><span class="special">&gt;(),</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">&lt;</span><span class="identifier">warrior</span><span class="special">&gt;();</span>
 593     <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>
 594   <span class="identifier">first</span><span class="special">-&gt;</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>
 595   <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
 596   <span class="identifier">first</span><span class="special">-&gt;</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>
 597   <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
 598 <span class="special">}</span>
 599 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
 600
 601 <span class="comment">// range-based for loop alternative</span>
 602
 603 <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>
 604 <span class="keyword">for</span><span class="special">(</span><span class="keyword">auto</span><span class="special">&amp;</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">&lt;</span><span class="identifier">warrior</span><span class="special">&gt;()){</span>
 605   <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>
 606   <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
 607   <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>
 608   <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
 609 <span class="special">}</span>
 610 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
 611 </pre>
 612 <p>
 613           This appends a <code class="computeroutput"><span class="string">"super"</span></code>
 614           prefix to the <code class="computeroutput"><span class="identifier">rank</span></code> data
 615           member of existing warriors:
 616         </p>
 617 <pre class="programlisting">superwarrior 2,superwarrior 6
 618 </pre>
 619 <p>
 620           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>
 621           (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">&amp;</span></code>,
 622           and this is precisely the difference between <code class="computeroutput"><span class="identifier">local_iterator</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">&gt;</span></code> (the type returned by <code class="computeroutput"><span class="identifier">begin</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">&gt;()</span></code>)
 623           and <code class="computeroutput"><span class="identifier">local_base_iterator</span></code>.
 624           <code class="computeroutput"><span class="identifier">local_iterator</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">&gt;</span></code>
 625           is also a <a href="http://en.cppreference.com/w/cpp/named_req/RandomAccessIterator" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">RandomAccessIterator</span></code></strong></span></a>:
 626           for most respects, [<code class="computeroutput"><span class="identifier">begin</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;()</span></code>, <code class="computeroutput"><span class="identifier">end</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;()</span></code>) can be regarded as a range over
 627           an array of <code class="computeroutput"><span class="identifier">T</span></code> objects.
 628           <code class="computeroutput"><span class="identifier">local_iterator</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span></code>s
 629           can be explicitly converted to <code class="computeroutput"><span class="identifier">local_base_iterator</span></code>s.
 630           Conversely, if a <code class="computeroutput"><span class="identifier">local_base_iterator</span></code>
 631           is associated to a segment for <code class="computeroutput"><span class="identifier">T</span></code>,
 632           it can then be explictly converted to a <code class="computeroutput"><span class="identifier">local_iterator</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;</span></code> (otherwise the conversion is undefined
 633           behavior).
 634         </p>
 635 <p>
 636           The figure shows the action scopes of all the iterators associated to a
 637           polymorphic collection (<code class="computeroutput"><span class="identifier">const_</span></code>
 638           versions not included):
 639         </p>
 640 <p>
 641           <span class="inlinemediaobject"><img src="img/poly_collection_iterators.png"></span>
 642         </p>
 643 <p>
 644           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
 645           used to range over the <span class="emphasis"><em>elements</em></span> of a particular segment,
 646           <code class="computeroutput"><span class="identifier">segment_traversal</span><span class="special">()</span></code>
 647           returns an object for ranging over <span class="emphasis"><em>segments</em></span>, so that
 648           the whole collection can be processed with a nested segment-element <code class="computeroutput"><span class="keyword">for</span></code> loop like the following:
 649         </p>
 650 <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>
 651 <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>
 652   <span class="keyword">for</span><span class="special">(</span><span class="identifier">sprite</span><span class="special">&amp;</span> <span class="identifier">s</span><span class="special">:</span><span class="identifier">seg</span><span class="special">){</span>
 653     <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
 654     <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>
 655     <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
 656   <span class="special">}</span>
 657 <span class="special">}</span>
 658 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
 659 </pre>
 660 <p>
 661           Segment decomposition of traversal loops forms the basis of <a class="link" href="tutorial.html#poly_collection.tutorial.algorithms" title="Algorithms">improved-performance
 662           algorithms</a>.
 663         </p>
 664 </div>
 665 <div class="section">
 666 <div class="titlepage"><div><div><h4 class="title">
 667 <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>
 668 </h4></div></div></div>
 669 <p>
 670           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
 671           memory in advance to minimize reallocations:
 672         </p>
 673 <pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">reserve</span><span class="special">&lt;</span><span class="identifier">goblin</span><span class="special">&gt;(</span><span class="number">100</span><span class="special">);</span> <span class="comment">// no reallocation till we exceed 100 goblins</span>
 674 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">capacity</span><span class="special">&lt;</span><span class="identifier">goblin</span><span class="special">&gt;()&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span> <span class="comment">// prints 100</span>
 675 </pre>
 676 <p>
 677           If there is no segment for the indicated type (here, <code class="computeroutput"><span class="identifier">goblin</span></code>),
 678           one is automatically created. This is in contrast with the rest of segment-specific
 679           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>.
 680         </p>
 681 <p>
 682           <code class="computeroutput"><span class="identifier">reserve</span></code> can deal with all
 683           segments at once. The following
 684         </p>
 685 <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>
 686 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">capacity</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">&gt;()&lt;&lt;</span><span class="string">", "</span>
 687          <span class="special">&lt;&lt;</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">capacity</span><span class="special">&lt;</span><span class="identifier">juggernaut</span><span class="special">&gt;()&lt;&lt;</span><span class="string">", "</span>
 688          <span class="special">&lt;&lt;</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">capacity</span><span class="special">&lt;</span><span class="identifier">goblin</span><span class="special">&gt;()&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span> <span class="comment">// prints 1000, 1000, 1000</span>
 689 </pre>
 690 <p>
 691           instructs every <span class="emphasis"><em>existing</em></span> segment to reserve 1,000
 692           elements. If a segment is created later (through element insertion or with
 693           <a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration" title="Type registration">type
 694           registration</a>), its capacity will be different.
 695         </p>
 696 <div class="note"><table border="0" summary="Note">
 697 <tr>
 698 <td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../doc/src/images/note.png"></td>
 699 <th align="left">Note</th>
 700 </tr>
 701 <tr><td align="left" valign="top"><p>
 702             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
 703             semantics cannot be applied to Boost.PolyCollection: for instance, <code class="computeroutput"><span class="identifier">capacity</span><span class="special">()</span></code>
 704             is typically used to check how many elements can be inserted without
 705             reallocation, but in a segmented structure that depends on the exact
 706             types of the elements and whether they are registered or not.
 707           </p></td></tr>
 708 </table></div>
 709 </div>
 710 </div>
 711 <div class="section">
 712 <div class="titlepage"><div><div><h3 class="title">
 713 <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
 714       and emplacement</a>
 715 </h3></div></div></div>
 716 <p>
 717         (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>.)
 718       </p>
 719 <p>
 720         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>,
 721         without further positional information, stores <code class="computeroutput"><span class="identifier">x</span></code>
 722         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
 723         position indicated if both <code class="computeroutput"><span class="identifier">it</span></code>
 724         and <code class="computeroutput"><span class="identifier">x</span></code> belong in the same
 725         segment; otherwise, <code class="computeroutput"><span class="identifier">it</span></code> is
 726         ignored. For instance, if our sprite collection has the following entities:
 727       </p>
 728 <pre class="programlisting">juggernaut 0,juggernaut 4,juggernaut 7,goblin 1,goblin 3,goblin 5,warrior 2,warrior 6
 729 </pre>
 730 <p>
 731         then this code:
 732       </p>
 733 <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>
 734 </pre>
 735 <p>
 736         puts the new <code class="computeroutput"><span class="identifier">juggernaut</span></code> at
 737         the beginning:
 738       </p>
 739 <pre class="programlisting"><span class="red">juggernaut 8</span>,juggernaut 0,juggernaut 4,juggernaut 7,goblin 1,...
 740 </pre>
 741 <p>
 742         whereas the position hint at
 743       </p>
 744 <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>
 745 </pre>
 746 <p>
 747         is ignored and the new <code class="computeroutput"><span class="identifier">goblin</span></code>
 748         gets inserted at the end of its segment:
 749       </p>
 750 <pre class="programlisting">juggernaut 8,...,juggernaut 7,goblin 1,goblin 3,goblin 5,<span class="red">goblin 9</span>,warrior 2,...
 751 </pre>
 752 <p>
 753         <a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.local_iterators" title="Local iterators">Local
 754         iterators</a> can also be used to indicate the insertion position:
 755       </p>
 756 <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">&lt;</span><span class="identifier">juggernaut</span><span class="special">&gt;()+</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>
 757                            <span class="comment">// ^^ remember local iterators are random access</span>
 758 </pre>
 759 <pre class="programlisting">juggernaut 8,juggernaut 0,<span class="red">juggernaut 10</span>,juggernaut 4,juggernaut 7,goblin 1,...
 760 </pre>
 761 <p>
 762         There is a caveat, though: when using a local iterator, the element inserted
 763         <span class="emphasis"><em>must belong to the indicated segment</em></span>:
 764       </p>
 765 <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>
 766 </pre>
 767 <p>
 768         Member functions are provided for range insertion, with and without a position
 769         hint:
 770       </p>
 771 <pre class="programlisting"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span><span class="special">&lt;</span><span class="identifier">sprite</span><span class="special">&gt;</span> <span class="identifier">c2</span><span class="special">;</span>
 772
 773 <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>
 774
 775 <span class="comment">// add some more warriors</span>
 776 <span class="identifier">std</span><span class="special">::</span><span class="identifier">array</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">,</span><span class="number">3</span><span class="special">&gt;</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>
 777 <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>
 778
 779 <span class="comment">// add some goblins at the beginning of their segment</span>
 780 <span class="identifier">std</span><span class="special">::</span><span class="identifier">array</span><span class="special">&lt;</span><span class="identifier">goblin</span><span class="special">,</span><span class="number">3</span><span class="special">&gt;</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>
 781 <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">&lt;</span><span class="identifier">goblin</span><span class="special">&gt;(),</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>
 782 </pre>
 783 <p>
 784         As <a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.type_registration" title="Type registration">already
 785         explained</a>, care must be taken that types be pre-registered into the
 786         collection if they are not passed as references to their actual type. So,
 787         why did not this line
 788       </p>
 789 <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>
 790 </pre>
 791 <p>
 792         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
 793         special case where the inserted range belongs to a polymorphic collection
 794         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">[16]</sup></a>.
 795       </p>
 796 <p>
 797         <a name="poly_collection.tutorial.insertion_and_emplacement.emplacement"></a>Emplacement
 798         is slightly different for Boost.PolyCollection than with standard containers.
 799         Consider this attempt at emplacing a <code class="computeroutput"><span class="identifier">goblin</span></code>:
 800       </p>
 801 <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>
 802 </pre>
 803 <p>
 804         If examined carefully, it is only natural that the code above not compile:
 805         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
 806         some other type constructible from an <code class="computeroutput"><span class="keyword">int</span></code>
 807         (like <code class="computeroutput"><span class="identifier">warrior</span></code>, <code class="computeroutput"><span class="identifier">juggernaut</span></code> or an unrelated class). So,
 808         the type of the emplaced element has to be specified explicitly:
 809       </p>
 810 <pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">emplace</span><span class="special">&lt;</span><span class="identifier">goblin</span><span class="special">&gt;(</span><span class="number">11</span><span class="special">);</span> <span class="comment">// now it works</span>
 811 </pre>
 812 <p>
 813         As with <code class="computeroutput"><span class="identifier">insert</span></code>, a position
 814         can be indicated for emplacing:
 815       </p>
 816 <pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">emplace_hint</span><span class="special">&lt;</span><span class="identifier">juggernaut</span><span class="special">&gt;(</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>
 817 <span class="identifier">c</span><span class="special">.</span><span class="identifier">emplace_pos</span><span class="special">&lt;</span><span class="identifier">goblin</span><span class="special">&gt;(</span><span class="identifier">c</span><span class="special">.</span><span class="identifier">begin</span><span class="special">&lt;</span><span class="identifier">goblin</span><span class="special">&gt;()+</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>
 818 <span class="identifier">c</span><span class="special">.</span><span class="identifier">emplace_pos</span><span class="special">&lt;</span><span class="identifier">warrior</span><span class="special">&gt;(</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>
 819 </pre>
 820 <p>
 821         Note the naming here: <code class="computeroutput"><span class="identifier">emplace_hint</span></code>
 822         is used when the position is indicated with a regular iterator, and for local
 823         iterators it is <code class="computeroutput"><span class="identifier">emplace_pos</span></code>.
 824       </p>
 825 </div>
 826 <div class="section">
 827 <div class="titlepage"><div><div><h3 class="title">
 828 <a name="poly_collection.tutorial.exceptions"></a><a class="link" href="tutorial.html#poly_collection.tutorial.exceptions" title="Exceptions">Exceptions</a>
 829 </h3></div></div></div>
 830 <p>
 831         (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>.)
 832       </p>
 833 <p>
 834         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>
 835         and those generated by user-provided types, polymorphic collections can throw
 836         the following:
 837       </p>
 838 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
 839 <li class="listitem">
 840             <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>
 841           </li>
 842 <li class="listitem">
 843             <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>
 844           </li>
 845 <li class="listitem">
 846             <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>
 847           </li>
 848 </ul></div>
 849 <p>
 850         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
 851         discussed</a>; let us focus on the other two.
 852       </p>
 853 <p>
 854         We have a new type of sprite in our game defined by the non-copyable class
 855         <code class="computeroutput"><span class="identifier">elf</span></code>:
 856       </p>
 857 <pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">elf</span><span class="special">:</span><span class="identifier">sprite</span>
 858 <span class="special">{</span>
 859   <span class="keyword">using</span> <span class="identifier">sprite</span><span class="special">::</span><span class="identifier">sprite</span><span class="special">;</span>
 860   <span class="identifier">elf</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">elf</span><span class="special">&amp;)=</span><span class="keyword">delete</span><span class="special">;</span> <span class="comment">// not copyable</span>
 861   <span class="identifier">elf</span><span class="special">(</span><span class="identifier">elf</span><span class="special">&amp;&amp;)=</span><span class="keyword">default</span><span class="special">;</span>     <span class="comment">// but moveable</span>
 862   <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">&amp;</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">&lt;&lt;</span><span class="string">"elf "</span><span class="special">&lt;&lt;</span><span class="identifier">id</span><span class="special">;}</span>
 863 <span class="special">};</span>
 864 </pre>
 865 <p>
 866         and we use it without problems until we write this:
 867       </p>
 868 <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>
 869 <span class="special">...</span>
 870
 871 <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>
 872 </pre>
 873 <p>
 874         The first insertion works because the <code class="computeroutput"><span class="identifier">elf</span></code>
 875         object passed is <span class="emphasis"><em>temporary</em></span> and can be <span class="emphasis"><em>moved</em></span>
 876         into the container, but the second statement actually needs to <span class="emphasis"><em>copy</em></span>
 877         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>,
 878         hence the exception.
 879       </p>
 880 <p>
 881         The potentially surprising aspect of this behavior is that standard containers
 882         signal this kind of problems by <span class="emphasis"><em>failing at compile time</em></span>.
 883         Here we cannot afford this luxury because the exact types contained in a
 884         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
 885         <code class="computeroutput"><span class="identifier">c</span></code> to <code class="computeroutput"><span class="identifier">c2</span></code>
 886         everything would have worked): basically, the deferral of errors from compile
 887         time to run time is an intrinsic feature of dynamic polymorphism.
 888       </p>
 889 <p>
 890         In the same vein, equality comparison requires that elements themselves be
 891         equality comparable:
 892       </p>
 893 <pre class="programlisting"><span class="identifier">c</span><span class="special">.</span><span class="identifier">clear</span><span class="special">&lt;</span><span class="identifier">elf</span><span class="special">&gt;();</span> <span class="comment">// get rid of non-copyable elfs</span>
 894 <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>
 895 <span class="comment">// check that the two are indeed equal</span>
 896 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;(</span><span class="identifier">c</span><span class="special">==</span><span class="identifier">c2</span><span class="special">)&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
 897                 <span class="comment">// throws boost::poly_collection::not_equality_comparable</span>
 898 </pre>
 899 <p>
 900         The above is unremarkable once we notice we have not defined <code class="computeroutput"><span class="keyword">operator</span><span class="special">==</span></code>
 901         for any <code class="computeroutput"><span class="identifier">sprite</span></code>. The problem
 902         may go unnoticed for quite some time, however, because determining that two
 903         polymorphic collections are equal (i.e. all their non-empty segments are
 904         equal) can return <code class="computeroutput"><span class="keyword">false</span></code> without
 905         comparing anything at all (for instance, if segment sizes differ), in which
 906         case no exception is thrown.
 907       </p>
 908 <div class="note"><table border="0" summary="Note">
 909 <tr>
 910 <td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../doc/src/images/note.png"></td>
 911 <th align="left">Note</th>
 912 </tr>
 913 <tr><td align="left" valign="top"><p>
 914           Operators for <code class="computeroutput"><span class="special">&lt;</span></code>, <code class="computeroutput"><span class="special">&lt;=</span></code>, <code class="computeroutput"><span class="special">&gt;</span></code>
 915           and <code class="computeroutput"><span class="special">&gt;=</span></code> comparison are not
 916           provided because <span class="emphasis"><em>segment</em></span> order is not fixed and may
 917           vary across otherwise identical collections. The situation is similar to
 918           that of standard <a href="http://en.cppreference.com/w/cpp/named_req/UnorderedAssociativeContainer" target="_top">unordered
 919           associative containers.</a>
 920         </p></td></tr>
 921 </table></div>
 922 <p>
 923         These three are all the intrinsic exceptions thrown by Boost.PolyCollection.
 924         The implication is that if a type is <a href="http://en.cppreference.com/w/cpp/named_req/CopyConstructible" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">CopyConstructible</span></code></strong></span></a>,
 925         <a href="http://en.cppreference.com/w/cpp/named_req/MoveAssignable" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">MoveAssignable</span></code></strong></span></a>
 926         (or move construction does not throw) and <a href="http://en.cppreference.com/w/cpp/named_req/EqualityComparable" target="_top"><span class="bold"><strong><code class="computeroutput"><span class="identifier">EqualityComparable</span></code></strong></span></a>,
 927         then the entire interface of Boost.PolyCollection is unrestrictedly available
 928         for it <a href="#ftn.poly_collection.tutorial.exceptions.f0" class="footnote" name="poly_collection.tutorial.exceptions.f0"><sup class="footnote">[17]</sup></a>.
 929       </p>
 930 </div>
 931 <div class="section">
 932 <div class="titlepage"><div><div><h3 class="title">
 933 <a name="poly_collection.tutorial.algorithms"></a><a class="link" href="tutorial.html#poly_collection.tutorial.algorithms" title="Algorithms">Algorithms</a>
 934 </h3></div></div></div>
 935 <div class="toc"><dl class="toc"><dt><span class="section"><a href="tutorial.html#poly_collection.tutorial.algorithms.type_restitution">Type
 936         restitution</a></span></dt></dl></div>
 937 <p>
 938         (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
 939         are used.)
 940       </p>
 941 <p>
 942         The ultimate purpose of Boost.PolyCollection is to speed up the processing
 943         of large quantities of polymorphic entities, in particular for those operations
 944         that involve linear traversal as implemented with a <code class="computeroutput"><span class="keyword">for</span></code>-loop
 945         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>
 946         algorithm.
 947       </p>
 948 <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>
 949 <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">(),[&amp;](</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&amp;</span> <span class="identifier">s</span><span class="special">){</span>
 950   <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
 951   <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>
 952   <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
 953 <span class="special">});</span>
 954 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
 955 </pre>
 956 <p>
 957         Replacing the container used in the program from classic alternatives to
 958         Boost.PolyCollection:
 959       </p>
 960 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
 961 <li class="listitem">
 962             <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">base</span><span class="special">*&gt;</span></code>
 963             (or similar) &#8594; <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span><span class="special">&lt;</span><span class="identifier">base</span><span class="special">&gt;</span></code>
 964           </li>
 965 <li class="listitem">
 966             <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">function</span><span class="special">&lt;</span><span class="identifier">signature</span><span class="special">&gt;&gt;</span></code>
 967             &#8594; <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">function_collection</span><span class="special">&lt;</span><span class="identifier">signature</span><span class="special">&gt;</span></code>
 968           </li>
 969 <li class="listitem">
 970             <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</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">&lt;</span><span class="identifier">concept_</span><span class="special">&gt;&gt;</span></code>
 971             &#8594; <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">any_collection</span><span class="special">&lt;</span><span class="identifier">concept_</span><span class="special">&gt;</span></code>
 972           </li>
 973 </ul></div>
 974 <p>
 975         is expected to increase performance due to better caching and branch prediction
 976         behavior. But there is still room for improvement.
 977       </p>
 978 <p>
 979         Consider this transformation of the code above using a double segment-element
 980         loop (based on the <a class="link" href="tutorial.html#poly_collection.tutorial.deeper_into_the_segmented_nature.local_iterators" title="Local iterators">local
 981         iterator</a> capabilities of Boost.PolyCollection):
 982       </p>
 983 <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>
 984 <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>
 985   <span class="keyword">for</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&amp;</span> <span class="identifier">s</span><span class="special">:</span><span class="identifier">seg_info</span><span class="special">){</span>
 986     <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
 987     <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>
 988     <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
 989   <span class="special">}</span>
 990 <span class="special">}</span>
 991 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
 992 </pre>
 993 <p>
 994         Although not obvious at first sight, this version of the same basic operation
 995         is actually <span class="emphasis"><em>faster</em></span> than the first one: for a segmented
 996         structure such as used by Boost.PolyCollection, each iteration with the non-local
 997         iterator passed to <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">for_each</span></code> involves:
 998       </p>
 999 <div class="orderedlist"><ol class="orderedlist" type="1">
1000 <li class="listitem">
1001             hopping to next position in the segment,
1002           </li>
1003 <li class="listitem">
1004             checking for <span class="emphasis"><em>end of segment</em></span> (always),
1005           </li>
1006 <li class="listitem">
1007             if at end (infrequent), selecting the next segment,
1008           </li>
1009 <li class="listitem">
1010             checking for <span class="emphasis"><em>end of range</em></span> (always),
1011           </li>
1012 </ol></div>
1013 <p>
1014         whereas in the second version, iteration on the inner loop, where most processing
1015         happens, is a simple increment-and-check operation, that is, there is one
1016         less check (which happens at the much shorter outer loop). When the workload
1017         of the algorithm (the actually useful stuff done with the elements themselves)
1018         is relatively light, the overhead of looping can be very significant.
1019       </p>
1020 <p>
1021         To make it easier for the user to take advantage of faster segment-element
1022         looping, Boost.PolyCollection provides its own version of <code class="computeroutput"><span class="identifier">for_each</span></code>
1023         based on that technique:
1024       </p>
1025 <pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</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">&gt;</span>
1026 <span class="special">...</span>
1027
1028 <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>
1029 <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">(),[&amp;](</span><span class="keyword">const</span> <span class="identifier">sprite</span><span class="special">&amp;</span> <span class="identifier">s</span><span class="special">){</span>
1030   <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
1031   <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>
1032   <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
1033 <span class="special">});</span>
1034 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
1035 </pre>
1036 <p>
1037         <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
1038         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
1039         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">[18]</sup></a>. Versions of other standard algorithms are provided as well:
1040       </p>
1041 <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>
1042   <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">&amp;</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>
1043 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">n</span><span class="special">&lt;&lt;</span><span class="string">" sprites with even id\n"</span><span class="special">;</span>
1044 </pre>
1045 <p>
1046         In fact, variants are given of most (though not all) of the algorithms in
1047         <a href="http://en.cppreference.com/w/cpp/algorithm" target="_top"><code class="computeroutput"><span class="special">&lt;</span><span class="identifier">algorithm</span><span class="special">&gt;</span></code></a>
1048         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">[19]</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>
1049         for details.
1050       </p>
1051 <div class="section">
1052 <div class="titlepage"><div><div><h4 class="title">
1053 <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
1054         restitution</a>
1055 </h4></div></div></div>
1056 <p>
1057           By <span class="emphasis"><em>type restitution</em></span> we mean the generic process of
1058           getting a concrete entity from an abstract one by providing missing type
1059           information:
1060         </p>
1061 <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>
1062 <span class="comment">// sprite -&gt; warrior</span>
1063 <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">&lt;</span><span class="identifier">warrior</span><span class="special">*&gt;(</span><span class="identifier">ps</span><span class="special">);</span>
1064
1065 <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">&lt;</span><span class="identifier">renderable</span><span class="special">&gt;</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>
1066 <span class="comment">// renderable -&gt; std::string</span>
1067 <span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">&amp;</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">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">&amp;&gt;(</span><span class="identifier">r</span><span class="special">);</span>
1068 </pre>
1069 <p>
1070           Type restitution has the potential to increase performance. Consider for
1071           instance the following:
1072         </p>
1073 <pre class="programlisting"><span class="comment">// render r with std::string restitution</span>
1074 <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>
1075   <span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">&amp;</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">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">string</span><span class="special">&amp;&gt;(</span><span class="identifier">r</span><span class="special">);</span>
1076   <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">str</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
1077 <span class="special">}</span>
1078 <span class="keyword">else</span><span class="special">{</span>
1079   <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">r</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
1080 <span class="special">}</span>
1081 </pre>
1082 <p>
1083           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">&lt;&lt;</span><span class="identifier">r</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span></code>, but when type restitution
1084           succeeds the statement <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">str</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span></code>
1085           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
1086           of view, supplying the compiler with extra type information allows it to
1087           perform more optimizations than in the abstract case, inlining being the
1088           prime example.
1089         </p>
1090 <p>
1091           All Boost.PolyCollection algorithms accept an optional list of types for
1092           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
1093           this point:
1094         </p>
1095 <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>
1096 <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>
1097   <span class="special">&lt;</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">&gt;(</span> <span class="comment">// restituted types</span>
1098   <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">(),[&amp;](</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&amp;</span> <span class="identifier">x</span><span class="special">){</span> <span class="comment">// loop traverses *all* elements</span>
1099     <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">&lt;&lt;</span><span class="identifier">x</span><span class="special">;</span>
1100     <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
1101   <span class="special">});</span>
1102 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
1103 </pre>
1104 <p>
1105           Output:
1106         </p>
1107 <pre class="programlisting">warrior 2,warrior 6,[pop-up 1],[pop-up 2],juggernaut 0,juggernaut 4,
1108 juggernaut 7,goblin 1,goblin 3,goblin 5,"stamina: 10,000","game over"
1109 </pre>
1110 <p>
1111           This rendering loop differs from the non-restituting one in two aspects:
1112         </p>
1113 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
1114 <li class="listitem">
1115               A list of types is provided as template arguments to the algorithm.
1116               This is an indication that the types <span class="emphasis"><em>may</em></span> be actually
1117               present in the collection, not a promise. Also, the list of types need
1118               not be exhaustive, that is, some unlisted types could be present in
1119               the collection &#8212;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
1120               and <code class="computeroutput"><span class="identifier">window</span></code>s), not only
1121               those corresponding to restituted types. In general, the more types
1122               are restituted, the greater the potential improvement in performance.
1123             </li>
1124 <li class="listitem">
1125               The lambda function passed is a generic one accepting its argument
1126               as <code class="computeroutput"><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&amp;</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">[20]</sup></a>.
1127             </li>
1128 </ul></div>
1129 <p>
1130           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
1131           type, say <code class="computeroutput"><span class="identifier">T</span></code>, belongs in
1132           the type restitution list: if this is the case, the lambda function is
1133           passed a <code class="computeroutput"><span class="keyword">const</span> <span class="identifier">T</span><span class="special">&amp;</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">&amp;</span></code>. For each restituted type we are saving
1134           indirection calls and possibly getting inlining optimizations, etc. As
1135           we see in the <a class="link" href="performance.html" title="Performance">performance section</a>,
1136           the speedup can be very significant.
1137         </p>
1138 <p>
1139           Type restitution works equally for the rest of collections of Boost.PolyCollection.
1140           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
1141           improved performance is more tricky:
1142         </p>
1143 <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>
1144 <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">&lt;</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">&gt;(</span>
1145   <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">(),[&amp;](</span><span class="keyword">const</span> <span class="keyword">auto</span><span class="special">&amp;</span> <span class="identifier">s</span><span class="special">){</span>
1146     <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="identifier">comma</span><span class="special">;</span>
1147     <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>
1148     <span class="identifier">comma</span><span class="special">=</span><span class="string">","</span><span class="special">;</span>
1149   <span class="special">});</span>
1150 <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">&lt;&lt;</span><span class="string">"\n"</span><span class="special">;</span>
1151 </pre>
1152 <p>
1153           The problem here is that, even though the argument to the lambda function
1154           will be restituted (when appropriate) to <code class="computeroutput"><span class="identifier">warrior</span><span class="special">&amp;</span></code>, <code class="computeroutput"><span class="identifier">juggernaut</span><span class="special">&amp;</span></code> or <code class="computeroutput"><span class="identifier">goblin</span><span class="special">&amp;</span></code>, using it still involves doing a virtual
1155           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>.
1156           Whether this call is resolved to a non-virtual one depends on the quality
1157           of implementation of the compiler:
1158         </p>
1159 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
1160 <li class="listitem">
1161               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
1162               principle</em></span> has enough information to get rid of the virtual
1163               function call.
1164             </li>
1165 <li class="listitem">
1166               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>
1167               capabilities <span class="emphasis"><em>may</em></span> be able to figure out that the
1168               type restitution scenario is actually casting the element to its true
1169               type, in which case, again, virtual calls are not needed.
1170             </li>
1171 </ul></div>
1172 </div>
1173 </div>
1174 <div class="footnotes">
1175 <br><hr style="width:100; text-align:left;margin-left: 0">
1176 <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">[12] </sup></a>
1177             Note that all <code class="computeroutput"><span class="identifier">sprite</span></code>s
1178             come into one segment: this is why goblins #1 and #3 are not adjacent.
1179             Exercise for the reader: change the code of the example so that sprites
1180             are further segmented according to their concrete type.
1181           </p></div>
1182 <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">[13] </sup></a>
1183             Except when small buffer optimization applies.
1184           </p></div>
1185 <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">[14] </sup></a>
1186             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">&lt;</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">&amp;&gt;</span></code> for some internally defined
1187             <code class="computeroutput"><span class="identifier">Concept2</span></code> that extends
1188             <code class="computeroutput"><span class="identifier">Concept</span></code>.
1189           </p></div>
1190 <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">[15] </sup></a>
1191             If this is conceptually difficult to grasp, consider the potentially
1192             more obvious case where <code class="computeroutput"><span class="identifier">warrior</span></code>
1193             is defined in a dynamic module linked to the main program: the code of
1194             <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">base_collection</span></code>, which has been compiled
1195             before linking, cannot even know the size of this as-of-yet unseen class,
1196             so hardly can it allocate a segment for the received object.
1197           </p></div>
1198 <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">[16] </sup></a>
1199           That is, Boost.PolyCollection has enough static information to do type
1200           registration without further assistance from the user.
1201         </p></div>
1202 <div id="ftn.poly_collection.tutorial.exceptions.f0" class="footnote"><p><a href="#poly_collection.tutorial.exceptions.f0" class="para"><sup class="para">[17] </sup></a>
1203           Provided, of course, that the type has the <span class="emphasis"><em>right</em></span> to
1204           be in the collection, that is, it is derived from the specified base, or
1205           callable with the specified signature, etc.
1206         </p></div>
1207 <div id="ftn.poly_collection.tutorial.algorithms.f0" class="footnote"><p><a href="#poly_collection.tutorial.algorithms.f0" class="para"><sup class="para">[18] </sup></a>
1208           For any other type of iterator, it is guaranteed not to compile.
1209         </p></div>
1210 <div id="ftn.poly_collection.tutorial.algorithms.f1" class="footnote"><p><a href="#poly_collection.tutorial.algorithms.f1" class="para"><sup class="para">[19] </sup></a>
1211           For example, algorithms requiring bidirectional iterators or a higher category
1212           are not provided because polymorphic collections have forward-only iterators.
1213         </p></div>
1214 <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">[20] </sup></a>
1215                 This requires C++14, but the same effect can be achieved in C++11
1216                 providing an equivalent, if more cumbersome, functor with a templatized
1217                 call operator.
1218               </p></div>
1219 </div>
1220 </div>
1221 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
1222 <td align="left"></td>
1223 <td align="right"><div class="copyright-footer">Copyright &#169; 2016-2019 Joaqu&#237;n
1224       M L&#243;pez Mu&#241;oz<p>
1225         Distributed under the Boost Software License, Version 1.0. (See accompanying
1226         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>)
1227       </p>
1228 </div></td>
1229 </tr></table>
1230 <hr>
1231 <div class="spirit-nav">
1232 <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>
1233 </div>
1234 </body>
1235 </html>