libs/multi_array/doc/iterator_categories.html

   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
  32 flawed because they use a single hierarchy of requirements to address two
  33 orthogonal issues: <b><i>iterator traversal</i></b> and <b><i>dereference return
  34 type</i></b>. The current iterator requirement hierarchy is mainly geared
  35 towards iterator traversal (hence the category names), while requirements that
  36 address dereference return type sneak in at various places. The following table
  37 gives a summary of the current dereference return type requirements in the
  38 iterator 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&amp;</tt> (or <tt>const T&amp;</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&amp;</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
  62 useful iterators can not be appropriately categorized. For example,
  63 <tt>vector&lt;bool&gt;::iterator</tt> is almost a random access iterator, but
  64 the return type is not <tt>bool&amp;</tt> (see <a href="http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#96">issue
  65 96</a> and Herb Sutter's paper J16/99-0008 = WG21 N1185). Therefore, the
  66 iterators only meet the requirements of input iterator and output iterator. This
  67 is 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&lt;bool&gt;</tt> is not the only example of useful iterators that do
  70 not return true references: there is the often cited example of disk-based
  71 collections.
  72 </p><p>Another example is a counting iterator, an iterator the returns a sequence of
  73 integers when incremented and dereferenced (see <a href="http://www.boost.org/libs/iterator/doc/counting_iterator.html"><tt>boost::counting_iterator</tt></a>).
  74 There are two ways to implement this iterator, 1) make the <tt>reference</tt>
  75 type be a true reference (a reference to an integer data member of the counting
  76 iterator) 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
  78 198</a>, the reference will not be valid after the iterator is destroyed. Option
  79 2) is therefore a better choice, but then we have a counting iterator that
  80 cannot be a random access iterator.
  81 </p><p>Yet another example is a transform iterator, an iterator adaptor that applies
  82 a 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>).
  83 For 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
  85 object, which is typically not a reference. However, with the current iterator
  86 requirements, if you wrap <tt>int*</tt> with a transform iterator, you do not
  87 get 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
  89 Library</a>. These iterators return vertex and edge descriptors, which are
  90 lightweight handles created on-the-fly. They must be returned by-value. As a
  91 result, their current standard iterator category is
  92 <tt>std::input_iterator_tag</tt>, which means that, strictly speaking, you could
  93 not use these iterators with algorithms like <tt>std::min_element()</tt>. As a
  94 temporary solution, we introduced the concept <a href="http://www.boost.org/libs/utility/MultiPassInputIterator.html">Multi-Pass
  95 Input Iterator</a> to describe the vertex and edge descriptors, but as the
  96 design 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
  98 standard 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
 105 requirements should be separated into two hierarchies. One set of concepts
 106 handles 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
 118 traversal:
 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
 126 Iterator requirements will continue to be used as is. Note that Input Iterator
 127 implies Readable Iterator and Output Iterator implies Writable Iterator.
 128 <p>Note: we considered defining a Single-Pass Iterator, which could be combined
 129 with Readable or Writable Iterator to replace the Input and Output Iterator
 130 requirements. We rejected this idea because there are several differences
 131 between Input and Output Iterators that make it hard to merge them: Input
 132 Iterator requires Equality Comparable while Output Iterator does not and Input
 133 Iterator requires Assignable while Output Iterator does not.
 134 </p><h3>New categories and traits classes</h3>Each of the new iterator requirements
 135 will 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
 152 traits mechanism. Adding new typedefs to <tt>std::iterator_traits</tt> is not an
 153 acceptable solution because that would break every existing iterator. Instead,
 154 we 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
 156 which there is a valid definition of <tt>std::iterator_traits</tt>. This can be
 157 accomplished by making the default behavior of the traits classes map the
 158 <tt>iterator_category</tt> of the iterator to the appropriate return or
 159 traversal category. For new iterators, either specializations of these traits
 160 classes can be defined, or the iterator can provide nested typedefs, and inherit
 161 from <tt>new_iterator_base</tt> (which is just a signal to the traits class that
 162 it is a new iterator). As with <tt>std::iterator_traits</tt>, specializations
 163 for <tt>T*</tt> are provided. <pre>namespace std {
 164
 165   struct new_iterator_base { };
 166
 167   template &lt;typename Iterator&gt;
 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&lt;Iterator&gt; 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 &lt;typename T&gt;
 189   struct return_category&lt;T*&gt;
 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 &lt;typename Iterator&gt;
 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&lt;Iterator&gt; 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 &lt;typename T&gt;
 218   struct traversal_category&lt;T*&gt;
 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
 226 more requirements than necessary on their iterator parameters due to the
 227 coarseness of the current iterator categories. By using the new iterator
 228 categories a better fit can be achieved, thereby increasing the reusability of
 229 the algorithms. These changes will not affect user-code, though they will
 230 require changes by standard implementers: dispatching should be based on the new
 231 categories, and in places return values may need to be handled more carefully.
 232 In 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>-&gt; 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>-&gt; Swappable Iterator </td></tr>
 273   <tr>
 274     <td>fill</td>
 275     <td rowspan="2">Forward Iterator<br>-&gt; 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>-&gt; 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>-&gt; 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>-&gt; 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>-&gt; Bidirectional Traversal Iterator and
 306       Readable Iterator<br>Bidirectional Iterator<br>-&gt; Bidirectional
 307       Traversal Iterator and Writable Iterator </td></tr>
 308   <tr>
 309     <td>next_permutation</td>
 310     <td rowspan="2">Bidirectional Iterator<br>-&gt; 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>-&gt; 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>-&gt; Bidirectional Traversal Iterator and
 323       Readable Iterator </td></tr>
 324   <tr>
 325     <td>random_shuffle</td>
 326     <td rowspan="9">Random Access Iterator<br>-&gt; 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&lt;X&gt;::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
 365 Iterator is an iterator that dereferences to produce an rvalue that is
 366 convertible 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&lt;X&gt;::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&lt;X&gt;::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&lt;X&gt;::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
 385 Constructible</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&lt;X&gt;::reference</tt></td></tr>
 399   <tr>
 400     <td>Member access</td>
 401     <td><tt>x-&gt;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
 409 Iterator is an iterator that can be used to store a value using the
 410 dereference-assignment expression.
 411 <h3>Definitions</h3>If <tt>x</tt> is an Writable Iterator of type <tt>X</tt>,
 412 then 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
 414 overloaded; 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
 416 the <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
 418 non-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&lt;X&gt;::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
 428 Constructible</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
 444 Iterator is an iterator whose dereferenced values can be swapped.
 445 <p>Note: the requirements for Swappable Iterator are dependent on the issues
 446 surrounding <tt>std::swap()</tt> being resolved. Here we assume that the issue
 447 will be resolved by allowing the overload of <tt>std::swap()</tt> for
 448 user-defined types.
 449 </p><p>Note: Readable Iterator and Writable Iterator combined implies Swappable
 450 Iterator because of the fully templated <tt>std::swap()</tt>. However, Swappable
 451 Iterator 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&lt;X&gt;::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
 465 means 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
 485 Constant Lvalue Iterator is an iterator that dereferences to produce a const
 486 reference to the pointed-to object, i.e., the associated <tt>reference</tt> type
 487 is <tt>const T&amp;</tt>. Changing the value of or destroying an iterator that
 488 models Constant Lvalue Iterator does not invalidate pointers and references
 489 previously obtained from that iterator.
 490 <h3>Refinement of</h3><a href="#concept_ReadableIterator">Readable
 491 Iterator</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&lt;X&gt;::reference</tt></td>
 498     <td>The return type of dereferencing the iterator, which must be <tt>const
 499       T&amp;</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&lt;X&gt;::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&lt;X&gt;::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>&nbsp;</td>
 537
 538  <td><tt>std::iterator_traits&lt;X&gt;::reference</tt></td>
 539
 540 </tr>
 541
 542 <tr>
 543
 544  <td>Member access</td>
 545
 546  <td><tt>x-&gt;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  &nbsp;
 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
 567 Mutable Lvalue Iterator is an iterator that dereferences to produce a reference
 568 to the pointed-to object. The associated <tt>reference</tt> type is
 569 <tt>T&amp;</tt>. Changing the value of or destroying an iterator that models
 570 Mutable Lvalue Iterator does not invalidate pointers and references previously
 571 obtained from that iterator.
 572 <h3>Refinement of</h3><a href="#concept_ReadableIterator">Readable
 573 Iterator</a>, <a href="#concept_WritableIterator">Writable
 574 Iterator</a>, and <a href="#concept_SwappableIterator">Swappable
 575 Iterator</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&lt;X&gt;::reference</tt></td>
 582     <td>The return type of dereferencing the iterator, which must be
 583       <tt>T&amp;</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&lt;X&gt;::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&lt;X&gt;::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>&nbsp;</td>
 621
 622  <td><tt>std::iterator_traits&lt;X&gt;::reference</tt></td>
 623
 624 </tr>
 625
 626 <tr>
 627
 628  <td>Member access</td>
 629
 630  <td><tt>x-&gt;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  &nbsp;
 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
 652 permissible 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
 654 Constructible</a>, <a href="http://www.boost.org/libs/utility/Assignable.html">Assignable</a>, <a href="http://www.sgi.com/tech/stl/DefaultConstructible.html">Default
 655 Constructible</a>, and <a href="http://www.sgi.com/tech/stl/EqualityComparable.html">Equality
 656 Comparable</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&lt;X&gt;::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&lt;X&gt;::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&amp;</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&amp;</tt></td></tr></tbody></table>
 688 <p>
 689 </p><hr>
 690 <!--------------------------------------------------------------------------->
 691 <h3><a name="concept_BidirectionalTraversalIterator"></a>Bidirectional Traversal
 692 Iterator </h3>An iterator that can be incremented and decremented.
 693 <h3>Refinement of</h3><a href="#concept_ForwardTraversalIterator">Forward
 694 Traversal 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&lt;X&gt;::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&amp;</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&amp;</tt></td></tr></tbody></table>
 721 <p>
 722 </p><hr>
 723 <!--------------------------------------------------------------------------->
 724 <h3><a name="concept_RandomAccessTraversalIterator"></a>Random Access Traversal
 725 Iterator </h3>An iterator that provides constant-time methods for moving forward
 726 and backward in arbitrary-sized steps.
 727 <h3>Refinement of</h3><a href="#concept_BidirectionalTraversalIterator">Bidirectional
 728 Traversal Iterator</a> and <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">Less Than
 729 Comparable</a> where <tt>&lt;</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&lt;X&gt;::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&amp;</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&amp;</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&lt;X&gt;::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&lt;X&gt;::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>