doc/html/container/non_standard_containers.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>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&#160;10.&#160;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">
  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&#237;n M. L&#243;pez Mu&#241;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/html/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">-&gt;</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&#160;10.1.&#160;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">&lt;</span><span class="identifier">T</span><span class="special">&gt;</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">&lt;</span><span class="identifier">T</span><span class="special">&gt;</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         specifiy requirements on memory consumption, but virtually any implementation
 190         of <code class="computeroutput"><span class="identifier">vector</span></code> has the same behavior
 191         wih 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&#8729;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&#8729;n and 1.5&#8729;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> &#8771; (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 &gt; p and the capacity to size ratio exceeds a given threshold:
 222       </p>
 223 <p>
 224         m<sub>sv</sub> &lt; m<sub>v</sub> &lt;-&gt; f &gt; (e + p)/(e - p). (provided e &gt; p)
 225       </p>
 226 <p>
 227         This threshold approaches typical values of f below 1.5 when e &gt; 5p; in
 228         a 32-bit architecture, when e &gt; 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&#237;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">&#8220;<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>&#8221;</span>
 266       </p>
 267 <p>
 268         <span class="quote">&#8220;<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&lt;double&gt;
 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>&#8221;</span>
 274       </p>
 275 <p>
 276         <span class="quote">&#8220;<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>&#8221;</span>
 283       </p>
 284 <p>
 285         <span class="quote">&#8220;<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>&#8221;</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">&#8220;<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>&#8221;</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 based
 311         associative containers based on Austern's and Alexandrescu's guidelines.
 312         These ordered vector containers have also benefited recently with the addition
 313         of <code class="computeroutput"><span class="identifier">move</span> <span class="identifier">semantics</span></code>
 314         to C++, 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">&#8220;<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&lt;T&gt;::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>&#8221;</span>
 374       </p>
 375 <p>
 376         <span class="quote">&#8220;<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>&#8221;</span>
 383       </p>
 384 <p>
 385         <span class="quote">&#8220;<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>&#8221;</span>
 396       </p>
 397 <p>
 398         <span class="quote">&#8220;<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>&#8221;</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">&amp;,</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">&amp;,</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">&amp;,</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">&lt;</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">&gt;</span></code> is convertible to <code class="computeroutput"><span class="identifier">small_vector_base</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">,</span>
 488         <span class="identifier">Allocator</span><span class="special">&gt;</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 &#169; 2009-2015 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>