1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"><html><head><!-- saved from url=(0022)http://internet.e-mail --><title>Improved Iterator Categories and Requirements</title> 2<meta content="text/html; charset=windows-1252" http-equiv="Content-Type"> 3<meta content="Microsoft FrontPage 5.0" name="GENERATOR"></head> 4<body bgcolor="#ffffff"> 5<p align="right"> 6<table border="0"> 7 <tbody> 8 <tr> 9 <td width="125"> 10 <p align="right">Document number: </p></td> 11 <td width="190"> 12 <p>J16/01-0011 = WG21 N1297 </p></td></tr> 13 <tr> 14 <td width="125"> 15 <p align="right">Date: </p></td> 16 <td width="190"> 17 <p>March 21, 2001 </p></td></tr> 18 <tr> 19 <td width="125"> 20 <p align="right">Author: </p></td> 21 <td width="190"> 22 <p>Jeremy Siek, <br>University of Notre Dame </p></td></tr> 23 <tr> 24 <td width="125"> 25 <p></p></td> 26 <td width="190"> 27 <p><a href="mailto:jsiek@lsc.nd.edu">jsiek@lsc.nd.edu</a> 28 </p></td></tr></tbody></table></p> 29<h1> 30<center>Improved Iterator Categories and Requirements</center></h1> 31<h2>Introduction</h2>The standard iterator categories and requirements are 32flawed because they use a single hierarchy of requirements to address two 33orthogonal issues: <b><i>iterator traversal</i></b> and <b><i>dereference return 34type</i></b>. The current iterator requirement hierarchy is mainly geared 35towards iterator traversal (hence the category names), while requirements that 36address dereference return type sneak in at various places. The following table 37gives a summary of the current dereference return type requirements in the 38iterator categories. 39<p> 40</p><center> 41<a name="table:1"> 42 <b>Table 1.</b> Summary of current dereference return type 43 requirements.</a><table border="1"> 44 <tbody> 45 <tr> 46 <td>Output Iterator</td> 47 <td><tt>*i = a</tt> </td></tr> 48 <tr> 49 <td>Input Iterator</td> 50 <td><tt>*i</tt> is convertible to <tt>T</tt></td></tr> 51 <tr> 52 <td>Forward Iterator</td> 53 <td><tt>*i</tt> is <tt>T&</tt> (or <tt>const T&</tt> once <a href="http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#200">issue 54 200</a> is resolved)</td></tr> 55 <tr> 56 <td>Random Access Iterator</td> 57 <td><tt>i[n]</tt> is convertible to <tt>T</tt> (which is odd because the 58 operational semantics say <tt>i[n]</tt> is equivalent to <tt>*(i + n)</tt> 59 which would have a return type of <tt>T&</tt>) </td></tr></tbody></table></center> 60<h2>Examples of useful iterators that do not ``fit''</h2> 61<p>Because of the mixing of iterator traversal and dereference return type, many 62useful iterators can not be appropriately categorized. For example, 63<tt>vector<bool>::iterator</tt> is almost a random access iterator, but 64the return type is not <tt>bool&</tt> (see <a href="http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#96">issue 6596</a> and Herb Sutter's paper J16/99-0008 = WG21 N1185). Therefore, the 66iterators only meet the requirements of input iterator and output iterator. This 67is so nonintuitive that at least one implementation erroneously assigns 68<tt>random_access_iterator_tag</tt> as its <tt>iterator_category</tt>. Also, 69<tt>vector<bool></tt> is not the only example of useful iterators that do 70not return true references: there is the often cited example of disk-based 71collections. 72</p><p>Another example is a counting iterator, an iterator the returns a sequence of 73integers when incremented and dereferenced (see <a href="http://www.boost.org/libs/iterator/doc/counting_iterator.html"><tt>boost::counting_iterator</tt></a>). 74There are two ways to implement this iterator, 1) make the <tt>reference</tt> 75type be a true reference (a reference to an integer data member of the counting 76iterator) or 2) make the <tt>reference</tt> type be the same as the 77<tt>value_type</tt>. Option 1) runs into the problems discussed in <a href="http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#198">Issue 78198</a>, the reference will not be valid after the iterator is destroyed. Option 792) is therefore a better choice, but then we have a counting iterator that 80cannot be a random access iterator. 81</p><p>Yet another example is a transform iterator, an iterator adaptor that applies 82a unary function object to the dereference value of the wrapped iterator (see <a href="http://www.boost.org/libs/iterator/doc/transform_iterator.html"><tt>boost::transform_iterator</tt></a>). 83For unary functions such as <tt>std::times</tt> the return type of 84<tt>operator*</tt> clearly needs to be the <tt>result_type</tt> of the function 85object, which is typically not a reference. However, with the current iterator 86requirements, if you wrap <tt>int*</tt> with a transform iterator, you do not 87get a random access iterator as expected, but an input iterator. 88</p><p>A fourth example is found in the vertex and edge iterators of the <a href="http://www.boost.org/libs/graph/doc/table_of_contents.html">Boost Graph 89Library</a>. These iterators return vertex and edge descriptors, which are 90lightweight handles created on-the-fly. They must be returned by-value. As a 91result, their current standard iterator category is 92<tt>std::input_iterator_tag</tt>, which means that, strictly speaking, you could 93not use these iterators with algorithms like <tt>std::min_element()</tt>. As a 94temporary solution, we introduced the concept <a href="http://www.boost.org/libs/utility/MultiPassInputIterator.html">Multi-Pass 95Input Iterator</a> to describe the vertex and edge descriptors, but as the 96design notes for concept suggest, a better solution is needed. 97</p><p>In short, there are many useful iterators that do not fit into the current 98standard iterator categories. As a result, the following bad things happen: 99</p><ul> 100 <li>Iterators are often miss-categorized. 101 </li><li>Algorithm requirements are more strict than necessary, because they can 102 not separate out the need for random-access from the need for a true reference 103 return type. </li></ul> 104<h2>Proposal for new iterator categories and requirements</h2>The iterator 105requirements should be separated into two hierarchies. One set of concepts 106handles the return type semantics: 107<ul> 108 <li><a href="#concept_ReadableIterator">Readable 109 Iterator</a> 110 </li><li><a href="#concept_WritableIterator">Writable 111 Iterator</a> 112 </li><li><a href="#concept_SwappableIterator">Swappable 113 Iterator</a> 114 </li><li><a href="#concept_ConstantLvalueIterator">Constant 115 Lvalue Iterator</a> 116 </li><li><a href="#concept_MutableLvalueIterator">Mutable 117 Lvalue Iterator</a> </li></ul>The other set of concepts handles iterator 118traversal: 119<ul> 120 <li><a href="#concept_ForwardTraversalIterator">Forward 121 Traversal Iterator</a> 122 </li><li><a href="#concept_BidirectionalTraversalIterator">Bidirectional 123 Traversal Iterator</a> 124 </li><li><a href="#concept_RandomAccessTraversalIterator">Random 125 Access Traversal Iterator</a> </li></ul>The current Input Iterator and Output 126Iterator requirements will continue to be used as is. Note that Input Iterator 127implies Readable Iterator and Output Iterator implies Writable Iterator. 128<p>Note: we considered defining a Single-Pass Iterator, which could be combined 129with Readable or Writable Iterator to replace the Input and Output Iterator 130requirements. We rejected this idea because there are several differences 131between Input and Output Iterators that make it hard to merge them: Input 132Iterator requires Equality Comparable while Output Iterator does not and Input 133Iterator requires Assignable while Output Iterator does not. 134</p><h3>New categories and traits classes</h3>Each of the new iterator requirements 135will need a category tag. <pre>namespace std { 136 137 // Return Type Categories 138 struct readable_iterator_tag { }; 139 struct writable_iterator_tag { }; 140 struct swappable_iterator_tag { }; 141 struct mutable_lvalue_iterator_tag : virtual public writable_iterator_tag, 142 virtual public readable_iterator_tag { }; 143 struct constant_lvalue_iterator_tag : public readable_iterator_tag { }; 144 145 // Traversal Categories 146 struct forward_traversal_tag { }; 147 struct bidirectional_traversal_tag : public forward_traversal_tag { }; 148 struct random_access_traversal_tag : public bidirectional_traversal_tag { }; 149 150} 151</pre>And there will need to be a way to access these category tags using a 152traits mechanism. Adding new typedefs to <tt>std::iterator_traits</tt> is not an 153acceptable solution because that would break every existing iterator. Instead, 154we propose two new traits classes. It is important that these traits classes are 155<b>backward compatible</b>, that is, they should work with any iterator for 156which there is a valid definition of <tt>std::iterator_traits</tt>. This can be 157accomplished by making the default behavior of the traits classes map the 158<tt>iterator_category</tt> of the iterator to the appropriate return or 159traversal category. For new iterators, either specializations of these traits 160classes can be defined, or the iterator can provide nested typedefs, and inherit 161from <tt>new_iterator_base</tt> (which is just a signal to the traits class that 162it is a new iterator). As with <tt>std::iterator_traits</tt>, specializations 163for <tt>T*</tt> are provided. <pre>namespace std { 164 165 struct new_iterator_base { }; 166 167 template <typename Iterator> 168 struct return_category 169 { 170 <b><i>// Pseudo-code</i></b> 171 if (Iterator inherits from new_iterator_base) { 172 typedef typename Iterator::return_category type; 173 } else { 174 typedef std::iterator_traits<Iterator> OldTraits; 175 typedef typename OldTraits::iterator_category Cat; 176 if (Cat inherits from std::forward_iterator_tag) 177 if (is-const(T)) 178 typedef boost::constant_lvalue_iterator_tag type; 179 else 180 typedef boost::mutable_lvalue_iterator_tag type; 181 else if (Cat inherits from std::input_iterator_tag) 182 typedef boost::readable_iterator_tag type; 183 else if (Cat inherits from std::output_iterator_tag) 184 typedef boost::writable_iterator_tag type; 185 } 186 }; 187 188 template <typename T> 189 struct return_category<T*> 190 { 191 <b><i>// Pseudo-code</i></b> 192 if (is-const(T)) 193 typedef boost::constant_lvalue_iterator_tag type; 194 else 195 typedef boost::mutable_lvalue_iterator_tag type; 196 }; 197 198 template <typename Iterator> 199 struct traversal_category 200 { 201 <b><i>// Pseudo-code</i></b> 202 if (Iterator inherits from new_iterator_base) { 203 typedef typename Iterator::traversal_category type; 204 } else { 205 typedef std::iterator_traits<Iterator> OldTraits; 206 typedef typename OldTraits::iterator_category Cat; 207 208 if (Cat inherits from std::random_access_iterator_tag) 209 typedef boost::random_access_traversal_tag type; 210 else if (Cat inherits from std::bidirectional_iterator_tag) 211 typedef boost::bidirectional_traversal_tag type; 212 else if (Cat inherits from std::forward_iterator_tag) 213 typedef boost::forward_traversal_tag type; 214 } 215 }; 216 217 template <typename T> 218 struct traversal_category<T*> 219 { 220 typedef boost::random_access_traversal_tag type; 221 }; 222 223} 224</pre> 225<h2>Impact on the Standard Algorithms</h2>Many of the standard algorithms place 226more requirements than necessary on their iterator parameters due to the 227coarseness of the current iterator categories. By using the new iterator 228categories a better fit can be achieved, thereby increasing the reusability of 229the algorithms. These changes will not affect user-code, though they will 230require changes by standard implementers: dispatching should be based on the new 231categories, and in places return values may need to be handled more carefully. 232In particular, uses of <tt>std::swap()</tt> will need to be replaced with 233<tt>std::iter_swap()</tt>, and <tt>std::iter_swap()</tt> will need to call 234<tt>std::swap()</tt>. 235<p> 236</p><center> 237<a name="table:2"> 238 <b>Table 2.</b> Requirement changes for standard 239 algorithms.</a><table border="1"> 240 <tbody> 241 <tr> 242 <th>Algorithm</th> 243 <th>Requirement Change</th></tr> 244 <tr> 245 <td>find_end</td> 246 <td rowspan="12">Forward Iterator<br>-> Forward Traversal Iterator and 247 Readable Iterator </td></tr> 248 <tr> 249 <td>find_first_of</td></tr> 250 <tr> 251 <td>adjacent_find</td></tr> 252 <tr> 253 <td>search</td></tr> 254 <tr> 255 <td>search_n</td></tr> 256 <tr> 257 <td>rotate_copy</td></tr> 258 <tr> 259 <td>lower_bound</td></tr> 260 <tr> 261 <td>upper_bound</td></tr> 262 <tr> 263 <td>equal_range</td></tr> 264 <tr> 265 <td>binary_search</td></tr> 266 <tr> 267 <td>min_element</td></tr> 268 <tr> 269 <td>max_element</td></tr> 270 <tr> 271 <td>iter_swap</td> 272 <td>Forward Iterator<br>-> Swappable Iterator </td></tr> 273 <tr> 274 <td>fill</td> 275 <td rowspan="2">Forward Iterator<br>-> Forward Traversal Iterator and 276 Writable Iterator </td></tr> 277 <tr> 278 <td>generate</td></tr> 279 <tr> 280 <td>swap_ranges</td> 281 <td rowspan="2">Forward Iterator<br>-> Forward Traversal Iterator and 282 Swappable Iterator </td></tr> 283 <tr> 284 <td>rotate</td></tr> 285 <tr> 286 <td>replace</td> 287 <td rowspan="5">Forward Iterator<br>-> Forward Traversal Iterator 288 and<br>Readable Iterator and Writable Iterator </td> 289 </tr><tr> 290 <td>replace_if</td></tr> 291 <tr> 292 <td>remove</td></tr> 293 <tr> 294 <td>remove_if</td></tr> 295 <tr> 296 <td>unique</td></tr> 297 <tr> 298 <td>reverse</td> 299 <td rowspan="2">Bidirectional Iterator<br>-> Bidirectional Traversal 300 Iterator and Swappable Iterator </td></tr> 301 <tr> 302 <td>partition</td></tr> 303 <tr> 304 <td>copy_backwards</td> 305 <td>Bidirectional Iterator<br>-> Bidirectional Traversal Iterator and 306 Readable Iterator<br>Bidirectional Iterator<br>-> Bidirectional 307 Traversal Iterator and Writable Iterator </td></tr> 308 <tr> 309 <td>next_permutation</td> 310 <td rowspan="2">Bidirectional Iterator<br>-> Bidirectional Traversal 311 Iterator and <br>Swappable Iterator and Readable Iterator </td> 312 </tr><tr> 313 <td>prev_permutation</td></tr> 314 <tr> 315 <td>stable_partition</td> 316 <td rowspan="2">Bidirectional Iterator<br>-> Bidirectional Traversal 317 Iterator and <br>Readable Iterator and Writable Iterator </td> 318 </tr><tr> 319 <td>inplace_merge</td></tr> 320 <tr> 321 <td>reverse_copy</td> 322 <td>Bidirectional Iterator<br>-> Bidirectional Traversal Iterator and 323 Readable Iterator </td></tr> 324 <tr> 325 <td>random_shuffle</td> 326 <td rowspan="9">Random Access Iterator<br>-> Random Access Traversal 327 Iterator and Swappable Iterator </td></tr> 328 <tr> 329 <td>sort</td></tr> 330 <tr> 331 <td>stable_sort</td></tr> 332 <tr> 333 <td>partial_sort</td></tr> 334 <tr> 335 <td>nth_element</td></tr> 336 <tr> 337 <td>push_heap</td></tr> 338 <tr> 339 <td>pop_heap</td></tr> 340 <tr> 341 <td>make_heap</td></tr> 342 <tr> 343 <td>sort_heap</td></tr></tbody></table></center> 344<h2>The New Iterator Requirements</h2> 345<h3>Notation</h3> 346<table> 347 <tbody> 348 <tr> 349 <td><tt>X</tt></td> 350 <td>The iterator type.</td></tr> 351 <tr> 352 <td><tt>T</tt></td> 353 <td>The value type of <tt>X</tt>, i.e., 354 <tt>std::iterator_traits<X>::value_type</tt>.</td></tr> 355 <tr> 356 <td><tt>x</tt>, <tt>y</tt></td> 357 <td>An object of type <tt>X</tt>.</td></tr> 358 <tr> 359 <td><tt>t</tt></td> 360 <td>An object of type <tt>T</tt>.</td></tr></tbody></table> 361<p> 362</p><hr> 363<!---------------------------------------------------------------------------> 364<h3><a name="concept_ReadableIterator"></a>Readable Iterator </h3>A Readable 365Iterator is an iterator that dereferences to produce an rvalue that is 366convertible to the <tt>value_type</tt> of the iterator. 367<h3>Associated Types</h3> 368<table border="1"> 369 <tbody> 370 <tr> 371 <td>Value type</td> 372 <td><tt>std::iterator_traits<X>::value_type</tt></td> 373 <td>The type of the objects pointed to by the iterator.</td></tr> 374 <tr> 375 <td>Reference type</td> 376 <td><tt>std::iterator_traits<X>::reference</tt></td> 377 <td>The return type of dereferencing the iterator. This type must be 378 convertible to <tt>T</tt>. </td></tr> 379 <tr> 380 <td>Return Category</td> 381 <td><tt>std::return_category<X>::type</tt></td> 382 <td>A type convertible to <tt>std::readable_iterator_tag</tt> 383 </td></tr></tbody></table> 384<h3>Refinement of</h3><a href="http://www.boost.org/libs/utility/CopyConstructible.html">Copy 385Constructible</a> 386<h3>Valid expressions</h3> 387<table border="1"> 388 <tbody> 389 <tr> 390 <th>Name</th> 391 <th>Expression</th> 392 <th>Type requirements</th> 393 <th>Return type</th></tr> 394 <tr> 395 <td>Dereference</td> 396 <td><tt>*x</tt></td> 397 <td>�</td> 398 <td><tt>std::iterator_traits<X>::reference</tt></td></tr> 399 <tr> 400 <td>Member access</td> 401 <td><tt>x->m</tt></td> 402 <td><tt>T</tt> is a type with a member named <tt>m</tt>.</td> 403 <td>If <tt>m</tt> is a data member, the type of <tt>m</tt>. If <tt>m</tt> 404 is a member function, the return type of <tt>m</tt>. </td></tr></tbody></table> 405<p> 406</p><hr> 407<!---------------------------------------------------------------------------> 408<h3><a name="concept_WritableIterator"></a>Writable Iterator </h3>A Writable 409Iterator is an iterator that can be used to store a value using the 410dereference-assignment expression. 411<h3>Definitions</h3>If <tt>x</tt> is an Writable Iterator of type <tt>X</tt>, 412then the expression <tt>*x = a;</tt> stores the value <tt>a</tt> into 413<tt>x</tt>. Note that <tt>operator=</tt>, like other C++ functions, may be 414overloaded; it may, in fact, even be a template function. In general, then, 415<tt>a</tt> may be any of several different types. A type <tt>A</tt> belongs to 416the <i>set of value types</i> of <tt>X</tt> if, for an object <tt>a</tt> of type 417<tt>A</tt>, <tt>*x = a;</tt> is well-defined and does not require performing any 418non-trivial conversions on <tt>a</tt>. 419<h3>Associated Types</h3> 420<table border="1"> 421 <tbody> 422 <tr> 423 <td>Return Category</td> 424 <td><tt>std::return_category<X>::type</tt></td> 425 <td>A type convertible to <tt>std::writable_iterator_tag</tt> 426 </td></tr></tbody></table> 427<h3>Refinement of</h3><a href="http://www.boost.org/libs/utility/CopyConstructible.html">Copy 428Constructible</a> 429<h3>Valid expressions</h3> 430<table border="1"> 431 <tbody> 432 <tr> 433 <th>Name</th> 434 <th>Expression</th> 435 <th>Return type</th></tr> 436 <tr> 437 <td>Dereference assignment</td> 438 <td><tt>*x = a</tt></td> 439 <td>unspecified</td></tr></tbody></table> 440<p> 441</p><hr> 442<!---------------------------------------------------------------------------> 443<h3><a name="concept_SwappableIterator"></a>Swappable Iterator </h3>A Swappable 444Iterator is an iterator whose dereferenced values can be swapped. 445<p>Note: the requirements for Swappable Iterator are dependent on the issues 446surrounding <tt>std::swap()</tt> being resolved. Here we assume that the issue 447will be resolved by allowing the overload of <tt>std::swap()</tt> for 448user-defined types. 449</p><p>Note: Readable Iterator and Writable Iterator combined implies Swappable 450Iterator because of the fully templated <tt>std::swap()</tt>. However, Swappable 451Iterator does not imply Readable Iterator nor Writable Iterator. 452</p><h3>Associated Types</h3> 453<table border="1"> 454 <tbody> 455 <tr> 456 <td>Return Category</td> 457 <td><tt>std::return_category<X>::type</tt></td> 458 <td>A type convertible to <tt>std::swappable_iterator_tag</tt> 459 </td></tr></tbody></table> 460<h3>Valid expressions</h3>Of the two valid expressions listed below, only one 461<b>OR</b> the other is required. If <tt>std::iter_swap()</tt> is overloaded for 462<tt>X</tt> then <tt>std::swap()</tt> is not required. If 463<tt>std::iter_swap()</tt> is not overloaded for <tt>X</tt> then the default 464(fully templated) version is used, which will call <tt>std::swap()</tt> (this 465means changing the current requirements for <tt>std::iter_swap()</tt>). 466<p> 467<table border="1"> 468 <tbody> 469 <tr> 470 <th>Name</th> 471 <th>Expression</th> 472 <th>Return type</th></tr> 473 <tr> 474 <td>Iterator Swap</td> 475 <td><tt>std::iter_swap(x, y)</tt></td> 476 <td>void</td></tr> 477 <tr> 478 <td>Dereference and Swap</td> 479 <td><tt>std::swap(*x, *y)</tt></td> 480 <td>void</td></tr></tbody></table> 481</p><p> 482</p><hr> 483<!---------------------------------------------------------------------------> 484<h3><a name="concept_ConstantLvalueIterator"></a>Constant Lvalue Iterator </h3>A 485Constant Lvalue Iterator is an iterator that dereferences to produce a const 486reference to the pointed-to object, i.e., the associated <tt>reference</tt> type 487is <tt>const T&</tt>. Changing the value of or destroying an iterator that 488models Constant Lvalue Iterator does not invalidate pointers and references 489previously obtained from that iterator. 490<h3>Refinement of</h3><a href="#concept_ReadableIterator">Readable 491Iterator</a> 492<h3>Associated Types</h3> 493<table border="1"> 494 <tbody> 495 <tr> 496 <td>Reference type</td> 497 <td><tt>std::iterator_traits<X>::reference</tt></td> 498 <td>The return type of dereferencing the iterator, which must be <tt>const 499 T&</tt>. </td></tr><!-- I don't think this is needed 500 501 <tr> 502 503 <td>Pointer type</td> 504 505 <td><tt>std::iterator_traits<X>::pointer</tt></td> 506 507 <td> 508 509 The pointer to the value type, which must be <tt>const T*</tt>. 510 511 </td> 512 513 </tr> 514 515--> 516 <tr> 517 <td>Return Category</td> 518 <td><tt>std::return_category<X>::type</tt></td> 519 <td>A type convertible to <tt>std::constant_lvalue_iterator_tag</tt> 520 </td></tr></tbody></table><!-- these are not necessary now that we use reference as operator* return type 521 522<h3>Valid expressions</h3> 523 524 525 526<Table border> 527 528<tr><TH>Name</TH><TH>Expression</TH><TH>Type requirements</TH><TH>Return type</TH></tr> 529 530<tr> 531 532 <td>Dereference</td> 533 534 <td><tt>*x</tt></td> 535 536 <td> </td> 537 538 <td><tt>std::iterator_traits<X>::reference</tt></td> 539 540</tr> 541 542<tr> 543 544 <td>Member access</td> 545 546 <td><tt>x->m</tt></td> 547 548 <td><tt>T</tt> is a type with a member named <tt>m</tt>.</td> 549 550 <td> 551 552 553 554 </td> 555 556</tr> 557 558</table> 559 560 561 562--> 563<p> 564</p><hr> 565<!---------------------------------------------------------------------------> 566<h3><a name="concept_MutableLvalueIterator"></a>Mutable Lvalue Iterator </h3>A 567Mutable Lvalue Iterator is an iterator that dereferences to produce a reference 568to the pointed-to object. The associated <tt>reference</tt> type is 569<tt>T&</tt>. Changing the value of or destroying an iterator that models 570Mutable Lvalue Iterator does not invalidate pointers and references previously 571obtained from that iterator. 572<h3>Refinement of</h3><a href="#concept_ReadableIterator">Readable 573Iterator</a>, <a href="#concept_WritableIterator">Writable 574Iterator</a>, and <a href="#concept_SwappableIterator">Swappable 575Iterator</a>. 576<h3>Associated Types</h3> 577<table border="1"> 578 <tbody> 579 <tr> 580 <td>Reference type</td> 581 <td><tt>std::iterator_traits<X>::reference</tt></td> 582 <td>The return type of dereferencing the iterator, which must be 583 <tt>T&</tt>.</td></tr><!-- I don't think this is necessary 584 585 <tr> 586 587 <td>Pointer type</td> 588 589 <td><tt>std::iterator_traits<X>::pointer</tt></td> 590 591 <td> 592 593 The pointer to the value type, which is <tt>T*</tt>. 594 595 </td> 596 597 </tr> 598 599--> 600 <tr> 601 <td>Return Category</td> 602 <td><tt>std::return_category<X>::type</tt></td> 603 <td>A type convertible to <tt>std::mutable_lvalue_iterator_tag</tt> 604 </td></tr></tbody></table><!-- no longer needed since the return type is specified as reference in the readable iterator 605 606<h3>Valid expressions</h3> 607 608 609 610<Table border> 611 612<tr><TH>Name</TH><TH>Expression</TH><TH>Type requirements</TH><TH>Return type</TH></tr> 613 614<tr> 615 616 <td>Dereference</td> 617 618 <td><tt>*x</tt></td> 619 620 <td> </td> 621 622 <td><tt>std::iterator_traits<X>::reference</tt></td> 623 624</tr> 625 626<tr> 627 628 <td>Member access</td> 629 630 <td><tt>x->m</tt></td> 631 632 <td><tt>T</tt> is a type with a member named <tt>m</tt>.</td> 633 634 <td> 635 636 637 638 </td> 639 640</tr> 641 642</table> 643 644 645 646--> 647<p> 648</p><hr> 649<!---------------------------------------------------------------------------> 650<h3><a name="concept_ForwardTraversalIterator"></a>Forward Traversal Iterator 651</h3>The Forward Iterator is an iterator that can be incremented. Also, it is 652permissible to make multiple passes through the iterator's range. 653<h3>Refinement of</h3><a href="http://www.boost.org/libs/utility/CopyConstructible.html">Copy 654Constructible</a>, <a href="http://www.boost.org/libs/utility/Assignable.html">Assignable</a>, <a href="https://www.boost.org/sgi/stl/DefaultConstructible.html">Default 655Constructible</a>, and <a href="https://www.boost.org/sgi/stl/EqualityComparable.html">Equality 656Comparable</a> 657<h3>Associated types</h3> 658<table border="1"> 659 <tbody> 660 <tr> 661 <td>Difference Type</td> 662 <td><tt>std::iterator_traits<X>::difference_type</tt></td> 663 <td>A signed integral type used for representing distances between 664 iterators that point into the same range. </td></tr> 665 <tr> 666 <td>Traversal Category</td> 667 <td><tt>std::traversal_category<X>::type</tt></td> 668 <td>A type convertible to <tt>std::forward_traversal_tag</tt> 669 </td></tr></tbody></table> 670<h3>Valid expressions</h3> 671<table border="1"> 672 <tbody> 673 <tr> 674 <th>Name</th> 675 <th>Expression</th> 676 <th>Type requirements</th> 677 <th>Return type</th></tr> 678 <tr> 679 <td>Preincrement</td> 680 <td><tt>++i</tt></td> 681 <td>�</td> 682 <td><tt>X&</tt></td></tr> 683 <tr> 684 <td>Postincrement</td> 685 <td><tt>i++</tt></td> 686 <td>�</td> 687 <td>convertible to <tt>const X&</tt></td></tr></tbody></table> 688<p> 689</p><hr> 690<!---------------------------------------------------------------------------> 691<h3><a name="concept_BidirectionalTraversalIterator"></a>Bidirectional Traversal 692Iterator </h3>An iterator that can be incremented and decremented. 693<h3>Refinement of</h3><a href="#concept_ForwardTraversalIterator">Forward 694Traversal Iterator</a> 695<h3>Associated types</h3> 696<table border="1"> 697 <tbody> 698 <tr> 699 <td>Traversal Category</td> 700 <td><tt>std::traversal_category<X>::type</tt></td> 701 <td>A type convertible to <tt>std::bidirectional_traversal_tag</tt> 702 </td></tr></tbody></table> 703<h3>Valid expressions</h3> 704<table border="1"> 705 <tbody> 706 <tr> 707 <th>Name</th> 708 <th>Expression</th> 709 <th>Type requirements</th> 710 <th>Return type</th></tr> 711 <tr> 712 <td>Predecrement</td> 713 <td><tt>--i</tt></td> 714 <td>�</td> 715 <td><tt>X&</tt></td></tr> 716 <tr> 717 <td>Postdecrement</td> 718 <td><tt>i--</tt></td> 719 <td>�</td> 720 <td>convertible to <tt>const X&</tt></td></tr></tbody></table> 721<p> 722</p><hr> 723<!---------------------------------------------------------------------------> 724<h3><a name="concept_RandomAccessTraversalIterator"></a>Random Access Traversal 725Iterator </h3>An iterator that provides constant-time methods for moving forward 726and backward in arbitrary-sized steps. 727<h3>Refinement of</h3><a href="#concept_BidirectionalTraversalIterator">Bidirectional 728Traversal Iterator</a> and <a href="https://www.boost.org/sgi/stl/LessThanComparable.html">Less Than 729Comparable</a> where <tt><</tt> is a total ordering 730<h3>Associated types</h3> 731<table border="1"> 732 <tbody> 733 <tr> 734 <td>Traversal Category</td> 735 <td><tt>std::traversal_category<X>::type</tt></td> 736 <td>A type convertible to <tt>std::random_access_traversal_tag</tt> 737 </td></tr></tbody></table> 738<h3>Valid expressions</h3> 739<table border="1"> 740 <tbody> 741 <tr> 742 <th>Name</th> 743 <th>Expression</th> 744 <th>Type requirements</th> 745 <th>Return type</th></tr> 746 <tr> 747 <td>Iterator addition</td> 748 <td><tt>i += n</tt></td> 749 <td>�</td> 750 <td><tt>X&</tt></td></tr> 751 <tr> 752 <td>Iterator addition</td> 753 <td><tt>i + n</tt> or <tt>n + i</tt></td> 754 <td>�</td> 755 <td><tt>X</tt></td></tr> 756 <tr> 757 <td>Iterator subtraction</td> 758 <td><tt>i -= n</tt></td> 759 <td>�</td> 760 <td><tt>X&</tt></td></tr> 761 <tr> 762 <td>Iterator subtraction</td> 763 <td><tt>i - n</tt></td> 764 <td>�</td> 765 <td><tt>X</tt></td></tr> 766 <tr> 767 <td>Difference</td> 768 <td><tt>i - j</tt></td> 769 <td>�</td> 770 <td><tt>std::iterator_traits<X>::difference_type</tt></td></tr> 771 <tr> 772 <td>Element operator</td> 773 <td><tt>i[n]</tt></td> 774 <td><tt>X</tt> must also be a model of <a href="#concept_ReadableIterator">Readable 775 Iterator</a>. </td> 776 <td><tt>std::iterator_traits<X>::reference</tt></td></tr> 777 <tr> 778 <td>Element assignment</td> 779 <td><tt>i[n] = t</tt></td> 780 <td><tt>X</tt> must also be a model of <a href="#concept_WritableIterator">Writable 781 Iterator</a>.</td> 782 <td>unspecified</td></tr></tbody></table> 783<p> 784</p><hr> 785<!-- LocalWords: HTML BGCOLOR FFFFFF TR TD Siek HREF mailto jsiek 786 787 --><!-- LocalWords: lsc edu tt const href http anubis dkuug dk JTC SC WG docs lt 788 789 --><!-- LocalWords: lwg html bool gt Sutter's htm Lvalue namespace std struct 790 791 --><!-- LocalWords: lvalue typename OldTraits reusability min iter prev inplace 792 793 --><!-- LocalWords: rvalue templated Preincrement Postincrement Predecrement 794 795 --><!-- LocalWords: Postdecrement 796 797 --></body></html> 798