libs/iterator/doc/new-iter-concepts.html

   1 <?xml version="1.0" encoding="utf-8" ?>
   2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
   3 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
   4 <head>
   5 <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
   6 <meta name="generator" content="Docutils 0.5: http://docutils.sourceforge.net/" />
   7 <title>New Iterator Concepts</title>
   8 <meta name="author" content="David Abrahams, Jeremy Siek, Thomas Witt" />
   9 <meta name="organization" content="Boost Consulting, Indiana University Open Systems Lab, Zephyr Associates, Inc." />
  10 <meta name="date" content="2006-09-11" />
  11 <meta name="copyright" content="Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003." />
  12 <link rel="stylesheet" href="../../../rst.css" type="text/css" />
  13 </head>
  14 <body>
  15 <div class="document" id="new-iterator-concepts">
  16 <h1 class="title">New Iterator Concepts</h1>
  17 <table class="docinfo" frame="void" rules="none">
  18 <col class="docinfo-name" />
  19 <col class="docinfo-content" />
  20 <tbody valign="top">
  21 <tr><th class="docinfo-name">Author:</th>
  22 <td>David Abrahams, Jeremy Siek, Thomas Witt</td></tr>
  23 <tr><th class="docinfo-name">Contact:</th>
  24 <td><a class="first reference external" href="mailto:dave&#64;boost-consulting.com">dave&#64;boost-consulting.com</a>, <a class="reference external" href="mailto:jsiek&#64;osl.iu.edu">jsiek&#64;osl.iu.edu</a>, <a class="last reference external" href="mailto:witt&#64;styleadvisor.com">witt&#64;styleadvisor.com</a></td></tr>
  25 <tr><th class="docinfo-name">Organization:</th>
  26 <td><a class="first reference external" href="http://www.boost-consulting.com">Boost Consulting</a>, Indiana University <a class="reference external" href="http://www.osl.iu.edu">Open Systems
  27 Lab</a>, <a class="last reference external" href="http://www.styleadvisor.com">Zephyr Associates, Inc.</a></td></tr>
  28 <tr><th class="docinfo-name">Date:</th>
  29 <td>2006-09-11</td></tr>
  30 <tr class="field"><th class="docinfo-name">Number:</th><td class="field-body">This is a revised version of <a class="reference external" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1550.htm">n1550</a>=03-0133, which was
  31 accepted for Technical Report 1 by the C++ standard
  32 committee's library working group. This proposal is a
  33 revision of paper <a class="reference external" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2001/n1297.html">n1297</a>, <a class="reference external" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1477.html">n1477</a>, and <a class="reference external" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1531.html">n1531</a>.</td>
  34 </tr>
  35 <tr><th class="docinfo-name">Copyright:</th>
  36 <td>Copyright David Abrahams, Jeremy Siek, and Thomas Witt
  37 2003.</td></tr>
  38 </tbody>
  39 </table>
  40 <!-- Distributed under the Boost -->
  41 <!-- Software License, Version 1.0. (See accompanying -->
  42 <!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
  43 <!-- Version 1.25 of this ReStructuredText document is the same as
  44 n1550_, the paper accepted by the LWG. -->
  45 <table class="docutils field-list" frame="void" rules="none">
  46 <col class="field-name" />
  47 <col class="field-body" />
  48 <tbody valign="top">
  49 <tr class="field"><th class="field-name">Abstract:</th><td class="field-body">We propose a new system of iterator concepts that treat
  50 access and positioning independently. This allows the
  51 concepts to more closely match the requirements
  52 of algorithms and provides better categorizations
  53 of iterators that are used in practice.</td>
  54 </tr>
  55 </tbody>
  56 </table>
  57 <div class="contents topic" id="table-of-contents">
  58 <p class="topic-title first">Table of Contents</p>
  59 <ul class="simple">
  60 <li><a class="reference internal" href="#motivation" id="id1">Motivation</a></li>
  61 <li><a class="reference internal" href="#impact-on-the-standard" id="id2">Impact on the Standard</a><ul>
  62 <li><a class="reference internal" href="#possible-but-not-proposed-changes-to-the-working-paper" id="id3">Possible (but not proposed) Changes to the Working Paper</a><ul>
  63 <li><a class="reference internal" href="#changes-to-algorithm-requirements" id="id4">Changes to Algorithm Requirements</a></li>
  64 <li><a class="reference internal" href="#deprecations" id="id5">Deprecations</a></li>
  65 <li><a class="reference internal" href="#vector-bool" id="id6"><tt class="docutils literal"><span class="pre">vector&lt;bool&gt;</span></tt></a></li>
  66 </ul>
  67 </li>
  68 </ul>
  69 </li>
  70 <li><a class="reference internal" href="#design" id="id7">Design</a></li>
  71 <li><a class="reference internal" href="#proposed-text" id="id8">Proposed Text</a><ul>
  72 <li><a class="reference internal" href="#addition-to-lib-iterator-requirements" id="id9">Addition to [lib.iterator.requirements]</a><ul>
  73 <li><a class="reference internal" href="#iterator-value-access-concepts-lib-iterator-value-access" id="id10">Iterator Value Access Concepts [lib.iterator.value.access]</a><ul>
  74 <li><a class="reference internal" href="#readable-iterators-lib-readable-iterators" id="id11">Readable Iterators [lib.readable.iterators]</a></li>
  75 <li><a class="reference internal" href="#writable-iterators-lib-writable-iterators" id="id12">Writable Iterators [lib.writable.iterators]</a></li>
  76 <li><a class="reference internal" href="#swappable-iterators-lib-swappable-iterators" id="id13">Swappable Iterators [lib.swappable.iterators]</a></li>
  77 <li><a class="reference internal" href="#lvalue-iterators-lib-lvalue-iterators" id="id14">Lvalue Iterators [lib.lvalue.iterators]</a></li>
  78 </ul>
  79 </li>
  80 <li><a class="reference internal" href="#iterator-traversal-concepts-lib-iterator-traversal" id="id15">Iterator Traversal Concepts [lib.iterator.traversal]</a><ul>
  81 <li><a class="reference internal" href="#incrementable-iterators-lib-incrementable-iterators" id="id16">Incrementable Iterators [lib.incrementable.iterators]</a></li>
  82 <li><a class="reference internal" href="#single-pass-iterators-lib-single-pass-iterators" id="id17">Single Pass Iterators [lib.single.pass.iterators]</a></li>
  83 <li><a class="reference internal" href="#forward-traversal-iterators-lib-forward-traversal-iterators" id="id18">Forward Traversal Iterators [lib.forward.traversal.iterators]</a></li>
  84 <li><a class="reference internal" href="#bidirectional-traversal-iterators-lib-bidirectional-traversal-iterators" id="id19">Bidirectional Traversal Iterators [lib.bidirectional.traversal.iterators]</a></li>
  85 <li><a class="reference internal" href="#random-access-traversal-iterators-lib-random-access-traversal-iterators" id="id20">Random Access Traversal Iterators [lib.random.access.traversal.iterators]</a></li>
  86 <li><a class="reference internal" href="#interoperable-iterators-lib-interoperable-iterators" id="id21">Interoperable Iterators [lib.interoperable.iterators]</a></li>
  87 </ul>
  88 </li>
  89 </ul>
  90 </li>
  91 <li><a class="reference internal" href="#addition-to-lib-iterator-synopsis" id="id22">Addition to [lib.iterator.synopsis]</a></li>
  92 <li><a class="reference internal" href="#addition-to-lib-iterator-traits" id="id23">Addition to [lib.iterator.traits]</a></li>
  93 </ul>
  94 </li>
  95 <li><a class="reference internal" href="#footnotes" id="id24">Footnotes</a></li>
  96 </ul>
  97 </div>
  98 <div class="section" id="motivation">
  99 <h1><a class="toc-backref" href="#id1">Motivation</a></h1>
 100 <p>The standard iterator categories and requirements are flawed because
 101 they use a single hierarchy of concepts to address two orthogonal
 102 issues: <em>iterator traversal</em> and <em>value access</em>. As a result, many
 103 algorithms with requirements expressed in terms of the iterator
 104 categories are too strict. Also, many real-world iterators can not be
 105 accurately categorized.  A proxy-based iterator with random-access
 106 traversal, for example, may only legally have a category of &quot;input
 107 iterator&quot;, so generic algorithms are unable to take advantage of its
 108 random-access capabilities.  The current iterator concept hierarchy is
 109 geared towards iterator traversal (hence the category names), while
 110 requirements that address value access sneak in at various places. The
 111 following table gives a summary of the current value access
 112 requirements in the iterator categories.</p>
 113 <table border="1" class="docutils">
 114 <colgroup>
 115 <col width="31%" />
 116 <col width="69%" />
 117 </colgroup>
 118 <thead valign="bottom">
 119 <tr><th class="head" colspan="2">Value Access Requirements in Existing Iterator Categories</th>
 120 </tr>
 121 </thead>
 122 <tbody valign="top">
 123 <tr><td>Output Iterator</td>
 124 <td><tt class="docutils literal"><span class="pre">*i</span> <span class="pre">=</span> <span class="pre">a</span></tt></td>
 125 </tr>
 126 <tr><td>Input Iterator</td>
 127 <td><tt class="docutils literal"><span class="pre">*i</span></tt> is convertible to <tt class="docutils literal"><span class="pre">T</span></tt></td>
 128 </tr>
 129 <tr><td>Forward Iterator</td>
 130 <td><tt class="docutils literal"><span class="pre">*i</span></tt> is <tt class="docutils literal"><span class="pre">T&amp;</span></tt> (or <tt class="docutils literal"><span class="pre">const</span> <span class="pre">T&amp;</span></tt> once <a class="reference external" href="http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#200">issue 200</a>
 131 is resolved)</td>
 132 </tr>
 133 <tr><td>Random Access Iterator</td>
 134 <td><tt class="docutils literal"><span class="pre">i[n]</span></tt> is convertible to <tt class="docutils literal"><span class="pre">T</span></tt> (also <tt class="docutils literal"><span class="pre">i[n]</span> <span class="pre">=</span> <span class="pre">t</span></tt>
 135 is required for mutable iterators once <a class="reference external" href="http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#299">issue 299</a>
 136 is resolved)</td>
 137 </tr>
 138 </tbody>
 139 </table>
 140 <p>Because iterator traversal and value access are mixed together in a
 141 single hierarchy, many useful iterators can not be appropriately
 142 categorized. For example, <tt class="docutils literal"><span class="pre">vector&lt;bool&gt;::iterator</span></tt> is almost a
 143 random access iterator, but the return type is not <tt class="docutils literal"><span class="pre">bool&amp;</span></tt> (see
 144 <a class="reference external" href="http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#96">issue 96</a> and Herb Sutter's paper J16/99-0008 = WG21
 145 N1185). Therefore, the iterators of <tt class="docutils literal"><span class="pre">vector&lt;bool&gt;</span></tt> only meet the
 146 requirements of input iterator and output iterator.  This is so
 147 nonintuitive that the C++ standard contradicts itself on this point.
 148 In paragraph 23.2.4/1 it says that a <tt class="docutils literal"><span class="pre">vector</span></tt> is a sequence that
 149 supports random access iterators.</p>
 150 <p>Another difficult-to-categorize iterator is the transform iterator, an
 151 adaptor which applies a unary function object to the dereferenced
 152 value of the some underlying iterator (see <a class="reference external" href="http://www.boost.org/libs/utility/transform_iterator.htm">transform_iterator</a>).
 153 For unary functions such as <tt class="docutils literal"><span class="pre">times</span></tt>, the return type of
 154 <tt class="docutils literal"><span class="pre">operator*</span></tt> clearly needs to be the <tt class="docutils literal"><span class="pre">result_type</span></tt> of the function
 155 object, which is typically not a reference.  Because random access
 156 iterators are required to return lvalues from <tt class="docutils literal"><span class="pre">operator*</span></tt>, if you
 157 wrap <tt class="docutils literal"><span class="pre">int*</span></tt> with a transform iterator, you do not get a random
 158 access iterator as might be expected, but an input iterator.</p>
 159 <p>A third example is found in the vertex and edge iterators of the
 160 <a class="reference external" href="http://www.boost.org/libs/graph/doc/table_of_contents.html">Boost Graph Library</a>. These iterators return vertex and edge
 161 descriptors, which are lightweight handles created on-the-fly. They
 162 must be returned by-value. As a result, their current standard
 163 iterator category is <tt class="docutils literal"><span class="pre">input_iterator_tag</span></tt>, which means that,
 164 strictly speaking, you could not use these iterators with algorithms
 165 like <tt class="docutils literal"><span class="pre">min_element()</span></tt>. As a temporary solution, the concept
 166 <a class="reference external" href="http://www.boost.org/libs/utility/MultiPassInputIterator.html">Multi-Pass Input Iterator</a> was introduced to describe the vertex and
 167 edge descriptors, but as the design notes for the concept suggest, a
 168 better solution is needed.</p>
 169 <p>In short, there are many useful iterators that do not fit into the
 170 current standard iterator categories. As a result, the following bad
 171 things happen:</p>
 172 <ul class="simple">
 173 <li>Iterators are often mis-categorized.</li>
 174 <li>Algorithm requirements are more strict than necessary, because they
 175 cannot separate the need for random access or bidirectional
 176 traversal from the need for a true reference return type.</li>
 177 </ul>
 178 </div>
 179 <div class="section" id="impact-on-the-standard">
 180 <h1><a class="toc-backref" href="#id2">Impact on the Standard</a></h1>
 181 <p>This proposal for TR1 is a pure extension. Further, the new iterator
 182 concepts are backward-compatible with the old iterator requirements,
 183 and old iterators are forward-compatible with the new iterator
 184 concepts. That is to say, iterators that satisfy the old requirements
 185 also satisfy appropriate concepts in the new system, and iterators
 186 modeling the new concepts will automatically satisfy the appropriate
 187 old requirements.</p>
 188 <!-- I think we need to say something about the resolution to allow
 189 convertibility to any of the old-style tags as a TR issue (hope it
 190 made it). -DWA -->
 191 <!-- Hmm, not sure I understand. Are you talking about whether a
 192 standards conforming input iterator is allowed to have
 193 a tag that is not input_iterator_tag but that
 194 is convertible to input_iterator_tag? -JGS -->
 195 <div class="section" id="possible-but-not-proposed-changes-to-the-working-paper">
 196 <h2><a class="toc-backref" href="#id3">Possible (but not proposed) Changes to the Working Paper</a></h2>
 197 <p>The extensions in this paper suggest several changes we might make
 198 to the working paper for the next standard.  These changes are not
 199 a formal part of this proposal for TR1.</p>
 200 <div class="section" id="changes-to-algorithm-requirements">
 201 <h3><a class="toc-backref" href="#id4">Changes to Algorithm Requirements</a></h3>
 202 <p>The algorithms in the standard library could benefit from the new
 203 iterator concepts because the new concepts provide a more accurate way
 204 to express their type requirements. The result is algorithms that are
 205 usable in more situations and have fewer type requirements.</p>
 206 <p>For the next working paper (but not for TR1), the committee should
 207 consider the following changes to the type requirements of algorithms.
 208 These changes are phrased as textual substitutions, listing the
 209 algorithms to which each textual substitution applies.</p>
 210 <p>Forward Iterator -&gt; Forward Traversal Iterator and Readable Iterator</p>
 211 <blockquote>
 212 <tt class="docutils literal"><span class="pre">find_end,</span> <span class="pre">adjacent_find,</span> <span class="pre">search,</span> <span class="pre">search_n,</span> <span class="pre">rotate_copy,</span>
 213 <span class="pre">lower_bound,</span> <span class="pre">upper_bound,</span> <span class="pre">equal_range,</span> <span class="pre">binary_search,</span>
 214 <span class="pre">min_element,</span> <span class="pre">max_element</span></tt></blockquote>
 215 <p>Forward Iterator (1) -&gt; Single Pass Iterator and Readable Iterator,
 216 Forward Iterator (2) -&gt; Forward Traversal Iterator and Readable Iterator</p>
 217 <blockquote>
 218 <tt class="docutils literal"><span class="pre">find_first_of</span></tt></blockquote>
 219 <p>Forward Iterator -&gt; Readable Iterator and Writable Iterator</p>
 220 <blockquote>
 221 <tt class="docutils literal"><span class="pre">iter_swap</span></tt></blockquote>
 222 <p>Forward Iterator -&gt; Single Pass Iterator and Writable Iterator</p>
 223 <blockquote>
 224 <tt class="docutils literal"><span class="pre">fill,</span> <span class="pre">generate</span></tt></blockquote>
 225 <p>Forward Iterator -&gt; Forward Traversal Iterator and Swappable Iterator</p>
 226 <blockquote>
 227 <tt class="docutils literal"><span class="pre">rotate</span></tt></blockquote>
 228 <p>Forward Iterator (1) -&gt; Swappable Iterator and Single Pass Iterator,
 229 Forward Iterator (2) -&gt; Swappable Iterator and  Incrementable Iterator</p>
 230 <blockquote>
 231 <tt class="docutils literal"><span class="pre">swap_ranges</span></tt></blockquote>
 232 <dl class="docutils">
 233 <dt>Forward Iterator -&gt; Forward Traversal Iterator and Readable Iterator and Writable Iterator</dt>
 234 <dd><tt class="docutils literal"><span class="pre">remove,</span> <span class="pre">remove_if,</span> <span class="pre">unique</span></tt></dd>
 235 </dl>
 236 <p>Forward Iterator -&gt; Single Pass Iterator and Readable Iterator and Writable Iterator</p>
 237 <blockquote>
 238 <tt class="docutils literal"><span class="pre">replace,</span> <span class="pre">replace_if</span></tt></blockquote>
 239 <dl class="docutils">
 240 <dt>Bidirectional Iterator -&gt; Bidirectional Traversal Iterator and Swappable Iterator</dt>
 241 <dd><tt class="docutils literal"><span class="pre">reverse</span></tt></dd>
 242 <dt>Bidirectional Iterator -&gt; Bidirectional Traversal Iterator and Readable and Swappable Iterator</dt>
 243 <dd><tt class="docutils literal"><span class="pre">partition</span></tt></dd>
 244 </dl>
 245 <p>Bidirectional Iterator (1) -&gt; Bidirectional Traversal Iterator and Readable Iterator,
 246 Bidirectional Iterator (2) -&gt; Bidirectional Traversal Iterator and Writable Iterator</p>
 247 <blockquote>
 248 <tt class="docutils literal"><span class="pre">copy_backwards</span></tt></blockquote>
 249 <dl class="docutils">
 250 <dt>Bidirectional Iterator -&gt; Bidirectional Traversal Iterator and Swappable Iterator and Readable Iterator</dt>
 251 <dd><tt class="docutils literal"><span class="pre">next_permutation,</span> <span class="pre">prev_permutation</span></tt></dd>
 252 <dt>Bidirectional Iterator -&gt; Bidirectional Traversal Iterator and Readable Iterator and Writable Iterator</dt>
 253 <dd><tt class="docutils literal"><span class="pre">stable_partition,</span> <span class="pre">inplace_merge</span></tt></dd>
 254 <dt>Bidirectional Iterator -&gt; Bidirectional Traversal Iterator and Readable Iterator</dt>
 255 <dd><tt class="docutils literal"><span class="pre">reverse_copy</span></tt></dd>
 256 <dt>Random Access Iterator -&gt; Random Access Traversal Iterator and Readable and Writable Iterator</dt>
 257 <dd><tt class="docutils literal"><span class="pre">random_shuffle,</span> <span class="pre">sort,</span> <span class="pre">stable_sort,</span> <span class="pre">partial_sort,</span> <span class="pre">nth_element,</span> <span class="pre">push_heap,</span> <span class="pre">pop_heap</span>
 258 <span class="pre">make_heap,</span> <span class="pre">sort_heap</span></tt></dd>
 259 <dt>Input Iterator (2) -&gt; Incrementable Iterator and Readable Iterator</dt>
 260 <dd><tt class="docutils literal"><span class="pre">equal,</span> <span class="pre">mismatch</span></tt></dd>
 261 <dt>Input Iterator (2) -&gt; Incrementable Iterator and Readable Iterator</dt>
 262 <dd><tt class="docutils literal"><span class="pre">transform</span></tt></dd>
 263 </dl>
 264 </div>
 265 <div class="section" id="deprecations">
 266 <h3><a class="toc-backref" href="#id5">Deprecations</a></h3>
 267 <p>For the next working paper (but not for TR1), the committee should
 268 consider deprecating the old iterator tags, and
 269 std::iterator_traits, since it will be superceded by individual
 270 traits metafunctions.</p>
 271 </div>
 272 <div class="section" id="vector-bool">
 273 <h3><a class="toc-backref" href="#id6"><tt class="docutils literal"><span class="pre">vector&lt;bool&gt;</span></tt></a></h3>
 274 <p>For the next working paper (but not for TR1), the committee should
 275 consider reclassifying <tt class="docutils literal"><span class="pre">vector&lt;bool&gt;::iterator</span></tt> as a Random
 276 Access Traversal Iterator and Readable Iterator and Writable
 277 Iterator.</p>
 278 </div>
 279 </div>
 280 </div>
 281 <div class="section" id="design">
 282 <h1><a class="toc-backref" href="#id7">Design</a></h1>
 283 <p>The iterator requirements are to be separated into two groups. One set
 284 of concepts handles the syntax and semantics of value access:</p>
 285 <ul class="simple">
 286 <li>Readable Iterator</li>
 287 <li>Writable Iterator</li>
 288 <li>Swappable Iterator</li>
 289 <li>Lvalue Iterator</li>
 290 </ul>
 291 <p>The access concepts describe requirements related to <tt class="docutils literal"><span class="pre">operator*</span></tt> and
 292 <tt class="docutils literal"><span class="pre">operator-&gt;</span></tt>, including the <tt class="docutils literal"><span class="pre">value_type</span></tt>, <tt class="docutils literal"><span class="pre">reference</span></tt>, and
 293 <tt class="docutils literal"><span class="pre">pointer</span></tt> associated types.</p>
 294 <p>The other set of concepts handles traversal:</p>
 295 <ul class="simple">
 296 <li>Incrementable Iterator</li>
 297 <li>Single Pass Iterator</li>
 298 <li>Forward Traversal Iterator</li>
 299 <li>Bidirectional Traversal Iterator</li>
 300 <li>Random Access Traversal Iterator</li>
 301 </ul>
 302 <p>The refinement relationships for the traversal concepts are in the
 303 following diagram.</p>
 304 <img alt="traversal.png" src="traversal.png" />
 305 <p>In addition to the iterator movement operators, such as
 306 <tt class="docutils literal"><span class="pre">operator++</span></tt>, the traversal concepts also include requirements on
 307 position comparison such as <tt class="docutils literal"><span class="pre">operator==</span></tt> and <tt class="docutils literal"><span class="pre">operator&lt;</span></tt>.  The
 308 reason for the fine grain slicing of the concepts into the
 309 Incrementable and Single Pass is to provide concepts that are exact
 310 matches with the original input and output iterator requirements.</p>
 311 <p>This proposal also includes a concept for specifying when an iterator
 312 is interoperable with another iterator, in the sense that <tt class="docutils literal"><span class="pre">int*</span></tt> is
 313 interoperable with <tt class="docutils literal"><span class="pre">int</span> <span class="pre">const*</span></tt>.</p>
 314 <ul class="simple">
 315 <li>Interoperable Iterators</li>
 316 </ul>
 317 <p>The relationship between the new iterator concepts and the old are
 318 given in the following diagram.</p>
 319 <img alt="oldeqnew.png" src="oldeqnew.png" />
 320 <p>Like the old iterator requirements, we provide tags for purposes of
 321 dispatching based on the traversal concepts.  The tags are related via
 322 inheritance so that a tag is convertible to another tag if the concept
 323 associated with the first tag is a refinement of the second tag.</p>
 324 <p>Our design reuses <tt class="docutils literal"><span class="pre">iterator_traits&lt;Iter&gt;::iterator_category</span></tt> to
 325 indicate an iterator's traversal capability.  To specify
 326 capabilities not captured by any old-style iterator category, an
 327 iterator designer can use an <tt class="docutils literal"><span class="pre">iterator_category</span></tt> type that is
 328 convertible to both the the most-derived old iterator category tag
 329 which fits, and the appropriate new iterator traversal tag.</p>
 330 <!-- dwa2003/1/2: Note that we are not *requiring* convertibility to
 331 a new-style traversal tag in order to meet new concepts.
 332 Old-style iterators still fit, after all. -->
 333 <p>We do not provide tags for the purposes of dispatching based on the
 334 access concepts, in part because we could not find a way to
 335 automatically infer the right access tags for old-style iterators.
 336 An iterator's writability may be dependent on the assignability of
 337 its <tt class="docutils literal"><span class="pre">value_type</span></tt> and there's no known way to detect whether an
 338 arbitrary type is assignable.  Fortunately, the need for
 339 dispatching based on access capability is not as great as the need
 340 for dispatching based on traversal capability.</p>
 341 <p>A difficult design decision concerned the <tt class="docutils literal"><span class="pre">operator[]</span></tt>. The direct
 342 approach for specifying <tt class="docutils literal"><span class="pre">operator[]</span></tt> would have a return type of
 343 <tt class="docutils literal"><span class="pre">reference</span></tt>; the same as <tt class="docutils literal"><span class="pre">operator*</span></tt>. However, going in this
 344 direction would mean that an iterator satisfying the old Random Access
 345 Iterator requirements would not necessarily be a model of Readable or
 346 Writable Lvalue Iterator.  Instead we have chosen a design that
 347 matches the preferred resolution of <a class="reference external" href="http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#299">issue 299</a>: <tt class="docutils literal"><span class="pre">operator[]</span></tt> is
 348 only required to return something convertible to the <tt class="docutils literal"><span class="pre">value_type</span></tt>
 349 (for a Readable Iterator), and is required to support assignment
 350 <tt class="docutils literal"><span class="pre">i[n]</span> <span class="pre">=</span> <span class="pre">t</span></tt> (for a Writable Iterator).</p>
 351 </div>
 352 <div class="section" id="proposed-text">
 353 <h1><a class="toc-backref" href="#id8">Proposed Text</a></h1>
 354 <div class="section" id="addition-to-lib-iterator-requirements">
 355 <h2><a class="toc-backref" href="#id9">Addition to [lib.iterator.requirements]</a></h2>
 356 <div class="section" id="iterator-value-access-concepts-lib-iterator-value-access">
 357 <h3><a class="toc-backref" href="#id10">Iterator Value Access Concepts [lib.iterator.value.access]</a></h3>
 358 <p>In the tables below, <tt class="docutils literal"><span class="pre">X</span></tt> is an iterator type, <tt class="docutils literal"><span class="pre">a</span></tt> is a constant
 359 object of type <tt class="docutils literal"><span class="pre">X</span></tt>, <tt class="docutils literal"><span class="pre">R</span></tt> is
 360 <tt class="docutils literal"><span class="pre">std::iterator_traits&lt;X&gt;::reference</span></tt>, <tt class="docutils literal"><span class="pre">T</span></tt> is
 361 <tt class="docutils literal"><span class="pre">std::iterator_traits&lt;X&gt;::value_type</span></tt>, and <tt class="docutils literal"><span class="pre">v</span></tt> is a constant
 362 object of type <tt class="docutils literal"><span class="pre">T</span></tt>.</p>
 363 <div class="section" id="readable-iterators-lib-readable-iterators">
 364 <span id="readable-iterator"></span><h4><a class="toc-backref" href="#id11">Readable Iterators [lib.readable.iterators]</a></h4>
 365 <p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Readable Iterator</em> concept
 366 for value type <tt class="docutils literal"><span class="pre">T</span></tt> if, in addition to <tt class="docutils literal"><span class="pre">X</span></tt> being Assignable and
 367 Copy Constructible, the following expressions are valid and respect
 368 the stated semantics. <tt class="docutils literal"><span class="pre">U</span></tt> is the type of any specified member of
 369 type <tt class="docutils literal"><span class="pre">T</span></tt>.</p>
 370 <table border="1" class="docutils">
 371 <colgroup>
 372 <col width="28%" />
 373 <col width="20%" />
 374 <col width="52%" />
 375 </colgroup>
 376 <thead valign="bottom">
 377 <tr><th class="head" colspan="3">Readable Iterator Requirements (in addition to Assignable and Copy Constructible)</th>
 378 </tr>
 379 <tr><th class="head">Expression</th>
 380 <th class="head">Return Type</th>
 381 <th class="head">Note/Precondition</th>
 382 </tr>
 383 </thead>
 384 <tbody valign="top">
 385 <tr><td><tt class="docutils literal"><span class="pre">iterator_traits&lt;X&gt;::value_type</span></tt></td>
 386 <td><tt class="docutils literal"><span class="pre">T</span></tt></td>
 387 <td>Any non-reference,
 388 non-cv-qualified type</td>
 389 </tr>
 390 <tr><td><tt class="docutils literal"><span class="pre">*a</span></tt></td>
 391 <td>Convertible to <tt class="docutils literal"><span class="pre">T</span></tt></td>
 392 <td><dl class="first last docutils">
 393 <dt>pre: <tt class="docutils literal"><span class="pre">a</span></tt> is dereferenceable. If <tt class="docutils literal"><span class="pre">a</span> <span class="pre">==</span> <span class="pre">b</span></tt> then <tt class="docutils literal"><span class="pre">*a</span></tt></dt>
 394 <dd>is equivalent to <tt class="docutils literal"><span class="pre">*b</span></tt>.</dd>
 395 </dl>
 396 </td>
 397 </tr>
 398 <tr><td><tt class="docutils literal"><span class="pre">a-&gt;m</span></tt></td>
 399 <td><tt class="docutils literal"><span class="pre">U&amp;</span></tt></td>
 400 <td>pre: <tt class="docutils literal"><span class="pre">pre:</span> <span class="pre">(*a).m</span></tt> is well-defined. Equivalent to <tt class="docutils literal"><span class="pre">(*a).m</span></tt>.</td>
 401 </tr>
 402 </tbody>
 403 </table>
 404 <!-- We won't say anything about iterator_traits<X>::reference until the DR is resolved. -JGS -->
 405 </div>
 406 <div class="section" id="writable-iterators-lib-writable-iterators">
 407 <span id="writable-iterator"></span><h4><a class="toc-backref" href="#id12">Writable Iterators [lib.writable.iterators]</a></h4>
 408 <p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Writable Iterator</em> concept
 409 if, in addition to <tt class="docutils literal"><span class="pre">X</span></tt> being Copy Constructible, the following
 410 expressions are valid and respect the stated semantics.  Writable
 411 Iterators have an associated <em>set of value types</em>.</p>
 412 <table border="1" class="docutils">
 413 <colgroup>
 414 <col width="37%" />
 415 <col width="21%" />
 416 <col width="42%" />
 417 </colgroup>
 418 <thead valign="bottom">
 419 <tr><th class="head" colspan="3">Writable Iterator Requirements (in addition to Copy Constructible)</th>
 420 </tr>
 421 <tr><th class="head">Expression</th>
 422 <th class="head">Return Type</th>
 423 <th class="head">Precondition</th>
 424 </tr>
 425 </thead>
 426 <tbody valign="top">
 427 <tr><td><tt class="docutils literal"><span class="pre">*a</span> <span class="pre">=</span> <span class="pre">o</span></tt></td>
 428 <td>&nbsp;</td>
 429 <td>pre: The type of <tt class="docutils literal"><span class="pre">o</span></tt>
 430 is in the set of
 431 value types of <tt class="docutils literal"><span class="pre">X</span></tt></td>
 432 </tr>
 433 </tbody>
 434 </table>
 435 </div>
 436 <div class="section" id="swappable-iterators-lib-swappable-iterators">
 437 <h4><a class="toc-backref" href="#id13">Swappable Iterators [lib.swappable.iterators]</a></h4>
 438 <p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Swappable Iterator</em> concept
 439 if, in addition to <tt class="docutils literal"><span class="pre">X</span></tt> being Copy Constructible, the following
 440 expressions are valid and respect the stated semantics.</p>
 441 <table border="1" class="docutils">
 442 <colgroup>
 443 <col width="37%" />
 444 <col width="19%" />
 445 <col width="43%" />
 446 </colgroup>
 447 <thead valign="bottom">
 448 <tr><th class="head" colspan="3">Swappable Iterator Requirements (in addition to Copy Constructible)</th>
 449 </tr>
 450 <tr><th class="head">Expression</th>
 451 <th class="head">Return Type</th>
 452 <th class="head">Postcondition</th>
 453 </tr>
 454 </thead>
 455 <tbody valign="top">
 456 <tr><td><tt class="docutils literal"><span class="pre">iter_swap(a,</span> <span class="pre">b)</span></tt></td>
 457 <td><tt class="docutils literal"><span class="pre">void</span></tt></td>
 458 <td>the pointed to values are
 459 exchanged</td>
 460 </tr>
 461 </tbody>
 462 </table>
 463 <p>[<em>Note:</em> An iterator that is a model of the <a class="reference internal" href="#readable-iterator">Readable Iterator</a> and
 464 <a class="reference internal" href="#writable-iterator">Writable Iterator</a> concepts is also a model of <em>Swappable
 465 Iterator</em>.  <em>--end note</em>]</p>
 466 </div>
 467 <div class="section" id="lvalue-iterators-lib-lvalue-iterators">
 468 <h4><a class="toc-backref" href="#id14">Lvalue Iterators [lib.lvalue.iterators]</a></h4>
 469 <p>The <em>Lvalue Iterator</em> concept adds the requirement that the return
 470 type of <tt class="docutils literal"><span class="pre">operator*</span></tt> type be a reference to the value type of the
 471 iterator.</p>
 472 <table border="1" class="docutils">
 473 <colgroup>
 474 <col width="22%" />
 475 <col width="19%" />
 476 <col width="59%" />
 477 </colgroup>
 478 <thead valign="bottom">
 479 <tr><th class="head" colspan="3">Lvalue Iterator Requirements</th>
 480 </tr>
 481 <tr><th class="head">Expression</th>
 482 <th class="head">Return Type</th>
 483 <th class="head">Note/Assertion</th>
 484 </tr>
 485 </thead>
 486 <tbody valign="top">
 487 <tr><td><tt class="docutils literal"><span class="pre">*a</span></tt></td>
 488 <td><tt class="docutils literal"><span class="pre">T&amp;</span></tt></td>
 489 <td><tt class="docutils literal"><span class="pre">T</span></tt> is <em>cv</em>
 490 <tt class="docutils literal"><span class="pre">iterator_traits&lt;X&gt;::value_type</span></tt>
 491 where <em>cv</em> is an optional
 492 cv-qualification.  pre: <tt class="docutils literal"><span class="pre">a</span></tt> is
 493 dereferenceable.</td>
 494 </tr>
 495 </tbody>
 496 </table>
 497 <p>If <tt class="docutils literal"><span class="pre">X</span></tt> is a <a class="reference internal" href="#writable-iterator">Writable Iterator</a> then <tt class="docutils literal"><span class="pre">a</span> <span class="pre">==</span> <span class="pre">b</span></tt> if and only if
 498 <tt class="docutils literal"><span class="pre">*a</span></tt> is the same object as <tt class="docutils literal"><span class="pre">*b</span></tt>.  If <tt class="docutils literal"><span class="pre">X</span></tt> is a <a class="reference internal" href="#readable-iterator">Readable
 499 Iterator</a> then <tt class="docutils literal"><span class="pre">a</span> <span class="pre">==</span> <span class="pre">b</span></tt> implies <tt class="docutils literal"><span class="pre">*a</span></tt> is the same object as
 500 <tt class="docutils literal"><span class="pre">*b</span></tt>.</p>
 501 </div>
 502 </div>
 503 <div class="section" id="iterator-traversal-concepts-lib-iterator-traversal">
 504 <h3><a class="toc-backref" href="#id15">Iterator Traversal Concepts [lib.iterator.traversal]</a></h3>
 505 <p>In the tables below, <tt class="docutils literal"><span class="pre">X</span></tt> is an iterator type, <tt class="docutils literal"><span class="pre">a</span></tt> and <tt class="docutils literal"><span class="pre">b</span></tt> are
 506 constant objects of type <tt class="docutils literal"><span class="pre">X</span></tt>, <tt class="docutils literal"><span class="pre">r</span></tt> and <tt class="docutils literal"><span class="pre">s</span></tt> are mutable objects of
 507 type <tt class="docutils literal"><span class="pre">X</span></tt>, <tt class="docutils literal"><span class="pre">T</span></tt> is <tt class="docutils literal"><span class="pre">std::iterator_traits&lt;X&gt;::value_type</span></tt>, and
 508 <tt class="docutils literal"><span class="pre">v</span></tt> is a constant object of type <tt class="docutils literal"><span class="pre">T</span></tt>.</p>
 509 <div class="section" id="incrementable-iterators-lib-incrementable-iterators">
 510 <h4><a class="toc-backref" href="#id16">Incrementable Iterators [lib.incrementable.iterators]</a></h4>
 511 <p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Incrementable Iterator</em>
 512 concept if, in addition to <tt class="docutils literal"><span class="pre">X</span></tt> being Assignable and Copy
 513 Constructible, the following expressions are valid and respect the
 514 stated semantics.</p>
 515 <table border="1" class="docutils">
 516 <colgroup>
 517 <col width="39%" />
 518 <col width="38%" />
 519 <col width="23%" />
 520 </colgroup>
 521 <thead valign="bottom">
 522 <tr><th class="head" colspan="3">Incrementable Iterator Requirements (in addition to Assignable, Copy Constructible)</th>
 523 </tr>
 524 <tr><th class="head">Expression</th>
 525 <th class="head">Return Type</th>
 526 <th class="head">Assertion</th>
 527 </tr>
 528 </thead>
 529 <tbody valign="top">
 530 <tr><td><tt class="docutils literal"><span class="pre">++r</span></tt></td>
 531 <td><tt class="docutils literal"><span class="pre">X&amp;</span></tt></td>
 532 <td><tt class="docutils literal"><span class="pre">&amp;r</span> <span class="pre">==</span> <span class="pre">&amp;++r</span></tt></td>
 533 </tr>
 534 <tr><td><tt class="docutils literal"><span class="pre">r++</span></tt></td>
 535 <td>&nbsp;</td>
 536 <td>&nbsp;</td>
 537 </tr>
 538 <tr><td><tt class="docutils literal"><span class="pre">*r++</span></tt></td>
 539 <td>&nbsp;</td>
 540 <td>&nbsp;</td>
 541 </tr>
 542 <tr><td><tt class="docutils literal"><span class="pre">iterator_traversal&lt;X&gt;::type</span></tt></td>
 543 <td>Convertible to
 544 <tt class="docutils literal"><span class="pre">incrementable_traversal_tag</span></tt></td>
 545 <td>&nbsp;</td>
 546 </tr>
 547 </tbody>
 548 </table>
 549 <p>If <tt class="docutils literal"><span class="pre">X</span></tt> is a <a class="reference internal" href="#writable-iterator">Writable Iterator</a> then <tt class="docutils literal"><span class="pre">X</span> <span class="pre">a(r++);</span></tt> is equivalent
 550 to <tt class="docutils literal"><span class="pre">X</span> <span class="pre">a(r);</span> <span class="pre">++r;</span></tt> and <tt class="docutils literal"><span class="pre">*r++</span> <span class="pre">=</span> <span class="pre">o</span></tt> is equivalent
 551 to  <tt class="docutils literal"><span class="pre">*r</span> <span class="pre">=</span> <span class="pre">o;</span> <span class="pre">++r</span></tt>.
 552 If <tt class="docutils literal"><span class="pre">X</span></tt> is a <a class="reference internal" href="#readable-iterator">Readable Iterator</a> then <tt class="docutils literal"><span class="pre">T</span> <span class="pre">z(*r++);</span></tt> is equivalent
 553 to <tt class="docutils literal"><span class="pre">T</span> <span class="pre">z(*r);</span> <span class="pre">++r;</span></tt>.</p>
 554 <!-- TR1: incrementable_iterator_tag changed to
 555 incrementable_traversal_tag for consistency. -->
 556 </div>
 557 <div class="section" id="single-pass-iterators-lib-single-pass-iterators">
 558 <h4><a class="toc-backref" href="#id17">Single Pass Iterators [lib.single.pass.iterators]</a></h4>
 559 <p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Single Pass Iterator</em>
 560 concept if the following expressions are valid and respect the stated
 561 semantics.</p>
 562 <table border="1" class="docutils">
 563 <colgroup>
 564 <col width="37%" />
 565 <col width="27%" />
 566 <col width="12%" />
 567 <col width="25%" />
 568 </colgroup>
 569 <thead valign="bottom">
 570 <tr><th class="head" colspan="4">Single Pass Iterator Requirements (in addition to Incrementable Iterator and Equality
 571 Comparable)</th>
 572 </tr>
 573 <tr><th class="head">Expression</th>
 574 <th class="head">Return Type</th>
 575 <th class="head">Operational
 576 Semantics</th>
 577 <th class="head">Assertion/
 578 Pre-/Post-condition</th>
 579 </tr>
 580 </thead>
 581 <tbody valign="top">
 582 <tr><td><tt class="docutils literal"><span class="pre">++r</span></tt></td>
 583 <td><tt class="docutils literal"><span class="pre">X&amp;</span></tt></td>
 584 <td>&nbsp;</td>
 585 <td>pre: <tt class="docutils literal"><span class="pre">r</span></tt> is
 586 dereferenceable; post:
 587 <tt class="docutils literal"><span class="pre">r</span></tt> is dereferenceable or
 588 <tt class="docutils literal"><span class="pre">r</span></tt> is past-the-end</td>
 589 </tr>
 590 <tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">==</span> <span class="pre">b</span></tt></td>
 591 <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
 592 <td>&nbsp;</td>
 593 <td><tt class="docutils literal"><span class="pre">==</span></tt> is an equivalence
 594 relation over its domain</td>
 595 </tr>
 596 <tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">!=</span> <span class="pre">b</span></tt></td>
 597 <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
 598 <td><tt class="docutils literal"><span class="pre">!(a</span> <span class="pre">==</span> <span class="pre">b)</span></tt></td>
 599 <td>&nbsp;</td>
 600 </tr>
 601 <tr><td><tt class="docutils literal"><span class="pre">iterator_traits&lt;X&gt;::difference_type</span></tt></td>
 602 <td>A signed integral type
 603 representing the distance
 604 between iterators</td>
 605 <td>&nbsp;</td>
 606 <td>&nbsp;</td>
 607 </tr>
 608 <tr><td><tt class="docutils literal"><span class="pre">iterator_traversal&lt;X&gt;::type</span></tt></td>
 609 <td>Convertible to
 610 <tt class="docutils literal"><span class="pre">single_pass_traversal_tag</span></tt></td>
 611 <td>&nbsp;</td>
 612 <td>&nbsp;</td>
 613 </tr>
 614 </tbody>
 615 </table>
 616 <!-- TR1: single_pass_iterator_tag changed to
 617 single_pass_traversal_tag for consistency -->
 618 </div>
 619 <div class="section" id="forward-traversal-iterators-lib-forward-traversal-iterators">
 620 <h4><a class="toc-backref" href="#id18">Forward Traversal Iterators [lib.forward.traversal.iterators]</a></h4>
 621 <p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Forward Traversal Iterator</em>
 622 concept if, in addition to <tt class="docutils literal"><span class="pre">X</span></tt> meeting the requirements of Default
 623 Constructible and Single Pass Iterator, the following expressions are
 624 valid and respect the stated semantics.</p>
 625 <table border="1" class="docutils">
 626 <colgroup>
 627 <col width="38%" />
 628 <col width="34%" />
 629 <col width="27%" />
 630 </colgroup>
 631 <thead valign="bottom">
 632 <tr><th class="head" colspan="3">Forward Traversal Iterator Requirements (in addition to Default Constructible and Single Pass Iterator)</th>
 633 </tr>
 634 <tr><th class="head">Expression</th>
 635 <th class="head">Return Type</th>
 636 <th class="head">Assertion/Note</th>
 637 </tr>
 638 </thead>
 639 <tbody valign="top">
 640 <tr><td><tt class="docutils literal"><span class="pre">X</span> <span class="pre">u;</span></tt></td>
 641 <td><tt class="docutils literal"><span class="pre">X&amp;</span></tt></td>
 642 <td>note: <tt class="docutils literal"><span class="pre">u</span></tt> may have a
 643 singular value.</td>
 644 </tr>
 645 <tr><td><tt class="docutils literal"><span class="pre">++r</span></tt></td>
 646 <td><tt class="docutils literal"><span class="pre">X&amp;</span></tt></td>
 647 <td><tt class="docutils literal"><span class="pre">r</span> <span class="pre">==</span> <span class="pre">s</span></tt> and <tt class="docutils literal"><span class="pre">r</span></tt> is
 648 dereferenceable implies
 649 <tt class="docutils literal"><span class="pre">++r</span> <span class="pre">==</span> <span class="pre">++s.</span></tt></td>
 650 </tr>
 651 <tr><td><tt class="docutils literal"><span class="pre">iterator_traversal&lt;X&gt;::type</span></tt></td>
 652 <td>Convertible to
 653 <tt class="docutils literal"><span class="pre">forward_traversal_tag</span></tt></td>
 654 <td>&nbsp;</td>
 655 </tr>
 656 </tbody>
 657 </table>
 658 <!-- TR1: forward_traversal_iterator_tag changed to
 659 forward_traversal_tag for consistency -->
 660 </div>
 661 <div class="section" id="bidirectional-traversal-iterators-lib-bidirectional-traversal-iterators">
 662 <h4><a class="toc-backref" href="#id19">Bidirectional Traversal Iterators [lib.bidirectional.traversal.iterators]</a></h4>
 663 <p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Bidirectional Traversal
 664 Iterator</em> concept if, in addition to <tt class="docutils literal"><span class="pre">X</span></tt> meeting the requirements of
 665 Forward Traversal Iterator, the following expressions are valid and
 666 respect the stated semantics.</p>
 667 <table border="1" class="docutils">
 668 <colgroup>
 669 <col width="33%" />
 670 <col width="32%" />
 671 <col width="14%" />
 672 <col width="21%" />
 673 </colgroup>
 674 <thead valign="bottom">
 675 <tr><th class="head" colspan="4">Bidirectional Traversal Iterator Requirements (in addition to Forward Traversal
 676 Iterator)</th>
 677 </tr>
 678 <tr><th class="head">Expression</th>
 679 <th class="head">Return Type</th>
 680 <th class="head">Operational
 681 Semantics</th>
 682 <th class="head">Assertion/
 683 Pre-/Post-condition</th>
 684 </tr>
 685 </thead>
 686 <tbody valign="top">
 687 <tr><td><tt class="docutils literal"><span class="pre">--r</span></tt></td>
 688 <td><tt class="docutils literal"><span class="pre">X&amp;</span></tt></td>
 689 <td>&nbsp;</td>
 690 <td><p class="first">pre: there exists
 691 <tt class="docutils literal"><span class="pre">s</span></tt> such that <tt class="docutils literal"><span class="pre">r</span>
 692 <span class="pre">==</span> <span class="pre">++s</span></tt>.  post:
 693 <tt class="docutils literal"><span class="pre">s</span></tt> is
 694 dereferenceable.</p>
 695 <p class="last"><tt class="docutils literal"><span class="pre">++(--r)</span> <span class="pre">==</span> <span class="pre">r</span></tt>.
 696 <tt class="docutils literal"><span class="pre">--r</span> <span class="pre">==</span> <span class="pre">--s</span></tt>
 697 implies <tt class="docutils literal"><span class="pre">r</span> <span class="pre">==</span>
 698 <span class="pre">s</span></tt>. <tt class="docutils literal"><span class="pre">&amp;r</span> <span class="pre">==</span> <span class="pre">&amp;--r</span></tt>.</p>
 699 </td>
 700 </tr>
 701 <tr><td><tt class="docutils literal"><span class="pre">r--</span></tt></td>
 702 <td>convertible to <tt class="docutils literal"><span class="pre">const</span> <span class="pre">X&amp;</span></tt></td>
 703 <td><pre class="first last literal-block">
 704 {
 705   X tmp = r;
 706   --r;
 707   return tmp;
 708 }
 709 </pre>
 710 </td>
 711 <td>&nbsp;</td>
 712 </tr>
 713 <tr><td><tt class="docutils literal"><span class="pre">iterator_traversal&lt;X&gt;::type</span></tt></td>
 714 <td>Convertible to
 715 <tt class="docutils literal"><span class="pre">bidirectional_traversal_tag</span></tt></td>
 716 <td>&nbsp;</td>
 717 <td>&nbsp;</td>
 718 </tr>
 719 </tbody>
 720 </table>
 721 <!-- TR1: bidirectional_traversal_iterator_tag changed to
 722 bidirectional_traversal_tag for consistency -->
 723 </div>
 724 <div class="section" id="random-access-traversal-iterators-lib-random-access-traversal-iterators">
 725 <h4><a class="toc-backref" href="#id20">Random Access Traversal Iterators [lib.random.access.traversal.iterators]</a></h4>
 726 <p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Random Access Traversal
 727 Iterator</em> concept if the following expressions are valid and respect
 728 the stated semantics.  In the table below, <tt class="docutils literal"><span class="pre">Distance</span></tt> is
 729 <tt class="docutils literal"><span class="pre">iterator_traits&lt;X&gt;::difference_type</span></tt> and <tt class="docutils literal"><span class="pre">n</span></tt> represents a
 730 constant object of type <tt class="docutils literal"><span class="pre">Distance</span></tt>.</p>
 731 <table border="1" class="docutils">
 732 <colgroup>
 733 <col width="28%" />
 734 <col width="30%" />
 735 <col width="23%" />
 736 <col width="20%" />
 737 </colgroup>
 738 <thead valign="bottom">
 739 <tr><th class="head" colspan="4">Random Access Traversal Iterator Requirements (in addition to Bidirectional Traversal Iterator)</th>
 740 </tr>
 741 <tr><th class="head">Expression</th>
 742 <th class="head">Return Type</th>
 743 <th class="head">Operational Semantics</th>
 744 <th class="head">Assertion/
 745 Precondition</th>
 746 </tr>
 747 </thead>
 748 <tbody valign="top">
 749 <tr><td><tt class="docutils literal"><span class="pre">r</span> <span class="pre">+=</span> <span class="pre">n</span></tt></td>
 750 <td><tt class="docutils literal"><span class="pre">X&amp;</span></tt></td>
 751 <td><pre class="first last literal-block">
 752 {
 753   Distance m = n;
 754   if (m &gt;= 0)
 755     while (m--)
 756       ++r;
 757   else
 758     while (m++)
 759       --r;
 760   return r;
 761 }
 762 </pre>
 763 </td>
 764 <td>&nbsp;</td>
 765 </tr>
 766 <tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">+</span> <span class="pre">n</span></tt>, <tt class="docutils literal"><span class="pre">n</span> <span class="pre">+</span> <span class="pre">a</span></tt></td>
 767 <td><tt class="docutils literal"><span class="pre">X</span></tt></td>
 768 <td><tt class="docutils literal"><span class="pre">{</span> <span class="pre">X</span> <span class="pre">tmp</span> <span class="pre">=</span> <span class="pre">a;</span> <span class="pre">return</span> <span class="pre">tmp</span>
 769 <span class="pre">+=</span> <span class="pre">n;</span> <span class="pre">}</span></tt></td>
 770 <td>&nbsp;</td>
 771 </tr>
 772 <tr><td><tt class="docutils literal"><span class="pre">r</span> <span class="pre">-=</span> <span class="pre">n</span></tt></td>
 773 <td><tt class="docutils literal"><span class="pre">X&amp;</span></tt></td>
 774 <td><tt class="docutils literal"><span class="pre">return</span> <span class="pre">r</span> <span class="pre">+=</span> <span class="pre">-n</span></tt></td>
 775 <td>&nbsp;</td>
 776 </tr>
 777 <tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">-</span> <span class="pre">n</span></tt></td>
 778 <td><tt class="docutils literal"><span class="pre">X</span></tt></td>
 779 <td><tt class="docutils literal"><span class="pre">{</span> <span class="pre">X</span> <span class="pre">tmp</span> <span class="pre">=</span> <span class="pre">a;</span> <span class="pre">return</span> <span class="pre">tmp</span>
 780 <span class="pre">-=</span> <span class="pre">n;</span> <span class="pre">}</span></tt></td>
 781 <td>&nbsp;</td>
 782 </tr>
 783 <tr><td><tt class="docutils literal"><span class="pre">b</span> <span class="pre">-</span> <span class="pre">a</span></tt></td>
 784 <td><tt class="docutils literal"><span class="pre">Distance</span></tt></td>
 785 <td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">&lt;</span> <span class="pre">b</span> <span class="pre">?</span>&nbsp; <span class="pre">distance(a,b)</span>
 786 <span class="pre">:</span> <span class="pre">-distance(b,a)</span></tt></td>
 787 <td>pre: there exists a
 788 value <tt class="docutils literal"><span class="pre">n</span></tt> of
 789 <tt class="docutils literal"><span class="pre">Distance</span></tt> such that
 790 <tt class="docutils literal"><span class="pre">a</span> <span class="pre">+</span> <span class="pre">n</span> <span class="pre">==</span> <span class="pre">b</span></tt>.  <tt class="docutils literal"><span class="pre">b</span>
 791 <span class="pre">==</span> <span class="pre">a</span> <span class="pre">+</span> <span class="pre">(b</span> <span class="pre">-</span> <span class="pre">a)</span></tt>.</td>
 792 </tr>
 793 <tr><td><tt class="docutils literal"><span class="pre">a[n]</span></tt></td>
 794 <td>convertible to T</td>
 795 <td><tt class="docutils literal"><span class="pre">*(a</span> <span class="pre">+</span> <span class="pre">n)</span></tt></td>
 796 <td>pre: a is a <a class="reference internal" href="#readable-iterator">Readable
 797 Iterator</a></td>
 798 </tr>
 799 <tr><td><tt class="docutils literal"><span class="pre">a[n]</span> <span class="pre">=</span> <span class="pre">v</span></tt></td>
 800 <td>convertible to T</td>
 801 <td><tt class="docutils literal"><span class="pre">*(a</span> <span class="pre">+</span> <span class="pre">n)</span> <span class="pre">=</span> <span class="pre">v</span></tt></td>
 802 <td>pre: a is a <a class="reference internal" href="#writable-iterator">Writable
 803 Iterator</a></td>
 804 </tr>
 805 <tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">&lt;</span> <span class="pre">b</span></tt></td>
 806 <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
 807 <td><tt class="docutils literal"><span class="pre">b</span> <span class="pre">-</span> <span class="pre">a</span> <span class="pre">&gt;</span> <span class="pre">0</span></tt></td>
 808 <td><tt class="docutils literal"><span class="pre">&lt;</span></tt> is a total
 809 ordering relation</td>
 810 </tr>
 811 <tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">&gt;</span> <span class="pre">b</span></tt></td>
 812 <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
 813 <td><tt class="docutils literal"><span class="pre">b</span> <span class="pre">&lt;</span> <span class="pre">a</span></tt></td>
 814 <td><tt class="docutils literal"><span class="pre">&gt;</span></tt> is a total
 815 ordering relation</td>
 816 </tr>
 817 <tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">&gt;=</span> <span class="pre">b</span></tt></td>
 818 <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
 819 <td><tt class="docutils literal"><span class="pre">!(a</span> <span class="pre">&lt;</span> <span class="pre">b)</span></tt></td>
 820 <td>&nbsp;</td>
 821 </tr>
 822 <tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">&lt;=</span> <span class="pre">b</span></tt></td>
 823 <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
 824 <td><tt class="docutils literal"><span class="pre">!(a</span> <span class="pre">&gt;</span> <span class="pre">b)</span></tt></td>
 825 <td>&nbsp;</td>
 826 </tr>
 827 <tr><td><tt class="docutils literal"><span class="pre">iterator_traversal&lt;X&gt;::type</span></tt></td>
 828 <td>Convertible to
 829 <tt class="docutils literal"><span class="pre">random_access_traversal_tag</span></tt></td>
 830 <td>&nbsp;</td>
 831 <td>&nbsp;</td>
 832 </tr>
 833 </tbody>
 834 </table>
 835 <!-- TR1: random_access_traversal_iterator_tag changed to
 836 random_access_traversal_tag for consistency -->
 837 </div>
 838 <div class="section" id="interoperable-iterators-lib-interoperable-iterators">
 839 <h4><a class="toc-backref" href="#id21">Interoperable Iterators [lib.interoperable.iterators]</a></h4>
 840 <p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> that models Single Pass Iterator is
 841 <em>interoperable with</em> a class or built-in type <tt class="docutils literal"><span class="pre">Y</span></tt> that also models
 842 Single Pass Iterator if the following expressions are valid and
 843 respect the stated semantics. In the tables below, <tt class="docutils literal"><span class="pre">x</span></tt> is an object
 844 of type <tt class="docutils literal"><span class="pre">X</span></tt>, <tt class="docutils literal"><span class="pre">y</span></tt> is an object of type <tt class="docutils literal"><span class="pre">Y</span></tt>, <tt class="docutils literal"><span class="pre">Distance</span></tt> is
 845 <tt class="docutils literal"><span class="pre">iterator_traits&lt;Y&gt;::difference_type</span></tt>, and <tt class="docutils literal"><span class="pre">n</span></tt> represents a
 846 constant object of type <tt class="docutils literal"><span class="pre">Distance</span></tt>.</p>
 847 <table border="1" class="docutils">
 848 <colgroup>
 849 <col width="13%" />
 850 <col width="27%" />
 851 <col width="60%" />
 852 </colgroup>
 853 <thead valign="bottom">
 854 <tr><th class="head">Expression</th>
 855 <th class="head">Return Type</th>
 856 <th class="head">Assertion/Precondition/Postcondition</th>
 857 </tr>
 858 </thead>
 859 <tbody valign="top">
 860 <tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">=</span> <span class="pre">x</span></tt></td>
 861 <td><tt class="docutils literal"><span class="pre">Y</span></tt></td>
 862 <td>post: <tt class="docutils literal"><span class="pre">y</span> <span class="pre">==</span> <span class="pre">x</span></tt></td>
 863 </tr>
 864 <tr><td><tt class="docutils literal"><span class="pre">Y(x)</span></tt></td>
 865 <td><tt class="docutils literal"><span class="pre">Y</span></tt></td>
 866 <td>post: <tt class="docutils literal"><span class="pre">Y(x)</span> <span class="pre">==</span> <span class="pre">x</span></tt></td>
 867 </tr>
 868 <tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre">==</span> <span class="pre">y</span></tt></td>
 869 <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
 870 <td><tt class="docutils literal"><span class="pre">==</span></tt> is an equivalence relation over its domain.</td>
 871 </tr>
 872 <tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">==</span> <span class="pre">x</span></tt></td>
 873 <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
 874 <td><tt class="docutils literal"><span class="pre">==</span></tt> is an equivalence relation over its domain.</td>
 875 </tr>
 876 <tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre">!=</span> <span class="pre">y</span></tt></td>
 877 <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
 878 <td><tt class="docutils literal"><span class="pre">bool(a==b)</span> <span class="pre">!=</span> <span class="pre">bool(a!=b)</span></tt> over its domain.</td>
 879 </tr>
 880 <tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">!=</span> <span class="pre">x</span></tt></td>
 881 <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
 882 <td><tt class="docutils literal"><span class="pre">bool(a==b)</span> <span class="pre">!=</span> <span class="pre">bool(a!=b)</span></tt> over its domain.</td>
 883 </tr>
 884 </tbody>
 885 </table>
 886 <p>If <tt class="docutils literal"><span class="pre">X</span></tt> and <tt class="docutils literal"><span class="pre">Y</span></tt> both model Random Access Traversal Iterator then
 887 the following additional requirements must be met.</p>
 888 <table border="1" class="docutils">
 889 <colgroup>
 890 <col width="12%" />
 891 <col width="25%" />
 892 <col width="23%" />
 893 <col width="41%" />
 894 </colgroup>
 895 <thead valign="bottom">
 896 <tr><th class="head">Expression</th>
 897 <th class="head">Return Type</th>
 898 <th class="head">Operational Semantics</th>
 899 <th class="head">Assertion/ Precondition</th>
 900 </tr>
 901 </thead>
 902 <tbody valign="top">
 903 <tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre">&lt;</span> <span class="pre">y</span></tt></td>
 904 <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
 905 <td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">-</span> <span class="pre">x</span> <span class="pre">&gt;</span> <span class="pre">0</span></tt></td>
 906 <td><tt class="docutils literal"><span class="pre">&lt;</span></tt> is a total ordering relation</td>
 907 </tr>
 908 <tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">&lt;</span> <span class="pre">x</span></tt></td>
 909 <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
 910 <td><tt class="docutils literal"><span class="pre">x</span> <span class="pre">-</span> <span class="pre">y</span> <span class="pre">&gt;</span> <span class="pre">0</span></tt></td>
 911 <td><tt class="docutils literal"><span class="pre">&lt;</span></tt> is a total ordering relation</td>
 912 </tr>
 913 <tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre">&gt;</span> <span class="pre">y</span></tt></td>
 914 <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
 915 <td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">&lt;</span> <span class="pre">x</span></tt></td>
 916 <td><tt class="docutils literal"><span class="pre">&gt;</span></tt> is a total ordering relation</td>
 917 </tr>
 918 <tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">&gt;</span> <span class="pre">x</span></tt></td>
 919 <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
 920 <td><tt class="docutils literal"><span class="pre">x</span> <span class="pre">&lt;</span> <span class="pre">y</span></tt></td>
 921 <td><tt class="docutils literal"><span class="pre">&gt;</span></tt> is a total ordering relation</td>
 922 </tr>
 923 <tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre">&gt;=</span> <span class="pre">y</span></tt></td>
 924 <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
 925 <td><tt class="docutils literal"><span class="pre">!(x</span> <span class="pre">&lt;</span> <span class="pre">y)</span></tt></td>
 926 <td>&nbsp;</td>
 927 </tr>
 928 <tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">&gt;=</span> <span class="pre">x</span></tt></td>
 929 <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
 930 <td><tt class="docutils literal"><span class="pre">!(y</span> <span class="pre">&lt;</span> <span class="pre">x)</span></tt></td>
 931 <td>&nbsp;</td>
 932 </tr>
 933 <tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre">&lt;=</span> <span class="pre">y</span></tt></td>
 934 <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
 935 <td><tt class="docutils literal"><span class="pre">!(x</span> <span class="pre">&gt;</span> <span class="pre">y)</span></tt></td>
 936 <td>&nbsp;</td>
 937 </tr>
 938 <tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">&lt;=</span> <span class="pre">x</span></tt></td>
 939 <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
 940 <td><tt class="docutils literal"><span class="pre">!(y</span> <span class="pre">&gt;</span> <span class="pre">x)</span></tt></td>
 941 <td>&nbsp;</td>
 942 </tr>
 943 <tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">-</span> <span class="pre">x</span></tt></td>
 944 <td><tt class="docutils literal"><span class="pre">Distance</span></tt></td>
 945 <td><tt class="docutils literal"><span class="pre">distance(Y(x),y)</span></tt></td>
 946 <td>pre: there exists a value <tt class="docutils literal"><span class="pre">n</span></tt> of
 947 <tt class="docutils literal"><span class="pre">Distance</span></tt> such that <tt class="docutils literal"><span class="pre">x</span> <span class="pre">+</span> <span class="pre">n</span> <span class="pre">==</span> <span class="pre">y</span></tt>.
 948 <tt class="docutils literal"><span class="pre">y</span> <span class="pre">==</span> <span class="pre">x</span> <span class="pre">+</span> <span class="pre">(y</span> <span class="pre">-</span> <span class="pre">x)</span></tt>.</td>
 949 </tr>
 950 <tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre">-</span> <span class="pre">y</span></tt></td>
 951 <td><tt class="docutils literal"><span class="pre">Distance</span></tt></td>
 952 <td><tt class="docutils literal"><span class="pre">distance(y,Y(x))</span></tt></td>
 953 <td>pre: there exists a value <tt class="docutils literal"><span class="pre">n</span></tt> of
 954 <tt class="docutils literal"><span class="pre">Distance</span></tt> such that <tt class="docutils literal"><span class="pre">y</span> <span class="pre">+</span> <span class="pre">n</span> <span class="pre">==</span> <span class="pre">x</span></tt>.
 955 <tt class="docutils literal"><span class="pre">x</span> <span class="pre">==</span> <span class="pre">y</span> <span class="pre">+</span> <span class="pre">(x</span> <span class="pre">-</span> <span class="pre">y)</span></tt>.</td>
 956 </tr>
 957 </tbody>
 958 </table>
 959 </div>
 960 </div>
 961 </div>
 962 <div class="section" id="addition-to-lib-iterator-synopsis">
 963 <h2><a class="toc-backref" href="#id22">Addition to [lib.iterator.synopsis]</a></h2>
 964 <pre class="literal-block">
 965 // lib.iterator.traits, traits and tags
 966 template &lt;class Iterator&gt; struct is_readable_iterator;
 967 template &lt;class Iterator&gt; struct iterator_traversal;
 968
 969 struct incrementable_traversal_tag { };
 970 struct single_pass_traversal_tag : incrementable_traversal_tag { };
 971 struct forward_traversal_tag : single_pass_traversal_tag { };
 972 struct bidirectional_traversal_tag : forward_traversal_tag { };
 973 struct random_access_traversal_tag : bidirectional_traversal_tag { };
 974 </pre>
 975 </div>
 976 <div class="section" id="addition-to-lib-iterator-traits">
 977 <h2><a class="toc-backref" href="#id23">Addition to [lib.iterator.traits]</a></h2>
 978 <p>The <tt class="docutils literal"><span class="pre">is_readable_iterator</span></tt> class
 979 template satisfies the <a class="reference external" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1519.htm">UnaryTypeTrait</a> requirements.</p>
 980 <p>Given an iterator type <tt class="docutils literal"><span class="pre">X</span></tt>, <tt class="docutils literal"><span class="pre">is_readable_iterator&lt;X&gt;::value</span></tt>
 981 yields <tt class="docutils literal"><span class="pre">true</span></tt> if, for an object <tt class="docutils literal"><span class="pre">a</span></tt> of type <tt class="docutils literal"><span class="pre">X</span></tt>, <tt class="docutils literal"><span class="pre">*a</span></tt> is
 982 convertible to <tt class="docutils literal"><span class="pre">iterator_traits&lt;X&gt;::value_type</span></tt>, and <tt class="docutils literal"><span class="pre">false</span></tt>
 983 otherwise.</p>
 984 <p><tt class="docutils literal"><span class="pre">iterator_traversal&lt;X&gt;::type</span></tt> is</p>
 985 <pre class="literal-block">
 986 <em>category-to-traversal</em>(iterator_traits&lt;X&gt;::iterator_category)
 987 </pre>
 988 <p>where <em>category-to-traversal</em> is defined as follows</p>
 989 <pre class="literal-block" id="category-to-traversal">
 990 <em>category-to-traversal</em>(C) =
 991     if (C is convertible to incrementable_traversal_tag)
 992         return C;
 993     else if (C is convertible to random_access_iterator_tag)
 994         return random_access_traversal_tag;
 995     else if (C is convertible to bidirectional_iterator_tag)
 996         return bidirectional_traversal_tag;
 997     else if (C is convertible to forward_iterator_tag)
 998         return forward_traversal_tag;
 999     else if (C is convertible to input_iterator_tag)
1000         return single_pass_traversal_tag;
1001     else if (C is convertible to output_iterator_tag)
1002         return incrementable_traversal_tag;
1003     else
1004         <em>the program is ill-formed</em>
1005 </pre>
1006 </div>
1007 </div>
1008 <div class="section" id="footnotes">
1009 <h1><a class="toc-backref" href="#id24">Footnotes</a></h1>
1010 <p>The UnaryTypeTrait concept is defined in <a class="reference external" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1519.htm">n1519</a>; the LWG is
1011 considering adding the requirement that specializations are derived
1012 from their nested <tt class="docutils literal"><span class="pre">::type</span></tt>.</p>
1013 <!-- LocalWords:  Abrahams Siek Witt const bool Sutter's WG int UL LI href Lvalue
1014 LocalWords:  ReadableIterator WritableIterator SwappableIterator cv pre iter
1015 LocalWords:  ConstantLvalueIterator MutableLvalueIterator CopyConstructible TR
1016 LocalWords:  ForwardTraversalIterator BidirectionalTraversalIterator lvalue
1017 LocalWords:  RandomAccessTraversalIterator dereferenceable Incrementable tmp
1018 LocalWords:  incrementable xxx min prev inplace png oldeqnew AccessTag struct
1019 LocalWords:  TraversalTag typename lvalues DWA Hmm JGS mis enum -->
1020 </div>
1021 </div>
1022 <div class="footer">
1023 <hr class="footer" />
1024 <a class="reference external" href="new-iter-concepts.rst">View document source</a>.
1025 Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source.
1026
1027 </div>
1028 </body>
1029 </html>