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>Non-standard containers</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="exception_handling.html" title="Boost.Container and C++ exceptions"> 11<link rel="next" href="extended_functionality.html" title="Extended functionality: Basic extensions"> 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="exception_handling.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="extended_functionality.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.non_standard_containers"></a><a class="link" href="non_standard_containers.html" title="Non-standard containers">Non-standard containers</a> 29</h2></div></div></div> 30<div class="toc"><dl class="toc"> 31<dt><span class="section"><a href="non_standard_containers.html#container.non_standard_containers.stable_vector"><span class="emphasis"><em>stable_vector</em></span></a></span></dt> 32<dt><span class="section"><a href="non_standard_containers.html#container.non_standard_containers.flat_xxx"><span class="emphasis"><em>flat_(multi)map/set</em></span> 33 associative containers</a></span></dt> 34<dt><span class="section"><a href="non_standard_containers.html#container.non_standard_containers.slist"><span class="emphasis"><em>slist</em></span></a></span></dt> 35<dt><span class="section"><a href="non_standard_containers.html#container.non_standard_containers.static_vector"><span class="emphasis"><em>static_vector</em></span></a></span></dt> 36<dt><span class="section"><a href="non_standard_containers.html#container.non_standard_containers.small_vector"><span class="emphasis"><em>small_vector</em></span></a></span></dt> 37</dl></div> 38<div class="section"> 39<div class="titlepage"><div><div><h3 class="title"> 40<a name="container.non_standard_containers.stable_vector"></a><a class="link" href="non_standard_containers.html#container.non_standard_containers.stable_vector" title="stable_vector"><span class="emphasis"><em>stable_vector</em></span></a> 41</h3></div></div></div> 42<p> 43 This useful, fully STL-compliant stable container <a href="http://bannalia.blogspot.com/2008/09/introducing-stablevector.html" target="_top">designed 44 by Joaquín M. López Muñoz</a> is an hybrid between <code class="computeroutput"><span class="identifier">vector</span></code> and <code class="computeroutput"><span class="identifier">list</span></code>, 45 providing most of the features of <code class="computeroutput"><span class="identifier">vector</span></code> 46 except <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#69" target="_top">element 47 contiguity</a>. 48 </p> 49<p> 50 Extremely convenient as they are, <code class="computeroutput"><span class="identifier">vector</span></code>s 51 have a limitation that many novice C++ programmers frequently stumble upon: 52 iterators and references to an element of an <code class="computeroutput"><span class="identifier">vector</span></code> 53 are invalidated when a preceding element is erased or when the vector expands 54 and needs to migrate its internal storage to a wider memory region (i.e. 55 when the required size exceeds the vector's capacity). We say then that 56 <code class="computeroutput"><span class="identifier">vector</span></code>s are unstable: by 57 contrast, stable containers are those for which references and iterators 58 to a given element remain valid as long as the element is not erased: examples 59 of stable containers within the C++ standard library are <code class="computeroutput"><span class="identifier">list</span></code> 60 and the standard associative containers (<code class="computeroutput"><span class="identifier">set</span></code>, 61 <code class="computeroutput"><span class="identifier">map</span></code>, etc.). 62 </p> 63<p> 64 Sometimes stability is too precious a feature to live without, but one particular 65 property of <code class="computeroutput"><span class="identifier">vector</span></code>s, element 66 contiguity, makes it impossible to add stability to this container. So, provided 67 we sacrifice element contiguity, how much can a stable design approach the 68 behavior of <code class="computeroutput"><span class="identifier">vector</span></code> (random 69 access iterators, amortized constant time end insertion/deletion, minimal 70 memory overhead, etc.)? The following image describes the layout of a possible 71 data structure upon which to base the design of a stable vector: 72 </p> 73<p> 74 <span class="inlinemediaobject"><img src="../../../libs/container/doc/images/stable_vector.png" align="middle" width="50%" alt="stable_vector"></span> 75 </p> 76<p> 77 Each element is stored in its own separate node. All the nodes are referenced 78 from a contiguous array of pointers, but also every node contains an "up" 79 pointer referring back to the associated array cell. This up pointer is the 80 key element to implementing stability and random accessibility: 81 </p> 82<p> 83 Iterators point to the nodes rather than to the pointer array. This ensures 84 stability, as it is only the pointer array that needs to be shifted or relocated 85 upon insertion or deletion. Random access operations can be implemented by 86 using the pointer array as a convenient intermediate zone. For instance, 87 if the iterator it holds a node pointer <code class="computeroutput"><span class="identifier">it</span><span class="special">.</span><span class="identifier">p</span></code> and 88 we want to advance it by n positions, we simply do: 89 </p> 90<pre class="programlisting"><span class="identifier">it</span><span class="special">.</span><span class="identifier">p</span> <span class="special">=</span> <span class="special">*(</span><span class="identifier">it</span><span class="special">.</span><span class="identifier">p</span><span class="special">-></span><span class="identifier">up</span><span class="special">+</span><span class="identifier">n</span><span class="special">);</span> 91</pre> 92<p> 93 That is, we go "up" to the pointer array, add n there and then 94 go "down" to the resulting node. 95 </p> 96<p> 97 <span class="bold"><strong>General properties</strong></span>. <code class="computeroutput"><span class="identifier">stable_vector</span></code> 98 satisfies all the requirements of a container, a reversible container and 99 a sequence and provides all the optional operations present in vector. Like 100 vector, iterators are random access. <code class="computeroutput"><span class="identifier">stable_vector</span></code> 101 does not provide element contiguity; in exchange for this absence, the container 102 is stable, i.e. references and iterators to an element of a <code class="computeroutput"><span class="identifier">stable_vector</span></code> remain valid as long as the 103 element is not erased, and an iterator that has been assigned the return 104 value of end() always remain valid until the destruction of the associated 105 <code class="computeroutput"><span class="identifier">stable_vector</span></code>. 106 </p> 107<p> 108 <span class="bold"><strong>Operation complexity</strong></span>. The big-O complexities 109 of <code class="computeroutput"><span class="identifier">stable_vector</span></code> operations 110 match exactly those of vector. In general, insertion/deletion is constant 111 time at the end of the sequence and linear elsewhere. Unlike vector, <code class="computeroutput"><span class="identifier">stable_vector</span></code> does not internally perform 112 any value_type destruction, copy/move construction/assignment operations 113 other than those exactly corresponding to the insertion of new elements or 114 deletion of stored elements, which can sometimes compensate in terms of performance 115 for the extra burden of doing more pointer manipulation and an additional 116 allocation per element. 117 </p> 118<p> 119 <span class="bold"><strong>Exception safety</strong></span>. (according to <a href="http://www.boost.org/community/exception_safety.html" target="_top">Abrahams' 120 terminology</a>) As <code class="computeroutput"><span class="identifier">stable_vector</span></code> 121 does not internally copy/move elements around, some operations provide stronger 122 exception safety guarantees than in vector: 123 </p> 124<div class="table"> 125<a name="container.non_standard_containers.stable_vector.stable_vector_req"></a><p class="title"><b>Table 9.1. Exception safety</b></p> 126<div class="table-contents"><table class="table" summary="Exception safety"> 127<colgroup> 128<col> 129<col> 130<col> 131</colgroup> 132<thead><tr> 133<th> 134 <p> 135 operation 136 </p> 137 </th> 138<th> 139 <p> 140 exception safety for <code class="computeroutput"><span class="identifier">vector</span><span class="special"><</span><span class="identifier">T</span><span class="special">></span></code> 141 </p> 142 </th> 143<th> 144 <p> 145 exception safety for <code class="computeroutput"><span class="identifier">stable_vector</span><span class="special"><</span><span class="identifier">T</span><span class="special">></span></code> 146 </p> 147 </th> 148</tr></thead> 149<tbody> 150<tr> 151<td> 152 <p> 153 insert 154 </p> 155 </td> 156<td> 157 <p> 158 strong unless copy/move construction/assignment of <code class="computeroutput"><span class="identifier">T</span></code> throw (basic) 159 </p> 160 </td> 161<td> 162 <p> 163 strong 164 </p> 165 </td> 166</tr> 167<tr> 168<td> 169 <p> 170 erase 171 </p> 172 </td> 173<td> 174 <p> 175 no-throw unless copy/move construction/assignment of <code class="computeroutput"><span class="identifier">T</span></code> throw (basic) 176 </p> 177 </td> 178<td> 179 <p> 180 no-throw 181 </p> 182 </td> 183</tr> 184</tbody> 185</table></div> 186</div> 187<br class="table-break"><p> 188 <span class="bold"><strong>Memory overhead</strong></span>. The C++ standard does not 189 specify requirements on memory consumption, but virtually any implementation 190 of <code class="computeroutput"><span class="identifier">vector</span></code> has the same behavior 191 with respect to memory usage: the memory allocated by a <code class="computeroutput"><span class="identifier">vector</span></code> 192 v with n elements of type T is 193 </p> 194<p> 195 m<sub>v</sub> = c∙e, 196 </p> 197<p> 198 where c is <code class="computeroutput"><span class="identifier">v</span><span class="special">.</span><span class="identifier">capacity</span><span class="special">()</span></code> 199 and e is <code class="computeroutput"><span class="keyword">sizeof</span><span class="special">(</span><span class="identifier">T</span><span class="special">)</span></code>. c can 200 be as low as n if the user has explicitly reserved the exact capacity required; 201 otherwise, the average value c for a growing <code class="computeroutput"><span class="identifier">vector</span></code> 202 oscillates between 1.25∙n and 1.5∙n for typical resizing policies. 203 For <code class="computeroutput"><span class="identifier">stable_vector</span></code>, the memory 204 usage is 205 </p> 206<p> 207 m<sub>sv</sub> = (c + 1)p + (n + 1)(e + p), 208 </p> 209<p> 210 where p is the size of a pointer. We have c + 1 and n + 1 rather than c and 211 n because a dummy node is needed at the end of the sequence. If we call f 212 the capacity to size ratio c/n and assume that n is large enough, we have 213 that 214 </p> 215<p> 216 m<sub>sv</sub>/m<sub>v</sub> ≃ (fp + e + p)/fe. 217 </p> 218<p> 219 So, <code class="computeroutput"><span class="identifier">stable_vector</span></code> uses less 220 memory than <code class="computeroutput"><span class="identifier">vector</span></code> only when 221 e > p and the capacity to size ratio exceeds a given threshold: 222 </p> 223<p> 224 m<sub>sv</sub> < m<sub>v</sub> <-> f > (e + p)/(e - p). (provided e > p) 225 </p> 226<p> 227 This threshold approaches typical values of f below 1.5 when e > 5p; in 228 a 32-bit architecture, when e > 20 bytes. 229 </p> 230<p> 231 <span class="bold"><strong>Summary</strong></span>. <code class="computeroutput"><span class="identifier">stable_vector</span></code> 232 is a drop-in replacement for <code class="computeroutput"><span class="identifier">vector</span></code> 233 providing stability of references and iterators, in exchange for missing 234 element contiguity and also some performance and memory overhead. When the 235 element objects are expensive to move around, the performance overhead can 236 turn into a net performance gain for <code class="computeroutput"><span class="identifier">stable_vector</span></code> 237 if many middle insertions or deletions are performed or if resizing is very 238 frequent. Similarly, if the elements are large there are situations when 239 the memory used by <code class="computeroutput"><span class="identifier">stable_vector</span></code> 240 can actually be less than required by vector. 241 </p> 242<p> 243 <span class="emphasis"><em>Note: Text and explanations taken from <a href="http://bannalia.blogspot.com/2008/09/introducing-stablevector.html" target="_top">Joaquín's 244 blog</a></em></span> 245 </p> 246</div> 247<div class="section"> 248<div class="titlepage"><div><div><h3 class="title"> 249<a name="container.non_standard_containers.flat_xxx"></a><a class="link" href="non_standard_containers.html#container.non_standard_containers.flat_xxx" title="flat_(multi)map/set associative containers"><span class="emphasis"><em>flat_(multi)map/set</em></span> 250 associative containers</a> 251</h3></div></div></div> 252<p> 253 Using sorted vectors instead of tree-based associative containers is a well-known 254 technique in C++ world. Matt Austern's classic article <a href="http://lafstern.org/matt/col1.pdf" target="_top">Why 255 You Shouldn't Use set, and What You Should Use Instead</a> (C++ Report 256 12:4, April 2000) was enlightening: 257 </p> 258<p> 259 <span class="quote">“<span class="quote"><span class="emphasis"><em>Red-black trees aren't the only way to organize data that 260 permits lookup in logarithmic time. One of the basic algorithms of computer 261 science is binary search, which works by successively dividing a range in 262 half. Binary search is log N and it doesn't require any fancy data structures, 263 just a sorted collection of elements. (...) You can use whatever data structure 264 is convenient, so long as it provides STL iterator; usually it's easiest 265 to use a C array, or a vector.</em></span></span>”</span> 266 </p> 267<p> 268 <span class="quote">“<span class="quote"><span class="emphasis"><em>Both std::lower_bound and set::find take time proportional 269 to log N, but the constants of proportionality are very different. Using 270 g++ (...) it takes X seconds to perform a million lookups in a sorted vector<double> 271 of a million elements, and almost twice as long (...) using a set. Moreover, 272 the set uses almost three times as much memory (48 million bytes) as the 273 vector (16.8 million).</em></span></span>”</span> 274 </p> 275<p> 276 <span class="quote">“<span class="quote"><span class="emphasis"><em>Using a sorted vector instead of a set gives you faster 277 lookup and much faster iteration, but at the cost of slower insertion. Insertion 278 into a set, using set::insert, is proportional to log N, but insertion into 279 a sorted vector, (...) , is proportional to N. Whenever you insert something 280 into a vector, vector::insert has to make room by shifting all of the elements 281 that follow it. On average, if you're equally likely to insert a new element 282 anywhere, you'll be shifting N/2 elements.</em></span></span>”</span> 283 </p> 284<p> 285 <span class="quote">“<span class="quote"><span class="emphasis"><em>It may sometimes be convenient to bundle all of this together 286 into a small container adaptor. This class does not satisfy the requirements 287 of a Standard Associative Container, since the complexity of insert is O(N) 288 rather than O(log N), but otherwise it is almost a drop-in replacement for 289 set.</em></span></span>”</span> 290 </p> 291<p> 292 Following Matt Austern's indications, Andrei Alexandrescu's <a href="http://www.bestwebbuys.com/Modern-C-Design-Generic-Programming-and-Design-Patterns-Applied-ISBN-9780201704310?isrc=-rd" target="_top">Modern 293 C++ Design</a> showed <code class="computeroutput"><span class="identifier">AssocVector</span></code>, 294 a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">map</span></code> drop-in replacement designed in his 295 <a href="http://loki-lib.sourceforge.net/" target="_top">Loki</a> library: 296 </p> 297<p> 298 <span class="quote">“<span class="quote"><span class="emphasis"><em>It seems as if we're better off with a sorted vector. The 299 disadvantages of a sorted vector are linear-time insertions and linear-time 300 deletions (...). In exchange, a vector offers about twice the lookup speed 301 and a much smaller working set (...). Loki saves the trouble of maintaining 302 a sorted vector by hand by defining an AssocVector class template. AssocVector 303 is a drop-in replacement for std::map (it supports the same set of member 304 functions), implemented on top of std::vector. AssocVector differs from a 305 map in the behavior of its erase functions (AssocVector::erase invalidates 306 all iterators into the object) and in the complexity guarantees of insert 307 and erase (linear as opposed to constant). </em></span></span>”</span> 308 </p> 309<p> 310 <span class="bold"><strong>Boost.Container</strong></span> <code class="computeroutput"><span class="identifier">flat_</span><span class="special">[</span><span class="identifier">multi</span><span class="special">]</span><span class="identifier">map</span><span class="special">/</span><span class="identifier">set</span></code> containers are ordered, vector-like 311 container based, associative containers following Austern's and Alexandrescu's 312 guidelines. These ordered vector containers have also benefited with the 313 addition of <code class="computeroutput"><span class="identifier">move</span> <span class="identifier">semantics</span></code> 314 to C++11, speeding up insertion and erasure times considerably. Flat associative 315 containers have the following attributes: 316 </p> 317<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 318<li class="listitem"> 319 Faster lookup than standard associative containers 320 </li> 321<li class="listitem"> 322 Much faster iteration than standard associative containers. Random-access 323 iterators instead of bidirectional iterators. 324 </li> 325<li class="listitem"> 326 Less memory consumption for small objects (and for big objects if <code class="computeroutput"><span class="identifier">shrink_to_fit</span></code> is used) 327 </li> 328<li class="listitem"> 329 Improved cache performance (data is stored in contiguous memory) 330 </li> 331<li class="listitem"> 332 Non-stable iterators (iterators are invalidated when inserting and erasing 333 elements) 334 </li> 335<li class="listitem"> 336 Non-copyable and non-movable values types can't be stored 337 </li> 338<li class="listitem"> 339 Weaker exception safety than standard associative containers (copy/move 340 constructors can throw when shifting values in erasures and insertions) 341 </li> 342<li class="listitem"> 343 Slower insertion and erasure than standard associative containers (specially 344 for non-movable types) 345 </li> 346</ul></div> 347</div> 348<div class="section"> 349<div class="titlepage"><div><div><h3 class="title"> 350<a name="container.non_standard_containers.slist"></a><a class="link" href="non_standard_containers.html#container.non_standard_containers.slist" title="slist"><span class="emphasis"><em>slist</em></span></a> 351</h3></div></div></div> 352<p> 353 When the standard template library was designed, it contained a singly linked 354 list called <code class="computeroutput"><span class="identifier">slist</span></code>. Unfortunately, 355 this container was not standardized and remained as an extension for many 356 standard library implementations until C++11 introduced <code class="computeroutput"><span class="identifier">forward_list</span></code>, 357 which is a bit different from the the original SGI <code class="computeroutput"><span class="identifier">slist</span></code>. 358 According to <a href="http://www.sgi.com/tech/stl/Slist.html" target="_top">SGI STL 359 documentation</a>: 360 </p> 361<p> 362 <span class="quote">“<span class="quote"><span class="emphasis"><em>An <code class="computeroutput"><span class="identifier">slist</span></code> 363 is a singly linked list: a list where each element is linked to the next 364 element, but not to the previous element. That is, it is a Sequence that 365 supports forward but not backward traversal, and (amortized) constant time 366 insertion and removal of elements. Slists, like lists, have the important 367 property that insertion and splicing do not invalidate iterators to list 368 elements, and that even removal invalidates only the iterators that point 369 to the elements that are removed. The ordering of iterators may be changed 370 (that is, slist<T>::iterator might have a different predecessor or 371 successor after a list operation than it did before), but the iterators themselves 372 will not be invalidated or made to point to different elements unless that 373 invalidation or mutation is explicit.</em></span></span>”</span> 374 </p> 375<p> 376 <span class="quote">“<span class="quote"><span class="emphasis"><em>The main difference between <code class="computeroutput"><span class="identifier">slist</span></code> 377 and list is that list's iterators are bidirectional iterators, while slist's 378 iterators are forward iterators. This means that <code class="computeroutput"><span class="identifier">slist</span></code> 379 is less versatile than list; frequently, however, bidirectional iterators 380 are unnecessary. You should usually use <code class="computeroutput"><span class="identifier">slist</span></code> 381 unless you actually need the extra functionality of list, because singly 382 linked lists are smaller and faster than double linked lists.</em></span></span>”</span> 383 </p> 384<p> 385 <span class="quote">“<span class="quote"><span class="emphasis"><em>Important performance note: like every other Sequence, 386 <code class="computeroutput"><span class="identifier">slist</span></code> defines the member 387 functions insert and erase. Using these member functions carelessly, however, 388 can result in disastrously slow programs. The problem is that insert's first 389 argument is an iterator pos, and that it inserts the new element(s) before 390 pos. This means that insert must find the iterator just before pos; this 391 is a constant-time operation for list, since list has bidirectional iterators, 392 but for <code class="computeroutput"><span class="identifier">slist</span></code> it must find 393 that iterator by traversing the list from the beginning up to pos. In other 394 words: insert and erase are slow operations anywhere but near the beginning 395 of the slist.</em></span></span>”</span> 396 </p> 397<p> 398 <span class="quote">“<span class="quote"><span class="emphasis"><em>Slist provides the member functions insert_after and erase_after, 399 which are constant time operations: you should always use insert_after and 400 erase_after whenever possible. If you find that insert_after and erase_after 401 aren't adequate for your needs, and that you often need to use insert and 402 erase in the middle of the list, then you should probably use list instead 403 of slist.</em></span></span>”</span> 404 </p> 405<p> 406 <span class="bold"><strong>Boost.Container</strong></span> updates the classic <code class="computeroutput"><span class="identifier">slist</span></code> container with C++11 features like 407 move semantics and placement insertion and implements it a bit differently 408 than the standard C++ <code class="computeroutput"><span class="identifier">forward_list</span></code>. 409 <code class="computeroutput"><span class="identifier">forward_list</span></code> has no <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code> 410 method, so it's been designed to allow (or in practice, encourage) implementations 411 without tracking list size with every insertion/erasure, allowing constant-time 412 <code class="computeroutput"><span class="identifier">splice_after</span><span class="special">(</span><span class="identifier">iterator</span><span class="special">,</span> <span class="identifier">forward_list</span> <span class="special">&,</span> 413 <span class="identifier">iterator</span><span class="special">,</span> 414 <span class="identifier">iterator</span><span class="special">)</span></code>-based 415 list merging. On the other hand <code class="computeroutput"><span class="identifier">slist</span></code> 416 offers constant-time <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code> for those that don't care about linear-time 417 <code class="computeroutput"><span class="identifier">splice_after</span><span class="special">(</span><span class="identifier">iterator</span><span class="special">,</span> <span class="identifier">slist</span> <span class="special">&,</span> 418 <span class="identifier">iterator</span><span class="special">,</span> 419 <span class="identifier">iterator</span><span class="special">)</span></code> 420 <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code> 421 and offers an additional <code class="computeroutput"><span class="identifier">splice_after</span><span class="special">(</span><span class="identifier">iterator</span><span class="special">,</span> <span class="identifier">slist</span> <span class="special">&,</span> <span class="identifier">iterator</span><span class="special">,</span> <span class="identifier">iterator</span><span class="special">,</span> <span class="identifier">size_type</span><span class="special">)</span></code> method that can speed up <code class="computeroutput"><span class="identifier">slist</span></code> 422 merging when the programmer already knows the size. <code class="computeroutput"><span class="identifier">slist</span></code> 423 and <code class="computeroutput"><span class="identifier">forward_list</span></code> are therefore 424 complementary. 425 </p> 426</div> 427<div class="section"> 428<div class="titlepage"><div><div><h3 class="title"> 429<a name="container.non_standard_containers.static_vector"></a><a class="link" href="non_standard_containers.html#container.non_standard_containers.static_vector" title="static_vector"><span class="emphasis"><em>static_vector</em></span></a> 430</h3></div></div></div> 431<p> 432 <code class="computeroutput"><span class="identifier">static_vector</span></code> is an hybrid 433 between <code class="computeroutput"><span class="identifier">vector</span></code> and <code class="computeroutput"><span class="identifier">array</span></code>: like <code class="computeroutput"><span class="identifier">vector</span></code>, 434 it's a sequence container with contiguous storage that can change in size, 435 along with the static allocation, low overhead, and fixed capacity of <code class="computeroutput"><span class="identifier">array</span></code>. <code class="computeroutput"><span class="identifier">static_vector</span></code> 436 is based on Adam Wulkiewicz and Andrew Hundt's high-performance <a href="https://svn.boost.org/svn/boost/sandbox/varray/doc/html/index.html" target="_top">varray</a> 437 class. 438 </p> 439<p> 440 The number of elements in a <code class="computeroutput"><span class="identifier">static_vector</span></code> 441 may vary dynamically up to a fixed capacity because elements are stored within 442 the object itself similarly to an array. However, objects are initialized 443 as they are inserted into <code class="computeroutput"><span class="identifier">static_vector</span></code> 444 unlike C arrays or <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">array</span></code> which must construct all elements 445 on instantiation. The behavior of <code class="computeroutput"><span class="identifier">static_vector</span></code> 446 enables the use of statically allocated elements in cases with complex object 447 lifetime requirements that would otherwise not be trivially possible. Some 448 other properties: 449 </p> 450<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 451<li class="listitem"> 452 Random access to elements 453 </li> 454<li class="listitem"> 455 Constant time insertion and removal of elements at the end 456 </li> 457<li class="listitem"> 458 Linear time insertion and removal of elements at the beginning or in 459 the middle. 460 </li> 461</ul></div> 462<p> 463 <code class="computeroutput"><span class="identifier">static_vector</span></code> is well suited 464 for use in a buffer, the internal implementation of other classes, or use 465 cases where there is a fixed limit to the number of elements that must be 466 stored. Embedded and realtime applications where allocation either may not 467 be available or acceptable are a particular case where <code class="computeroutput"><span class="identifier">static_vector</span></code> 468 can be beneficial. 469 </p> 470</div> 471<div class="section"> 472<div class="titlepage"><div><div><h3 class="title"> 473<a name="container.non_standard_containers.small_vector"></a><a class="link" href="non_standard_containers.html#container.non_standard_containers.small_vector" title="small_vector"><span class="emphasis"><em>small_vector</em></span></a> 474</h3></div></div></div> 475<p> 476 <code class="computeroutput"><span class="identifier">small_vector</span></code> is a vector-like 477 container optimized for the case when it contains few elements. It contains 478 some preallocated elements in-place, which allows it to avoid the use of 479 dynamic storage allocation when the actual number of elements is below that 480 preallocated threshold. <code class="computeroutput"><span class="identifier">small_vector</span></code> 481 is inspired by <a href="http://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h" target="_top">LLVM's 482 <code class="computeroutput"><span class="identifier">SmallVector</span></code></a> container. 483 Unlike <code class="computeroutput"><span class="identifier">static_vector</span></code>, <code class="computeroutput"><span class="identifier">small_vector</span></code>'s capacity can grow beyond 484 the initial preallocated capacity. 485 </p> 486<p> 487 <code class="computeroutput"><span class="identifier">small_vector</span><span class="special"><</span><span class="identifier">T</span><span class="special">,</span> <span class="identifier">N</span><span class="special">,</span> <span class="identifier">Allocator</span><span class="special">></span></code> is convertible to <code class="computeroutput"><span class="identifier">small_vector_base</span><span class="special"><</span><span class="identifier">T</span><span class="special">,</span> 488 <span class="identifier">Allocator</span><span class="special">></span></code>, 489 a type that is independent from the preallocated element count, allowing 490 client code that does not need to be templated on that N argument. <code class="computeroutput"><span class="identifier">small_vector</span></code> inherits all <code class="computeroutput"><span class="identifier">vector</span></code>'s member functions so it supports 491 all standard features like emplacement, stateful allocators, etc. 492 </p> 493</div> 494</div> 495<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 496<td align="left"></td> 497<td align="right"><div class="copyright-footer">Copyright © 2009-2018 Ion Gaztanaga<p> 498 Distributed under the Boost Software License, Version 1.0. (See accompanying 499 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>) 500 </p> 501</div></td> 502</tr></table> 503<hr> 504<div class="spirit-nav"> 505<a accesskey="p" href="exception_handling.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="extended_functionality.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 506</div> 507</body> 508</html> 509
