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