Gitiles
Code Review Sign In
realtimeroboticsgroup.org / RealtimeRoboticsGroup / test / a57b70145cb0a950c1c3a9a4fddf0438c60126f2 / . / third_party / boostorg / utility / Collection.html
blob: b92ddd6eeb0388a088311eaeb5dc964d1e72a5f1 [file] [log] [blame]
Brian Silverman60e3e2a2018-08-04 23:57:12 -0700[diff] [blame]1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
2
3<html>
4<head>
5 <meta http-equiv="Content-Language" content="en-us">
6 <meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
7
8 <title>Collection</title>
9</head>
10
11<body bgcolor="#FFFFFF" link="#0000EE" text="#000000" vlink="#551A8B" alink=
12"#FF0000">
13 <h1><img src="../../boost.png" alt="boost logo" width="277" align="middle"
14 height="86"><br>
15 Collection</h1>
16
17 <h3>Description</h3>
18
19 <p>A Collection is a <i>concept</i> similar to the STL <a href=
20 "http://www.sgi.com/tech/stl/Container.html">Container</a> concept. A
21 Collection provides iterators for accessing a range of elements and
22 provides information about the number of elements in the Collection.
23 However, a Collection has fewer requirements than a Container. The
24 motivation for the Collection concept is that there are many useful
25 Container-like types that do not meet the full requirements of Container,
26 and many algorithms that can be written with this reduced set of
27 requirements. To summarize the reduction in requirements:</p>
28
29 <ul>
30 <li>It is not required to "own" its elements: the lifetime of an element
31 in a Collection does not have to match the lifetime of the Collection
32 object, though the lifetime of the element should cover the lifetime of
33 the Collection object.</li>
34
35 <li>The semantics of copying a Collection object is not defined (it could
36 be a deep or shallow copy or not even support copying).</li>
37
38 <li>The associated reference type of a Collection does not have to be a
39 real C++ reference.</li>
40 </ul>Because of the reduced requirements, some care must be taken when
41 writing code that is meant to be generic for all Collection types. In
42 particular, a Collection object should be passed by-reference since
43 assumptions can not be made about the behaviour of the copy constructor.
44
45 <h3>Associated types</h3>
46
47 <table border summary="">
48 <tr>
49 <td valign="top">Value type</td>
50
51 <td valign="top"><tt>X::value_type</tt></td>
52
53 <td valign="top">The type of the object stored in a Collection. If the
54 Collection is <i>mutable</i> then the value type must be <a href=
55 "http://www.sgi.com/tech/stl/Assignable.html">Assignable</a>. Otherwise
56 the value type must be <a href=
57 "./CopyConstructible.html">CopyConstructible</a>.</td>
58 </tr>
59
60 <tr>
61 <td valign="top">Iterator type</td>
62
63 <td valign="top"><tt>X::iterator</tt></td>
64
65 <td valign="top">The type of iterator used to iterate through a
66 Collection's elements. The iterator's value type is expected to be the
67 Collection's value type. A conversion from the iterator type to the
68 const iterator type must exist. The iterator type must be an <a href=
69 "http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.</td>
70 </tr>
71
72 <tr>
73 <td valign="top">Const iterator type</td>
74
75 <td valign="top"><tt>X::const_iterator</tt></td>
76
77 <td valign="top">A type of iterator that may be used to examine, but
78 not to modify, a Collection's elements.</td>
79 </tr>
80
81 <tr>
82 <td valign="top">Reference type</td>
83
84 <td valign="top"><tt>X::reference</tt></td>
85
86 <td valign="top">A type that behaves like a reference to the
87 Collection's value type. <a href="#n1">[1]</a></td>
88 </tr>
89
90 <tr>
91 <td valign="top">Const reference type</td>
92
93 <td valign="top"><tt>X::const_reference</tt></td>
94
95 <td valign="top">A type that behaves like a const reference to the
96 Collection's value type.</td>
97 </tr>
98
99 <tr>
100 <td valign="top">Pointer type</td>
101
102 <td valign="top"><tt>X::pointer</tt></td>
103
104 <td valign="top">A type that behaves as a pointer to the Collection's
105 value type.</td>
106 </tr>
107
108 <tr>
109 <td valign="top">Distance type</td>
110
111 <td valign="top"><tt>X::difference_type</tt></td>
112
113 <td valign="top">A signed integral type used to represent the distance
114 between two of the Collection's iterators. This type must be the same
115 as the iterator's distance type.</td>
116 </tr>
117
118 <tr>
119 <td valign="top">Size type</td>
120
121 <td valign="top"><tt>X::size_type</tt></td>
122
123 <td valign="top">An unsigned integral type that can represent any
124 nonnegative value of the Collection's distance type.</td>
125 </tr>
126 </table>
127
128 <h3>Notation</h3>
129
130 <table summary="">
131 <tr>
132 <td valign="top"><tt>X</tt></td>
133
134 <td valign="top">A type that is a model of Collection.</td>
135 </tr>
136
137 <tr>
138 <td valign="top"><tt>a</tt>, <tt>b</tt></td>
139
140 <td valign="top">Object of type <tt>X</tt>.</td>
141 </tr>
142
143 <tr>
144 <td valign="top"><tt>T</tt></td>
145
146 <td valign="top">The value type of <tt>X</tt>.</td>
147 </tr>
148 </table>
149
150 <h3>Valid expressions</h3>
151
152 <p>The following expressions must be valid.</p>
153
154 <table border summary="">
155 <tr>
156 <th>Name</th>
157
158 <th>Expression</th>
159
160 <th>Return type</th>
161 </tr>
162
163 <tr>
164 <td valign="top">Beginning of range</td>
165
166 <td valign="top"><tt>a.begin()</tt></td>
167
168 <td valign="top"><tt>iterator</tt> if <tt>a</tt> is mutable,
169 <tt>const_iterator</tt> otherwise</td>
170 </tr>
171
172 <tr>
173 <td valign="top">End of range</td>
174
175 <td valign="top"><tt>a.end()</tt></td>
176
177 <td valign="top"><tt>iterator</tt> if <tt>a</tt> is mutable,
178 <tt>const_iterator</tt> otherwise</td>
179 </tr>
180
181 <tr>
182 <td valign="top">Size</td>
183
184 <td valign="top"><tt>a.size()</tt></td>
185
186 <td valign="top"><tt>size_type</tt></td>
187 </tr><!--
188<TR>
189<TD VAlign=top>
190Maximum size
191</TD>
192<TD VAlign=top>
193<tt>a.max_size()</tt>
194</TD>
195<TD VAlign=top>
196<tt>size_type</tt>
197</TD>
198</TR>
199-->
200
201 <tr>
202 <td valign="top">Empty Collection</td>
203
204 <td valign="top"><tt>a.empty()</tt></td>
205
206 <td valign="top">Convertible to <tt>bool</tt></td>
207 </tr>
208
209 <tr>
210 <td valign="top">Swap</td>
211
212 <td valign="top"><tt>a.swap(b)</tt></td>
213
214 <td valign="top"><tt>void</tt></td>
215 </tr>
216 </table>
217
218 <h3>Expression semantics</h3>
219
220 <table border summary="">
221 <tr>
222 <th>Name</th>
223
224 <th>Expression</th>
225
226 <th>Semantics</th>
227
228 <th>Postcondition</th>
229 </tr>
230
231 <tr>
232 <td valign="top">Beginning of range</td>
233
234 <td valign="top"><tt>a.begin()</tt></td>
235
236 <td valign="top">Returns an iterator pointing to the first element in
237 the Collection.</td>
238
239 <td valign="top"><tt>a.begin()</tt> is either dereferenceable or
240 past-the-end. It is past-the-end if and only if <tt>a.size() ==
241 0</tt>.</td>
242 </tr>
243
244 <tr>
245 <td valign="top">End of range</td>
246
247 <td valign="top"><tt>a.end()</tt></td>
248
249 <td valign="top">Returns an iterator pointing one past the last element
250 in the Collection.</td>
251
252 <td valign="top"><tt>a.end()</tt> is past-the-end.</td>
253 </tr>
254
255 <tr>
256 <td valign="top">Size</td>
257
258 <td valign="top"><tt>a.size()</tt></td>
259
260 <td valign="top">Returns the size of the Collection, that is, its
261 number of elements.</td>
262
263 <td valign="top"><tt>a.size() &gt;= 0</tt></td>
264 </tr><!--
265<TR>
266<TD VAlign=top>
267Maximum size
268</TD>
269<TD VAlign=top>
270<tt>a.max_size()</tt>
271</TD>
272<TD VAlign=top>
273&nbsp;
274</TD>
275<TD VAlign=top>
276Returns the largest size that this Collection can ever have. <A href="#8">[8]</A>
277</TD>
278<TD VAlign=top>
279<tt>a.max_size() &gt;= 0 &amp;&amp; a.max_size() &gt;= a.size()</tt>
280</TD>
281</TR>
282 -->
283
284 <tr>
285 <td valign="top">Empty Collection</td>
286
287 <td valign="top"><tt>a.empty()</tt></td>
288
289 <td valign="top">Equivalent to <tt>a.size() == 0</tt>. (But possibly
290 faster.)</td>
291
292 <td valign="top">&nbsp;</td>
293 </tr>
294
295 <tr>
296 <td valign="top">Swap</td>
297
298 <td valign="top"><tt>a.swap(b)</tt></td>
299
300 <td valign="top">Equivalent to <tt>swap(a,b)</tt></td>
301
302 <td valign="top">&nbsp;</td>
303 </tr>
304 </table>
305
306 <h3>Complexity guarantees</h3>
307
308 <p><tt>begin()</tt> and <tt>end()</tt> are amortized constant time.</p>
309
310 <p><tt>size()</tt> is at most linear in the Collection's size.
311 <tt>empty()</tt> is amortized constant time.</p>
312
313 <p><tt>swap()</tt> is at most linear in the size of the two
314 collections.</p>
315
316 <h3>Invariants</h3>
317
318 <table border summary="">
319 <tr>
320 <td valign="top">Valid range</td>
321
322 <td valign="top">For any Collection <tt>a</tt>, <tt>[a.begin(),
323 a.end())</tt> is a valid range.</td>
324 </tr>
325
326 <tr>
327 <td valign="top">Range size</td>
328
329 <td valign="top"><tt>a.size()</tt> is equal to the distance from
330 <tt>a.begin()</tt> to <tt>a.end()</tt>.</td>
331 </tr>
332
333 <tr>
334 <td valign="top">Completeness</td>
335
336 <td valign="top">An algorithm that iterates through the range
337 <tt>[a.begin(), a.end())</tt> will pass through every element of
338 <tt>a</tt>.</td>
339 </tr>
340 </table>
341
342 <h3>Models</h3>
343
344 <ul>
345 <li><tt>array</tt></li>
346
347 <li><tt>array_ptr</tt></li>
348
349 <li><tt>vector&lt;bool&gt;</tt></li>
350 </ul>
351
352 <h3>Collection Refinements</h3>
353
354 <p>There are quite a few concepts that refine the Collection concept,
355 similar to the concepts that refine the Container concept. Here is a brief
356 overview of the refining concepts.</p>
357
358 <h4>ForwardCollection</h4>
359
360 <p>The elements are arranged in some order that does not change
361 spontaneously from one iteration to the next. As a result, a
362 ForwardCollection is <a href=
363 "http://www.sgi.com/tech/stl/EqualityComparable.html">EqualityComparable</a>
364 and <a href=
365 "http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>.
366 In addition, the iterator type of a ForwardCollection is a
367 MultiPassInputIterator which is just an InputIterator with the added
368 requirements that the iterator can be used to make multiple passes through
369 a range, and that if <tt>it1 == it2</tt> and <tt>it1</tt> is
370 dereferenceable then <tt>++it1 == ++it2</tt>. The ForwardCollection also
371 has a <tt>front()</tt> method.</p>
372
373 <table border summary="">
374 <tr>
375 <th>Name</th>
376
377 <th>Expression</th>
378
379 <th>Return type</th>
380
381 <th>Semantics</th>
382 </tr>
383
384 <tr>
385 <td valign="top">Front</td>
386
387 <td valign="top"><tt>a.front()</tt></td>
388
389 <td valign="top"><tt>reference</tt> if <tt>a</tt> is mutable,<br>
390 <tt>const_reference</tt> otherwise.</td>
391
392 <td valign="top">Equivalent to <tt>*(a.begin())</tt>.</td>
393 </tr>
394 </table>
395
396 <h4>ReversibleCollection</h4>
397
398 <p>The container provides access to iterators that traverse in both
399 directions (forward and reverse). The iterator type must meet all of the
400 requirements of <a href=
401 "http://www.sgi.com/tech/stl/BidirectionalIterator.html">BidirectionalIterator</a>
402 except that the reference type does not have to be a real C++ reference.
403 The ReversibleCollection adds the following requirements to those of
404 ForwardCollection.</p>
405
406 <table border summary="">
407 <tr>
408 <th>Name</th>
409
410 <th>Expression</th>
411
412 <th>Return type</th>
413
414 <th>Semantics</th>
415 </tr>
416
417 <tr>
418 <td valign="top">Beginning of range</td>
419
420 <td valign="top"><tt>a.rbegin()</tt></td>
421
422 <td valign="top"><tt>reverse_iterator</tt> if <tt>a</tt> is mutable,
423 <tt>const_reverse_iterator</tt> otherwise.</td>
424
425 <td valign="top">Equivalent to
426 <tt>X::reverse_iterator(a.end())</tt>.</td>
427 </tr>
428
429 <tr>
430 <td valign="top">End of range</td>
431
432 <td valign="top"><tt>a.rend()</tt></td>
433
434 <td valign="top"><tt>reverse_iterator</tt> if <tt>a</tt> is mutable,
435 <tt>const_reverse_iterator</tt> otherwise.</td>
436
437 <td valign="top">Equivalent to
438 <tt>X::reverse_iterator(a.begin())</tt>.</td>
439 </tr>
440
441 <tr>
442 <td valign="top">Back</td>
443
444 <td valign="top"><tt>a.back()</tt></td>
445
446 <td valign="top"><tt>reference</tt> if <tt>a</tt> is mutable,<br>
447 <tt>const_reference</tt> otherwise.</td>
448
449 <td valign="top">Equivalent to <tt>*(--a.end())</tt>.</td>
450 </tr>
451 </table>
452
453 <h4>SequentialCollection</h4>
454
455 <p>The elements are arranged in a strict linear order. No extra methods are
456 required.</p>
457
458 <h4>RandomAccessCollection</h4>
459
460 <p>The iterators of a RandomAccessCollection satisfy all of the
461 requirements of <a href=
462 "http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>
463 except that the reference type does not have to be a real C++ reference. In
464 addition, a RandomAccessCollection provides an element access operator.</p>
465
466 <table border summary="">
467 <tr>
468 <th>Name</th>
469
470 <th>Expression</th>
471
472 <th>Return type</th>
473
474 <th>Semantics</th>
475 </tr>
476
477 <tr>
478 <td valign="top">Element Access</td>
479
480 <td valign="top"><tt>a[n]</tt></td>
481
482 <td valign="top"><tt>reference</tt> if <tt>a</tt> is mutable,
483 <tt>const_reference</tt> otherwise.</td>
484
485 <td valign="top">Returns the nth element of the Collection. <tt>n</tt>
486 must be convertible to <tt>size_type</tt>. Precondition: <tt>0 &lt;= n
487 &lt; a.size()</tt>.</td>
488 </tr>
489 </table>
490
491 <h3>Notes</h3>
492
493 <p><a name="n1" id="n1">[1]</a> The reference type does not have to be a
494 real C++ reference. The requirements of the reference type depend on the
495 context within which the Collection is being used. Specifically it depends
496 on the requirements the context places on the value type of the Collection.
497 The reference type of the Collection must meet the same requirements as the
498 value type. In addition, the reference objects must be equivalent to the
499 value type objects in the collection (which is trivially true if they are
500 the same object). Also, in a mutable Collection, an assignment to the
501 reference object must result in an assignment to the object in the
502 Collection (again, which is trivially true if they are the same object, but
503 non-trivial if the reference type is a proxy class).</p>
504
505 <h3>See also</h3>
506
507 <p><a href=
508 "http://www.sgi.com/tech/stl/Container.html">Container</a><br></p>
509 <hr>
510
511 <p><a href="http://validator.w3.org/check?uri=referer"><img border="0" src=
512 "../../doc/images/valid-html401.png" alt="Valid HTML 4.01 Transitional"
513 height="31" width="88"></a></p>
514
515 <p>Revised
516 <!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %B, %Y" startspan -->05
517 December, 2006<!--webbot bot="Timestamp" endspan i-checksum="38516" --></p>
518
519 <table summary="">
520 <tr valign="top">
521 <td nowrap><i>Copyright &copy; 2000</i></td>
522
523 <td><i><a href="http://www.boost.org/people/jeremy_siek.htm">Jeremy
524 Siek</a>, Univ.of Notre Dame and C++ Library &amp; Compiler Group/SGI
525 (<a href="mailto:jsiek@engr.sgi.com">jsiek@engr.sgi.com</a>)</i></td>
526 </tr>
527 </table>
528
529 <p><i>Distributed under the Boost Software License, Version 1.0. (See
530 accompanying file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or
531 copy at <a href=
532 "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)</i></p>
533</body>
534</html>