1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> 2<html> 3<head> 4<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 5<title>Main features</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="../container.html" title="Chapter 9. Boost.Container"> 10<link rel="prev" href="../container.html" title="Chapter 9. Boost.Container"> 11<link rel="next" href="exception_handling.html" title="Boost.Container and C++ exceptions"> 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="../container.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../container.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="exception_handling.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="container.main_features"></a><a class="link" href="main_features.html" title="Main features">Main features</a> 29</h2></div></div></div> 30<div class="toc"><dl class="toc"> 31<dt><span class="section"><a href="main_features.html#container.main_features.move_emplace">Efficient insertion</a></span></dt> 32<dt><span class="section"><a href="main_features.html#container.main_features.containers_of_incomplete_types">Containers 33 of Incomplete Types</a></span></dt> 34<dt><span class="section"><a href="main_features.html#container.main_features.scary_iterators">SCARY iterators</a></span></dt> 35<dt><span class="section"><a href="main_features.html#container.main_features.other_features">Other features</a></span></dt> 36</dl></div> 37<div class="section"> 38<div class="titlepage"><div><div><h3 class="title"> 39<a name="container.main_features.move_emplace"></a><a class="link" href="main_features.html#container.main_features.move_emplace" title="Efficient insertion">Efficient insertion</a> 40</h3></div></div></div> 41<div class="toc"><dl class="toc"> 42<dt><span class="section"><a href="main_features.html#container.main_features.move_emplace.move_containers">Move-aware 43 containers</a></span></dt> 44<dt><span class="section"><a href="main_features.html#container.main_features.move_emplace.emplace">Emplace: 45 Placement insertion</a></span></dt> 46</dl></div> 47<p> 48 Move semantics and placement insertion are two features brought by C++11 49 containers that can have a very positive impact in your C++ applications. 50 Boost.Container implements both techniques both for C++11 and C++03 compilers. 51 </p> 52<div class="section"> 53<div class="titlepage"><div><div><h4 class="title"> 54<a name="container.main_features.move_emplace.move_containers"></a><a class="link" href="main_features.html#container.main_features.move_emplace.move_containers" title="Move-aware containers">Move-aware 55 containers</a> 56</h4></div></div></div> 57<p> 58 All containers offered by <span class="bold"><strong>Boost.Container</strong></span> 59 can store movable-only types and actual requirements for <code class="computeroutput"><span class="identifier">value_type</span></code> depend on each container operations. 60 Following C++11 requirements even for C++03 compilers, many operations 61 now require movable or default constructible types instead of just copy 62 constructible types. 63 </p> 64<p> 65 Containers themselves are also movable, with no-throw guarantee if allocator 66 or predicate (if present) copy operations are no-throw. This allows high 67 performance operations when transferring data between vectors. Let's see 68 an example: 69 </p> 70<p> 71</p> 72<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">container</span><span class="special">/</span><span class="identifier">vector</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 73<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">move</span><span class="special">/</span><span class="identifier">utility_core</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 74<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">cassert</span><span class="special">></span> 75 76<span class="comment">//Non-copyable class</span> 77<span class="keyword">class</span> <span class="identifier">non_copyable</span> 78<span class="special">{</span> 79 <span class="identifier">BOOST_MOVABLE_BUT_NOT_COPYABLE</span><span class="special">(</span><span class="identifier">non_copyable</span><span class="special">)</span> 80 81 <span class="keyword">public</span><span class="special">:</span> 82 <span class="identifier">non_copyable</span><span class="special">(){}</span> 83 <span class="identifier">non_copyable</span><span class="special">(</span><span class="identifier">BOOST_RV_REF</span><span class="special">(</span><span class="identifier">non_copyable</span><span class="special">))</span> <span class="special">{}</span> 84 <span class="identifier">non_copyable</span><span class="special">&</span> <span class="keyword">operator</span><span class="special">=(</span><span class="identifier">BOOST_RV_REF</span><span class="special">(</span><span class="identifier">non_copyable</span><span class="special">))</span> <span class="special">{</span> <span class="keyword">return</span> <span class="special">*</span><span class="keyword">this</span><span class="special">;</span> <span class="special">}</span> 85<span class="special">};</span> 86 87<span class="keyword">int</span> <span class="identifier">main</span> <span class="special">()</span> 88<span class="special">{</span> 89 <span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">container</span><span class="special">;</span> 90 91 <span class="comment">//Store non-copyable objects in a vector</span> 92 <span class="identifier">vector</span><span class="special"><</span><span class="identifier">non_copyable</span><span class="special">></span> <span class="identifier">v</span><span class="special">;</span> 93 <span class="identifier">non_copyable</span> <span class="identifier">nc</span><span class="special">;</span> 94 <span class="identifier">v</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">move</span><span class="special">(</span><span class="identifier">nc</span><span class="special">));</span> 95 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">v</span><span class="special">.</span><span class="identifier">size</span><span class="special">()</span> <span class="special">==</span> <span class="number">1</span><span class="special">);</span> 96 97 <span class="comment">//Reserve no longer needs copy-constructible</span> 98 <span class="identifier">v</span><span class="special">.</span><span class="identifier">reserve</span><span class="special">(</span><span class="number">100</span><span class="special">);</span> 99 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">v</span><span class="special">.</span><span class="identifier">capacity</span><span class="special">()</span> <span class="special">>=</span> <span class="number">100</span><span class="special">);</span> 100 101 <span class="comment">//This resize overload only needs movable and default constructible</span> 102 <span class="identifier">v</span><span class="special">.</span><span class="identifier">resize</span><span class="special">(</span><span class="number">200</span><span class="special">);</span> 103 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">v</span><span class="special">.</span><span class="identifier">size</span><span class="special">()</span> <span class="special">==</span> <span class="number">200</span><span class="special">);</span> 104 105 <span class="comment">//Containers are also movable</span> 106 <span class="identifier">vector</span><span class="special"><</span><span class="identifier">non_copyable</span><span class="special">></span> <span class="identifier">v_other</span><span class="special">(</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">move</span><span class="special">(</span><span class="identifier">v</span><span class="special">));</span> 107 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">v_other</span><span class="special">.</span><span class="identifier">size</span><span class="special">()</span> <span class="special">==</span> <span class="number">200</span><span class="special">);</span> 108 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">v</span><span class="special">.</span><span class="identifier">empty</span><span class="special">());</span> 109 110 <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> 111<span class="special">}</span> 112</pre> 113<p> 114 </p> 115</div> 116<div class="section"> 117<div class="titlepage"><div><div><h4 class="title"> 118<a name="container.main_features.move_emplace.emplace"></a><a class="link" href="main_features.html#container.main_features.move_emplace.emplace" title="Emplace: Placement insertion">Emplace: 119 Placement insertion</a> 120</h4></div></div></div> 121<p> 122 All containers offered by <span class="bold"><strong>Boost.Container</strong></span> 123 implement placement insertion, which means that objects can be built directly 124 into the container from user arguments without creating any temporary object. 125 For compilers without variadic templates support placement insertion is 126 emulated up to a finite (10) number of arguments. 127 </p> 128<p> 129 Expensive to move types are perfect candidates emplace functions and in 130 case of node containers (<code class="computeroutput"><a class="link" href="../boost/container/list.html" title="Class template list">list</a></code>, 131 <code class="computeroutput"><a class="link" href="../boost/container/set.html" title="Class template set">set</a></code>, ...) emplace allows 132 storing non-movable and non-copyable types in containers! Let's see an 133 example: 134 </p> 135<p> 136</p> 137<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">container</span><span class="special">/</span><span class="identifier">list</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 138<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">cassert</span><span class="special">></span> 139 140<span class="comment">//Non-copyable and non-movable class</span> 141<span class="keyword">class</span> <span class="identifier">non_copy_movable</span> 142<span class="special">{</span> 143 <span class="identifier">non_copy_movable</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">non_copy_movable</span> <span class="special">&);</span> 144 <span class="identifier">non_copy_movable</span><span class="special">&</span> <span class="keyword">operator</span><span class="special">=(</span><span class="keyword">const</span> <span class="identifier">non_copy_movable</span> <span class="special">&);</span> 145 146 <span class="keyword">public</span><span class="special">:</span> 147 <span class="identifier">non_copy_movable</span><span class="special">(</span><span class="keyword">int</span> <span class="special">=</span> <span class="number">0</span><span class="special">)</span> <span class="special">{}</span> 148<span class="special">};</span> 149 150<span class="keyword">int</span> <span class="identifier">main</span> <span class="special">()</span> 151<span class="special">{</span> 152 <span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">container</span><span class="special">;</span> 153 154 <span class="comment">//Store non-copyable and non-movable objects in a list</span> 155 <span class="identifier">list</span><span class="special"><</span><span class="identifier">non_copy_movable</span><span class="special">></span> <span class="identifier">l</span><span class="special">;</span> 156 <span class="identifier">non_copy_movable</span> <span class="identifier">ncm</span><span class="special">;</span> 157 158 <span class="comment">//A new element will be built calling non_copy_movable(int) constructor</span> 159 <span class="identifier">l</span><span class="special">.</span><span class="identifier">emplace</span><span class="special">(</span><span class="identifier">l</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="number">0</span><span class="special">);</span> 160 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">l</span><span class="special">.</span><span class="identifier">size</span><span class="special">()</span> <span class="special">==</span> <span class="number">1</span><span class="special">);</span> 161 162 <span class="comment">//A new element will be value initialized</span> 163 <span class="identifier">l</span><span class="special">.</span><span class="identifier">emplace</span><span class="special">(</span><span class="identifier">l</span><span class="special">.</span><span class="identifier">begin</span><span class="special">());</span> 164 <span class="identifier">assert</span><span class="special">(</span><span class="identifier">l</span><span class="special">.</span><span class="identifier">size</span><span class="special">()</span> <span class="special">==</span> <span class="number">2</span><span class="special">);</span> 165 <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> 166<span class="special">}</span> 167</pre> 168<p> 169 </p> 170</div> 171</div> 172<div class="section"> 173<div class="titlepage"><div><div><h3 class="title"> 174<a name="container.main_features.containers_of_incomplete_types"></a><a class="link" href="main_features.html#container.main_features.containers_of_incomplete_types" title="Containers of Incomplete Types">Containers 175 of Incomplete Types</a> 176</h3></div></div></div> 177<div class="toc"><dl class="toc"> 178<dt><span class="section"><a href="main_features.html#container.main_features.containers_of_incomplete_types.recursive_containers">Recursive 179 containers</a></span></dt> 180<dt><span class="section"><a href="main_features.html#container.main_features.containers_of_incomplete_types.type_erasure">Type 181 Erasure</a></span></dt> 182</dl></div> 183<p> 184 Incomplete types allow <a href="http://en.wikipedia.org/wiki/Type_erasure" target="_top"><span class="bold"><strong>type erasure </strong></span></a> and <a href="http://en.wikipedia.org/wiki/Recursive_data_type" target="_top"><span class="bold"><strong>recursive data types</strong></span></a>, and C and C++ programmers 185 have been using it for years to build complex data structures, like tree 186 structures where a node may have an arbitrary number of children. 187 </p> 188<p> 189 What about standard containers? Containers of incomplete types have been 190 under discussion for a long time, as explained in Matt Austern's great article 191 (<a href="http://drdobbs.com/184403814" target="_top"><span class="bold"><strong>The Standard 192 Librarian: Containers of Incomplete Types</strong></span></a>): 193 </p> 194<p> 195 <span class="quote">“<span class="quote"><span class="emphasis"><em>Unlike most of my columns, this one is about something you 196 can't do with the C++ Standard library: put incomplete types in one of the 197 standard containers. This column explains why you might want to do this, 198 why the standardization committee banned it even though they knew it was 199 useful, and what you might be able to do to get around the restriction.</em></span></span>”</span> 200 </p> 201<p> 202 <span class="quote">“<span class="quote"><span class="emphasis"><em>In 1997, shortly before the C++ Standard was completed, 203 the standardization committee received a query: Is it possible to create 204 standard containers with incomplete types? It took a while for the committee 205 to understand the question. What would such a thing even mean, and why on 206 earth would you ever want to do it? The committee eventually worked it out 207 and came up with an answer to the question. (Just so you don't have to skip 208 ahead to the end, the answer is "no.") But the question is much 209 more interesting than the answer: it points to a useful, and insufficiently 210 discussed, programming technique. The standard library doesn't directly support 211 that technique, but the two can be made to coexist.</em></span></span>”</span> 212 </p> 213<p> 214 <span class="quote">“<span class="quote"><span class="emphasis"><em>In a future revision of C++, it might make sense to relax 215 the restriction on instantiating standard library templates with incomplete 216 types. Clearly, the general prohibition should stay in place - instantiating 217 templates with incomplete types is a delicate business, and there are too 218 many classes in the standard library where it would make no sense. But perhaps 219 it should be relaxed on a case-by-case basis, and <code class="computeroutput"><span class="identifier">vector</span></code> 220 looks like a good candidate for such special-case treatment: it's the one 221 standard container class where there are good reasons to instantiate it with 222 an incomplete type and where Standard Library implementors want to make it 223 work. As of today, in fact, implementors would have to go out of their way 224 to prohibit it!</em></span></span>”</span> 225 </p> 226<p> 227 C++11 standard is also cautious about incomplete types and STL: <span class="quote">“<span class="quote"><span class="emphasis"><em>17.6.4.8 228 Other functions (...) 2. the effects are undefined in the following cases: 229 (...) In particular - if an incomplete type (3.9) is used as a template argument 230 when instantiating a template component, unless specifically allowed for 231 that component</em></span></span>”</span>. 232 </p> 233<p> 234 Finally C++17 added support for incomplete types in <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span></code>, 235 <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span></code> and <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">forward_list</span></code> 236 (see <a href="https://wg21.link/n4510" target="_top"><span class="emphasis"><em>N4510: Minimal incomplete 237 type support for standard containers, revision 4</em></span></a> for details), 238 but no other containers like <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">map</span><span class="special">/</span><span class="identifier">unordered_set</span><span class="special">/</span><span class="identifier">unordered_map</span></code>, 239 </p> 240<p> 241 Fortunately all <span class="bold"><strong>Boost.Container</strong></span> containers 242 except <code class="computeroutput"><a class="link" href="../boost/container/static_vector.html" title="Class template static_vector">static_vector</a></code> 243 and <code class="computeroutput"><a class="link" href="../boost/container/small_vector.html" title="Class template small_vector">small_vector</a></code> 244 and <code class="computeroutput"><a class="link" href="../boost/container/basic_string.html" title="Class template basic_string">basic_string</a></code> 245 are designed to support incomplete types. <code class="computeroutput"><a class="link" href="../boost/container/static_vector.html" title="Class template static_vector">static_vector</a></code> 246 and <code class="computeroutput"><a class="link" href="../boost/container/small_vector.html" title="Class template small_vector">small_vector</a></code> 247 are special because they statically allocates memory for <code class="computeroutput"><span class="identifier">value_type</span></code> 248 and this requires complete types. <code class="computeroutput"><a class="link" href="../boost/container/basic_string.html" title="Class template basic_string">basic_string</a></code> 249 implements Small String Optimization which also requires complete types. 250 </p> 251<p> 252 <span class="bold"><strong>Boost.Container</strong></span> containers supporting incomplete 253 types also support instantiating iterators to those incomplete elements. 254 </p> 255<div class="section"> 256<div class="titlepage"><div><div><h4 class="title"> 257<a name="container.main_features.containers_of_incomplete_types.recursive_containers"></a><a class="link" href="main_features.html#container.main_features.containers_of_incomplete_types.recursive_containers" title="Recursive containers">Recursive 258 containers</a> 259</h4></div></div></div> 260<p> 261 Most <span class="bold"><strong>Boost.Container</strong></span> containers can be 262 used to define recursive containers: 263 </p> 264<p> 265</p> 266<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">container</span><span class="special">/</span><span class="identifier">vector</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 267<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">container</span><span class="special">/</span><span class="identifier">stable_vector</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 268<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">container</span><span class="special">/</span><span class="identifier">deque</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 269<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">container</span><span class="special">/</span><span class="identifier">list</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 270<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">container</span><span class="special">/</span><span class="identifier">map</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 271<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">container</span><span class="special">/</span><span class="identifier">string</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 272 273<span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">container</span><span class="special">;</span> 274 275<span class="keyword">struct</span> <span class="identifier">data</span> 276<span class="special">{</span> 277 <span class="keyword">int</span> <span class="identifier">i_</span><span class="special">;</span> 278 <span class="comment">//A vector holding still undefined class 'data'</span> 279 <span class="identifier">vector</span><span class="special"><</span><span class="identifier">data</span><span class="special">></span> <span class="identifier">v_</span><span class="special">;</span> 280 <span class="identifier">vector</span><span class="special"><</span><span class="identifier">data</span><span class="special">>::</span><span class="identifier">iterator</span> <span class="identifier">vi_</span><span class="special">;</span> 281 <span class="comment">//A stable_vector holding still undefined class 'data'</span> 282 <span class="identifier">stable_vector</span><span class="special"><</span><span class="identifier">data</span><span class="special">></span> <span class="identifier">sv_</span><span class="special">;</span> 283 <span class="identifier">stable_vector</span><span class="special"><</span><span class="identifier">data</span><span class="special">>::</span><span class="identifier">iterator</span> <span class="identifier">svi_</span><span class="special">;</span> 284 <span class="comment">//A stable_vector holding still undefined class 'data'</span> 285 <span class="identifier">deque</span><span class="special"><</span><span class="identifier">data</span><span class="special">></span> <span class="identifier">d_</span><span class="special">;</span> 286 <span class="identifier">deque</span><span class="special"><</span><span class="identifier">data</span><span class="special">>::</span><span class="identifier">iterator</span> <span class="identifier">di_</span><span class="special">;</span> 287 <span class="comment">//A list holding still undefined 'data'</span> 288 <span class="identifier">list</span><span class="special"><</span><span class="identifier">data</span><span class="special">></span> <span class="identifier">l_</span><span class="special">;</span> 289 <span class="identifier">list</span><span class="special"><</span><span class="identifier">data</span><span class="special">>::</span><span class="identifier">iterator</span> <span class="identifier">li_</span><span class="special">;</span> 290 <span class="comment">//A map holding still undefined 'data'</span> 291 <span class="identifier">map</span><span class="special"><</span><span class="identifier">data</span><span class="special">,</span> <span class="identifier">data</span><span class="special">></span> <span class="identifier">m_</span><span class="special">;</span> 292 <span class="identifier">map</span><span class="special"><</span><span class="identifier">data</span><span class="special">,</span> <span class="identifier">data</span><span class="special">>::</span><span class="identifier">iterator</span> <span class="identifier">mi_</span><span class="special">;</span> 293 294 <span class="keyword">friend</span> <span class="keyword">bool</span> <span class="keyword">operator</span> <span class="special"><(</span><span class="keyword">const</span> <span class="identifier">data</span> <span class="special">&</span><span class="identifier">l</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">data</span> <span class="special">&</span><span class="identifier">r</span><span class="special">)</span> 295 <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">l</span><span class="special">.</span><span class="identifier">i_</span> <span class="special"><</span> <span class="identifier">r</span><span class="special">.</span><span class="identifier">i_</span><span class="special">;</span> <span class="special">}</span> 296<span class="special">};</span> 297 298<span class="keyword">struct</span> <span class="identifier">tree_node</span> 299<span class="special">{</span> 300 <span class="identifier">string</span> <span class="identifier">name</span><span class="special">;</span> 301 <span class="identifier">string</span> <span class="identifier">value</span><span class="special">;</span> 302 303 <span class="comment">//children nodes of this node</span> 304 <span class="identifier">list</span><span class="special"><</span><span class="identifier">tree_node</span><span class="special">></span> <span class="identifier">children_</span><span class="special">;</span> 305 <span class="identifier">list</span><span class="special"><</span><span class="identifier">tree_node</span><span class="special">>::</span><span class="identifier">iterator</span> <span class="identifier">selected_child_</span><span class="special">;</span> 306<span class="special">};</span> 307 308 309 310<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span> 311<span class="special">{</span> 312 <span class="comment">//a container holding a recursive data type</span> 313 <span class="identifier">stable_vector</span><span class="special"><</span><span class="identifier">data</span><span class="special">></span> <span class="identifier">sv</span><span class="special">;</span> 314 <span class="identifier">sv</span><span class="special">.</span><span class="identifier">resize</span><span class="special">(</span><span class="number">100</span><span class="special">);</span> 315 316 <span class="comment">//Let's build a tree based in</span> 317 <span class="comment">//a recursive data type</span> 318 <span class="identifier">tree_node</span> <span class="identifier">root</span><span class="special">;</span> 319 <span class="identifier">root</span><span class="special">.</span><span class="identifier">name</span> <span class="special">=</span> <span class="string">"root"</span><span class="special">;</span> 320 <span class="identifier">root</span><span class="special">.</span><span class="identifier">value</span> <span class="special">=</span> <span class="string">"root_value"</span><span class="special">;</span> 321 <span class="identifier">root</span><span class="special">.</span><span class="identifier">children_</span><span class="special">.</span><span class="identifier">resize</span><span class="special">(</span><span class="number">7</span><span class="special">);</span> 322 <span class="identifier">root</span><span class="special">.</span><span class="identifier">selected_child_</span> <span class="special">=</span> <span class="identifier">root</span><span class="special">.</span><span class="identifier">children_</span><span class="special">.</span><span class="identifier">begin</span><span class="special">();</span> 323 <span class="keyword">return</span> <span class="number">0</span><span class="special">;</span> 324<span class="special">}</span> 325</pre> 326<p> 327 </p> 328</div> 329<div class="section"> 330<div class="titlepage"><div><div><h4 class="title"> 331<a name="container.main_features.containers_of_incomplete_types.type_erasure"></a><a class="link" href="main_features.html#container.main_features.containers_of_incomplete_types.type_erasure" title="Type Erasure">Type 332 Erasure</a> 333</h4></div></div></div> 334<p> 335 Containers of incomplete types are useful to break header file dependencies 336 and improve compilation types. With Boost.Container, you can write a header 337 file defining a class with containers of incomplete types as data members, 338 if you carefully put all the implementation details that require knowing 339 the size of the <code class="computeroutput"><span class="identifier">value_type</span></code> 340 in your implementation file: 341 </p> 342<p> 343 In this header file we define a class (<code class="computeroutput"><span class="identifier">MyClassHolder</span><span class="special">)</span></code> that holds a <code class="computeroutput"><span class="identifier">vector</span></code> 344 of an incomplete type (<code class="computeroutput"><span class="identifier">MyClass</span></code>) 345 that it's only forward declared. 346 </p> 347<p> 348</p> 349<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">container</span><span class="special">/</span><span class="identifier">vector</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 350 351<span class="comment">//MyClassHolder.h</span> 352 353<span class="comment">//We don't need to include "MyClass.h"</span> 354<span class="comment">//to store vector<MyClass></span> 355<span class="keyword">class</span> <span class="identifier">MyClass</span><span class="special">;</span> 356 357<span class="keyword">class</span> <span class="identifier">MyClassHolder</span> 358<span class="special">{</span> 359 <span class="keyword">public</span><span class="special">:</span> 360 361 <span class="keyword">void</span> <span class="identifier">AddNewObject</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">MyClass</span> <span class="special">&</span><span class="identifier">o</span><span class="special">);</span> 362 <span class="keyword">const</span> <span class="identifier">MyClass</span> <span class="special">&</span> <span class="identifier">GetLastObject</span><span class="special">()</span> <span class="keyword">const</span><span class="special">;</span> 363 364 <span class="keyword">private</span><span class="special">:</span> 365 <span class="special">::</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">container</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">MyClass</span><span class="special">></span> <span class="identifier">vector_</span><span class="special">;</span> 366<span class="special">};</span> 367</pre> 368<p> 369 </p> 370<p> 371 Then we can define <code class="computeroutput"><span class="identifier">MyClass</span></code> 372 in its own header file. 373 </p> 374<p> 375</p> 376<pre class="programlisting"><span class="comment">//MyClass.h</span> 377 378<span class="keyword">class</span> <span class="identifier">MyClass</span> 379<span class="special">{</span> 380 <span class="keyword">private</span><span class="special">:</span> 381 <span class="keyword">int</span> <span class="identifier">value_</span><span class="special">;</span> 382 383 <span class="keyword">public</span><span class="special">:</span> 384 <span class="identifier">MyClass</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">val</span> <span class="special">=</span> <span class="number">0</span><span class="special">)</span> <span class="special">:</span> <span class="identifier">value_</span><span class="special">(</span><span class="identifier">val</span><span class="special">){}</span> 385 386 <span class="keyword">friend</span> <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">==(</span><span class="keyword">const</span> <span class="identifier">MyClass</span> <span class="special">&</span><span class="identifier">l</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">MyClass</span> <span class="special">&</span><span class="identifier">r</span><span class="special">)</span> 387 <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">l</span><span class="special">.</span><span class="identifier">value_</span> <span class="special">==</span> <span class="identifier">r</span><span class="special">.</span><span class="identifier">value_</span><span class="special">;</span> <span class="special">}</span> 388 <span class="comment">//...</span> 389<span class="special">};</span> 390</pre> 391<p> 392 </p> 393<p> 394 And include it only in the implementation file of <code class="computeroutput"><span class="identifier">MyClassHolder</span></code> 395 </p> 396<p> 397</p> 398<pre class="programlisting"><span class="comment">//MyClassHolder.cpp</span> 399 400<span class="preprocessor">#include</span> <span class="string">"MyClassHolder.h"</span> 401 402<span class="comment">//In the implementation MyClass must be a complete</span> 403<span class="comment">//type so we include the appropriate header</span> 404<span class="preprocessor">#include</span> <span class="string">"MyClass.h"</span> 405 406<span class="keyword">void</span> <span class="identifier">MyClassHolder</span><span class="special">::</span><span class="identifier">AddNewObject</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">MyClass</span> <span class="special">&</span><span class="identifier">o</span><span class="special">)</span> 407<span class="special">{</span> <span class="identifier">vector_</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(</span><span class="identifier">o</span><span class="special">);</span> <span class="special">}</span> 408 409<span class="keyword">const</span> <span class="identifier">MyClass</span> <span class="special">&</span> <span class="identifier">MyClassHolder</span><span class="special">::</span><span class="identifier">GetLastObject</span><span class="special">()</span> <span class="keyword">const</span> 410<span class="special">{</span> <span class="keyword">return</span> <span class="identifier">vector_</span><span class="special">.</span><span class="identifier">back</span><span class="special">();</span> <span class="special">}</span> 411</pre> 412<p> 413 </p> 414<p> 415 Finally, we can just compile, link, and run! 416 </p> 417<p> 418</p> 419<pre class="programlisting"><span class="comment">//Main.cpp</span> 420 421<span class="preprocessor">#include</span> <span class="string">"MyClassHolder.h"</span> 422<span class="preprocessor">#include</span> <span class="string">"MyClass.h"</span> 423 424<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">cassert</span><span class="special">></span> 425 426<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span> 427<span class="special">{</span> 428 <span class="identifier">MyClass</span> <span class="identifier">mc</span><span class="special">(</span><span class="number">7</span><span class="special">);</span> 429 <span class="identifier">MyClassHolder</span> <span class="identifier">myclassholder</span><span class="special">;</span> 430 <span class="identifier">myclassholder</span><span class="special">.</span><span class="identifier">AddNewObject</span><span class="special">(</span><span class="identifier">mc</span><span class="special">);</span> 431 <span class="keyword">return</span> <span class="identifier">myclassholder</span><span class="special">.</span><span class="identifier">GetLastObject</span><span class="special">()</span> <span class="special">==</span> <span class="identifier">mc</span> <span class="special">?</span> <span class="number">0</span> <span class="special">:</span> <span class="number">1</span><span class="special">;</span> 432<span class="special">}</span> 433</pre> 434<p> 435 </p> 436</div> 437</div> 438<div class="section"> 439<div class="titlepage"><div><div><h3 class="title"> 440<a name="container.main_features.scary_iterators"></a><a class="link" href="main_features.html#container.main_features.scary_iterators" title="SCARY iterators">SCARY iterators</a> 441</h3></div></div></div> 442<p> 443 The paper N2913, titled <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2913.pdf" target="_top">SCARY 444 Iterator Assignment and Initialization</a>, proposed a requirement that 445 a standard container's iterator types have no dependency on any type argument 446 apart from the container's <code class="computeroutput"><span class="identifier">value_type</span></code>, 447 <code class="computeroutput"><span class="identifier">difference_type</span></code>, <code class="computeroutput"><span class="identifier">pointer</span> <span class="identifier">type</span></code>, 448 and <code class="computeroutput"><span class="identifier">const_pointer</span></code> type. In 449 particular, according to the proposal, the types of a standard container's 450 iterators should not depend on the container's <code class="computeroutput"><span class="identifier">key_compare</span></code>, 451 <code class="computeroutput"><span class="identifier">hasher</span></code>, <code class="computeroutput"><span class="identifier">key_equal</span></code>, 452 or <code class="computeroutput"><span class="identifier">allocator</span></code> types. 453 </p> 454<p> 455 That paper demonstrated that SCARY operations were crucial to the performant 456 implementation of common design patterns using STL components. It showed 457 that implementations that support SCARY operations reduce object code bloat 458 by eliminating redundant specializations of iterator and algorithm templates. 459 </p> 460<p> 461 <span class="bold"><strong>Boost.Container</strong></span> containers implement SCARY 462 iterators so the iterator type of a container is only dependent on the <code class="computeroutput"><span class="identifier">allocator_traits</span><span class="special"><</span><span class="identifier">allocator_type</span><span class="special">>::</span><span class="identifier">pointer</span></code> type (the pointer type of the 463 <code class="computeroutput"><span class="identifier">value_type</span></code> to be inserted 464 in the container). Reference types and all other typedefs are deduced from 465 the pointer type using the C++11 <code class="computeroutput"><span class="identifier">pointer_traits</span></code> 466 utility. This leads to lower code bloat in algorithms and classes templated 467 on iterators. 468 </p> 469</div> 470<div class="section"> 471<div class="titlepage"><div><div><h3 class="title"> 472<a name="container.main_features.other_features"></a><a class="link" href="main_features.html#container.main_features.other_features" title="Other features">Other features</a> 473</h3></div></div></div> 474<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 475<li class="listitem"> 476 Default constructors don't allocate memory which improves performance 477 and usually implies a no-throw guarantee (if predicate's or allocator's 478 default constructor doesn't throw). 479 </li> 480<li class="listitem"> 481 Small string optimization for <code class="computeroutput"><a class="link" href="../boost/container/basic_string.html" title="Class template basic_string">basic_string</a></code>, 482 with an internal buffer of 11/23 bytes (32/64 bit systems) <span class="bold"><strong>without</strong></span> increasing the usual <code class="computeroutput"><span class="keyword">sizeof</span></code> 483 of the string (3 words). 484 </li> 485<li class="listitem"> 486 <code class="computeroutput"><span class="special">[</span><span class="identifier">multi</span><span class="special">]</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">map</span></code> 487 containers are size optimized embedding the color bit of the red-black 488 tree nodes in the parent pointer. 489 </li> 490<li class="listitem"> 491 <code class="computeroutput"><span class="special">[</span><span class="identifier">multi</span><span class="special">]</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">map</span></code> 492 containers use no recursive functions so stack problems are avoided. 493 </li> 494</ul></div> 495</div> 496</div> 497<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 498<td align="left"></td> 499<td align="right"><div class="copyright-footer">Copyright © 2009-2018 Ion Gaztanaga<p> 500 Distributed under the Boost Software License, Version 1.0. (See accompanying 501 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>) 502 </p> 503</div></td> 504</tr></table> 505<hr> 506<div class="spirit-nav"> 507<a accesskey="p" href="../container.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../container.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="exception_handling.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 508</div> 509</body> 510</html> 511
