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() >= 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 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() >= 0 && a.max_size() >= 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"> </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"> </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<bool></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 <= n 487 < 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 © 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 & 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> 535
