+++ /dev/null
-<?xml version="1.0" encoding="utf-8" ?>
-<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
-<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
-<head>
-<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
-<meta name="generator" content="Docutils 0.5: http://docutils.sourceforge.net/" />
-<title>New Iterator Concepts</title>
-<meta name="author" content="David Abrahams, Jeremy Siek, Thomas Witt" />
-<meta name="organization" content="Boost Consulting, Indiana University Open Systems Lab, Zephyr Associates, Inc." />
-<meta name="date" content="2006-09-11" />
-<meta name="copyright" content="Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003." />
-<link rel="stylesheet" href="../../../rst.css" type="text/css" />
-</head>
-<body>
-<div class="document" id="new-iterator-concepts">
-<h1 class="title">New Iterator Concepts</h1>
-<table class="docinfo" frame="void" rules="none">
-<col class="docinfo-name" />
-<col class="docinfo-content" />
-<tbody valign="top">
-<tr><th class="docinfo-name">Author:</th>
-<td>David Abrahams, Jeremy Siek, Thomas Witt</td></tr>
-<tr><th class="docinfo-name">Contact:</th>
-<td><a class="first reference external" href="mailto:dave@boost-consulting.com">dave@boost-consulting.com</a>, <a class="reference external" href="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</a>, <a class="last reference external" href="mailto:witt@styleadvisor.com">witt@styleadvisor.com</a></td></tr>
-<tr><th class="docinfo-name">Organization:</th>
-<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
-Lab</a>, <a class="last reference external" href="http://www.styleadvisor.com">Zephyr Associates, Inc.</a></td></tr>
-<tr><th class="docinfo-name">Date:</th>
-<td>2006-09-11</td></tr>
-<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
-accepted for Technical Report 1 by the C++ standard
-committee's library working group. This proposal is a
-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>
-</tr>
-<tr><th class="docinfo-name">Copyright:</th>
-<td>Copyright David Abrahams, Jeremy Siek, and Thomas Witt
-2003.</td></tr>
-</tbody>
-</table>
-<!-- Distributed under the Boost -->
-<!-- Software License, Version 1.0. (See accompanying -->
-<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
-<!-- Version 1.25 of this ReStructuredText document is the same as
-n1550_, the paper accepted by the LWG. -->
-<table class="docutils field-list" frame="void" rules="none">
-<col class="field-name" />
-<col class="field-body" />
-<tbody valign="top">
-<tr class="field"><th class="field-name">Abstract:</th><td class="field-body">We propose a new system of iterator concepts that treat
-access and positioning independently. This allows the
-concepts to more closely match the requirements
-of algorithms and provides better categorizations
-of iterators that are used in practice.</td>
-</tr>
-</tbody>
-</table>
-<div class="contents topic" id="table-of-contents">
-<p class="topic-title first">Table of Contents</p>
-<ul class="simple">
-<li><a class="reference internal" href="#motivation" id="id1">Motivation</a></li>
-<li><a class="reference internal" href="#impact-on-the-standard" id="id2">Impact on the Standard</a><ul>
-<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>
-<li><a class="reference internal" href="#changes-to-algorithm-requirements" id="id4">Changes to Algorithm Requirements</a></li>
-<li><a class="reference internal" href="#deprecations" id="id5">Deprecations</a></li>
-<li><a class="reference internal" href="#vector-bool" id="id6"><tt class="docutils literal"><span class="pre">vector<bool></span></tt></a></li>
-</ul>
-</li>
-</ul>
-</li>
-<li><a class="reference internal" href="#design" id="id7">Design</a></li>
-<li><a class="reference internal" href="#proposed-text" id="id8">Proposed Text</a><ul>
-<li><a class="reference internal" href="#addition-to-lib-iterator-requirements" id="id9">Addition to [lib.iterator.requirements]</a><ul>
-<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>
-<li><a class="reference internal" href="#readable-iterators-lib-readable-iterators" id="id11">Readable Iterators [lib.readable.iterators]</a></li>
-<li><a class="reference internal" href="#writable-iterators-lib-writable-iterators" id="id12">Writable Iterators [lib.writable.iterators]</a></li>
-<li><a class="reference internal" href="#swappable-iterators-lib-swappable-iterators" id="id13">Swappable Iterators [lib.swappable.iterators]</a></li>
-<li><a class="reference internal" href="#lvalue-iterators-lib-lvalue-iterators" id="id14">Lvalue Iterators [lib.lvalue.iterators]</a></li>
-</ul>
-</li>
-<li><a class="reference internal" href="#iterator-traversal-concepts-lib-iterator-traversal" id="id15">Iterator Traversal Concepts [lib.iterator.traversal]</a><ul>
-<li><a class="reference internal" href="#incrementable-iterators-lib-incrementable-iterators" id="id16">Incrementable Iterators [lib.incrementable.iterators]</a></li>
-<li><a class="reference internal" href="#single-pass-iterators-lib-single-pass-iterators" id="id17">Single Pass Iterators [lib.single.pass.iterators]</a></li>
-<li><a class="reference internal" href="#forward-traversal-iterators-lib-forward-traversal-iterators" id="id18">Forward Traversal Iterators [lib.forward.traversal.iterators]</a></li>
-<li><a class="reference internal" href="#bidirectional-traversal-iterators-lib-bidirectional-traversal-iterators" id="id19">Bidirectional Traversal Iterators [lib.bidirectional.traversal.iterators]</a></li>
-<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>
-<li><a class="reference internal" href="#interoperable-iterators-lib-interoperable-iterators" id="id21">Interoperable Iterators [lib.interoperable.iterators]</a></li>
-</ul>
-</li>
-</ul>
-</li>
-<li><a class="reference internal" href="#addition-to-lib-iterator-synopsis" id="id22">Addition to [lib.iterator.synopsis]</a></li>
-<li><a class="reference internal" href="#addition-to-lib-iterator-traits" id="id23">Addition to [lib.iterator.traits]</a></li>
-</ul>
-</li>
-<li><a class="reference internal" href="#footnotes" id="id24">Footnotes</a></li>
-</ul>
-</div>
-<div class="section" id="motivation">
-<h1><a class="toc-backref" href="#id1">Motivation</a></h1>
-<p>The standard iterator categories and requirements are flawed because
-they use a single hierarchy of concepts to address two orthogonal
-issues: <em>iterator traversal</em> and <em>value access</em>. As a result, many
-algorithms with requirements expressed in terms of the iterator
-categories are too strict. Also, many real-world iterators can not be
-accurately categorized. A proxy-based iterator with random-access
-traversal, for example, may only legally have a category of "input
-iterator", so generic algorithms are unable to take advantage of its
-random-access capabilities. The current iterator concept hierarchy is
-geared towards iterator traversal (hence the category names), while
-requirements that address value access sneak in at various places. The
-following table gives a summary of the current value access
-requirements in the iterator categories.</p>
-<table border="1" class="docutils">
-<colgroup>
-<col width="31%" />
-<col width="69%" />
-</colgroup>
-<thead valign="bottom">
-<tr><th class="head" colspan="2">Value Access Requirements in Existing Iterator Categories</th>
-</tr>
-</thead>
-<tbody valign="top">
-<tr><td>Output Iterator</td>
-<td><tt class="docutils literal"><span class="pre">*i</span> <span class="pre">=</span> <span class="pre">a</span></tt></td>
-</tr>
-<tr><td>Input Iterator</td>
-<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>
-</tr>
-<tr><td>Forward Iterator</td>
-<td><tt class="docutils literal"><span class="pre">*i</span></tt> is <tt class="docutils literal"><span class="pre">T&</span></tt> (or <tt class="docutils literal"><span class="pre">const</span> <span class="pre">T&</span></tt> once <a class="reference external" href="http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#200">issue 200</a>
-is resolved)</td>
-</tr>
-<tr><td>Random Access Iterator</td>
-<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>
-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>
-is resolved)</td>
-</tr>
-</tbody>
-</table>
-<p>Because iterator traversal and value access are mixed together in a
-single hierarchy, many useful iterators can not be appropriately
-categorized. For example, <tt class="docutils literal"><span class="pre">vector<bool>::iterator</span></tt> is almost a
-random access iterator, but the return type is not <tt class="docutils literal"><span class="pre">bool&</span></tt> (see
-<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
-N1185). Therefore, the iterators of <tt class="docutils literal"><span class="pre">vector<bool></span></tt> only meet the
-requirements of input iterator and output iterator. This is so
-nonintuitive that the C++ standard contradicts itself on this point.
-In paragraph 23.2.4/1 it says that a <tt class="docutils literal"><span class="pre">vector</span></tt> is a sequence that
-supports random access iterators.</p>
-<p>Another difficult-to-categorize iterator is the transform iterator, an
-adaptor which applies a unary function object to the dereferenced
-value of the some underlying iterator (see <a class="reference external" href="http://www.boost.org/libs/utility/transform_iterator.htm">transform_iterator</a>).
-For unary functions such as <tt class="docutils literal"><span class="pre">times</span></tt>, the return type of
-<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
-object, which is typically not a reference. Because random access
-iterators are required to return lvalues from <tt class="docutils literal"><span class="pre">operator*</span></tt>, if you
-wrap <tt class="docutils literal"><span class="pre">int*</span></tt> with a transform iterator, you do not get a random
-access iterator as might be expected, but an input iterator.</p>
-<p>A third example is found in the vertex and edge iterators of the
-<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
-descriptors, which are lightweight handles created on-the-fly. They
-must be returned by-value. As a result, their current standard
-iterator category is <tt class="docutils literal"><span class="pre">input_iterator_tag</span></tt>, which means that,
-strictly speaking, you could not use these iterators with algorithms
-like <tt class="docutils literal"><span class="pre">min_element()</span></tt>. As a temporary solution, the concept
-<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
-edge descriptors, but as the design notes for the concept suggest, a
-better solution is needed.</p>
-<p>In short, there are many useful iterators that do not fit into the
-current standard iterator categories. As a result, the following bad
-things happen:</p>
-<ul class="simple">
-<li>Iterators are often mis-categorized.</li>
-<li>Algorithm requirements are more strict than necessary, because they
-cannot separate the need for random access or bidirectional
-traversal from the need for a true reference return type.</li>
-</ul>
-</div>
-<div class="section" id="impact-on-the-standard">
-<h1><a class="toc-backref" href="#id2">Impact on the Standard</a></h1>
-<p>This proposal for TR1 is a pure extension. Further, the new iterator
-concepts are backward-compatible with the old iterator requirements,
-and old iterators are forward-compatible with the new iterator
-concepts. That is to say, iterators that satisfy the old requirements
-also satisfy appropriate concepts in the new system, and iterators
-modeling the new concepts will automatically satisfy the appropriate
-old requirements.</p>
-<!-- I think we need to say something about the resolution to allow
-convertibility to any of the old-style tags as a TR issue (hope it
-made it). -DWA -->
-<!-- Hmm, not sure I understand. Are you talking about whether a
-standards conforming input iterator is allowed to have
-a tag that is not input_iterator_tag but that
-is convertible to input_iterator_tag? -JGS -->
-<div class="section" id="possible-but-not-proposed-changes-to-the-working-paper">
-<h2><a class="toc-backref" href="#id3">Possible (but not proposed) Changes to the Working Paper</a></h2>
-<p>The extensions in this paper suggest several changes we might make
-to the working paper for the next standard. These changes are not
-a formal part of this proposal for TR1.</p>
-<div class="section" id="changes-to-algorithm-requirements">
-<h3><a class="toc-backref" href="#id4">Changes to Algorithm Requirements</a></h3>
-<p>The algorithms in the standard library could benefit from the new
-iterator concepts because the new concepts provide a more accurate way
-to express their type requirements. The result is algorithms that are
-usable in more situations and have fewer type requirements.</p>
-<p>For the next working paper (but not for TR1), the committee should
-consider the following changes to the type requirements of algorithms.
-These changes are phrased as textual substitutions, listing the
-algorithms to which each textual substitution applies.</p>
-<p>Forward Iterator -> Forward Traversal Iterator and Readable Iterator</p>
-<blockquote>
-<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>
-<span class="pre">lower_bound,</span> <span class="pre">upper_bound,</span> <span class="pre">equal_range,</span> <span class="pre">binary_search,</span>
-<span class="pre">min_element,</span> <span class="pre">max_element</span></tt></blockquote>
-<p>Forward Iterator (1) -> Single Pass Iterator and Readable Iterator,
-Forward Iterator (2) -> Forward Traversal Iterator and Readable Iterator</p>
-<blockquote>
-<tt class="docutils literal"><span class="pre">find_first_of</span></tt></blockquote>
-<p>Forward Iterator -> Readable Iterator and Writable Iterator</p>
-<blockquote>
-<tt class="docutils literal"><span class="pre">iter_swap</span></tt></blockquote>
-<p>Forward Iterator -> Single Pass Iterator and Writable Iterator</p>
-<blockquote>
-<tt class="docutils literal"><span class="pre">fill,</span> <span class="pre">generate</span></tt></blockquote>
-<p>Forward Iterator -> Forward Traversal Iterator and Swappable Iterator</p>
-<blockquote>
-<tt class="docutils literal"><span class="pre">rotate</span></tt></blockquote>
-<p>Forward Iterator (1) -> Swappable Iterator and Single Pass Iterator,
-Forward Iterator (2) -> Swappable Iterator and Incrementable Iterator</p>
-<blockquote>
-<tt class="docutils literal"><span class="pre">swap_ranges</span></tt></blockquote>
-<dl class="docutils">
-<dt>Forward Iterator -> Forward Traversal Iterator and Readable Iterator and Writable Iterator</dt>
-<dd><tt class="docutils literal"><span class="pre">remove,</span> <span class="pre">remove_if,</span> <span class="pre">unique</span></tt></dd>
-</dl>
-<p>Forward Iterator -> Single Pass Iterator and Readable Iterator and Writable Iterator</p>
-<blockquote>
-<tt class="docutils literal"><span class="pre">replace,</span> <span class="pre">replace_if</span></tt></blockquote>
-<dl class="docutils">
-<dt>Bidirectional Iterator -> Bidirectional Traversal Iterator and Swappable Iterator</dt>
-<dd><tt class="docutils literal"><span class="pre">reverse</span></tt></dd>
-<dt>Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable and Swappable Iterator</dt>
-<dd><tt class="docutils literal"><span class="pre">partition</span></tt></dd>
-</dl>
-<p>Bidirectional Iterator (1) -> Bidirectional Traversal Iterator and Readable Iterator,
-Bidirectional Iterator (2) -> Bidirectional Traversal Iterator and Writable Iterator</p>
-<blockquote>
-<tt class="docutils literal"><span class="pre">copy_backwards</span></tt></blockquote>
-<dl class="docutils">
-<dt>Bidirectional Iterator -> Bidirectional Traversal Iterator and Swappable Iterator and Readable Iterator</dt>
-<dd><tt class="docutils literal"><span class="pre">next_permutation,</span> <span class="pre">prev_permutation</span></tt></dd>
-<dt>Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable Iterator and Writable Iterator</dt>
-<dd><tt class="docutils literal"><span class="pre">stable_partition,</span> <span class="pre">inplace_merge</span></tt></dd>
-<dt>Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable Iterator</dt>
-<dd><tt class="docutils literal"><span class="pre">reverse_copy</span></tt></dd>
-<dt>Random Access Iterator -> Random Access Traversal Iterator and Readable and Writable Iterator</dt>
-<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>
-<span class="pre">make_heap,</span> <span class="pre">sort_heap</span></tt></dd>
-<dt>Input Iterator (2) -> Incrementable Iterator and Readable Iterator</dt>
-<dd><tt class="docutils literal"><span class="pre">equal,</span> <span class="pre">mismatch</span></tt></dd>
-<dt>Input Iterator (2) -> Incrementable Iterator and Readable Iterator</dt>
-<dd><tt class="docutils literal"><span class="pre">transform</span></tt></dd>
-</dl>
-</div>
-<div class="section" id="deprecations">
-<h3><a class="toc-backref" href="#id5">Deprecations</a></h3>
-<p>For the next working paper (but not for TR1), the committee should
-consider deprecating the old iterator tags, and
-std::iterator_traits, since it will be superceded by individual
-traits metafunctions.</p>
-</div>
-<div class="section" id="vector-bool">
-<h3><a class="toc-backref" href="#id6"><tt class="docutils literal"><span class="pre">vector<bool></span></tt></a></h3>
-<p>For the next working paper (but not for TR1), the committee should
-consider reclassifying <tt class="docutils literal"><span class="pre">vector<bool>::iterator</span></tt> as a Random
-Access Traversal Iterator and Readable Iterator and Writable
-Iterator.</p>
-</div>
-</div>
-</div>
-<div class="section" id="design">
-<h1><a class="toc-backref" href="#id7">Design</a></h1>
-<p>The iterator requirements are to be separated into two groups. One set
-of concepts handles the syntax and semantics of value access:</p>
-<ul class="simple">
-<li>Readable Iterator</li>
-<li>Writable Iterator</li>
-<li>Swappable Iterator</li>
-<li>Lvalue Iterator</li>
-</ul>
-<p>The access concepts describe requirements related to <tt class="docutils literal"><span class="pre">operator*</span></tt> and
-<tt class="docutils literal"><span class="pre">operator-></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
-<tt class="docutils literal"><span class="pre">pointer</span></tt> associated types.</p>
-<p>The other set of concepts handles traversal:</p>
-<ul class="simple">
-<li>Incrementable Iterator</li>
-<li>Single Pass Iterator</li>
-<li>Forward Traversal Iterator</li>
-<li>Bidirectional Traversal Iterator</li>
-<li>Random Access Traversal Iterator</li>
-</ul>
-<p>The refinement relationships for the traversal concepts are in the
-following diagram.</p>
-<img alt="traversal.png" src="traversal.png" />
-<p>In addition to the iterator movement operators, such as
-<tt class="docutils literal"><span class="pre">operator++</span></tt>, the traversal concepts also include requirements on
-position comparison such as <tt class="docutils literal"><span class="pre">operator==</span></tt> and <tt class="docutils literal"><span class="pre">operator<</span></tt>. The
-reason for the fine grain slicing of the concepts into the
-Incrementable and Single Pass is to provide concepts that are exact
-matches with the original input and output iterator requirements.</p>
-<p>This proposal also includes a concept for specifying when an iterator
-is interoperable with another iterator, in the sense that <tt class="docutils literal"><span class="pre">int*</span></tt> is
-interoperable with <tt class="docutils literal"><span class="pre">int</span> <span class="pre">const*</span></tt>.</p>
-<ul class="simple">
-<li>Interoperable Iterators</li>
-</ul>
-<p>The relationship between the new iterator concepts and the old are
-given in the following diagram.</p>
-<img alt="oldeqnew.png" src="oldeqnew.png" />
-<p>Like the old iterator requirements, we provide tags for purposes of
-dispatching based on the traversal concepts. The tags are related via
-inheritance so that a tag is convertible to another tag if the concept
-associated with the first tag is a refinement of the second tag.</p>
-<p>Our design reuses <tt class="docutils literal"><span class="pre">iterator_traits<Iter>::iterator_category</span></tt> to
-indicate an iterator's traversal capability. To specify
-capabilities not captured by any old-style iterator category, an
-iterator designer can use an <tt class="docutils literal"><span class="pre">iterator_category</span></tt> type that is
-convertible to both the the most-derived old iterator category tag
-which fits, and the appropriate new iterator traversal tag.</p>
-<!-- dwa2003/1/2: Note that we are not *requiring* convertibility to
-a new-style traversal tag in order to meet new concepts.
-Old-style iterators still fit, after all. -->
-<p>We do not provide tags for the purposes of dispatching based on the
-access concepts, in part because we could not find a way to
-automatically infer the right access tags for old-style iterators.
-An iterator's writability may be dependent on the assignability of
-its <tt class="docutils literal"><span class="pre">value_type</span></tt> and there's no known way to detect whether an
-arbitrary type is assignable. Fortunately, the need for
-dispatching based on access capability is not as great as the need
-for dispatching based on traversal capability.</p>
-<p>A difficult design decision concerned the <tt class="docutils literal"><span class="pre">operator[]</span></tt>. The direct
-approach for specifying <tt class="docutils literal"><span class="pre">operator[]</span></tt> would have a return type of
-<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
-direction would mean that an iterator satisfying the old Random Access
-Iterator requirements would not necessarily be a model of Readable or
-Writable Lvalue Iterator. Instead we have chosen a design that
-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
-only required to return something convertible to the <tt class="docutils literal"><span class="pre">value_type</span></tt>
-(for a Readable Iterator), and is required to support assignment
-<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>
-</div>
-<div class="section" id="proposed-text">
-<h1><a class="toc-backref" href="#id8">Proposed Text</a></h1>
-<div class="section" id="addition-to-lib-iterator-requirements">
-<h2><a class="toc-backref" href="#id9">Addition to [lib.iterator.requirements]</a></h2>
-<div class="section" id="iterator-value-access-concepts-lib-iterator-value-access">
-<h3><a class="toc-backref" href="#id10">Iterator Value Access Concepts [lib.iterator.value.access]</a></h3>
-<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
-object of type <tt class="docutils literal"><span class="pre">X</span></tt>, <tt class="docutils literal"><span class="pre">R</span></tt> is
-<tt class="docutils literal"><span class="pre">std::iterator_traits<X>::reference</span></tt>, <tt class="docutils literal"><span class="pre">T</span></tt> is
-<tt class="docutils literal"><span class="pre">std::iterator_traits<X>::value_type</span></tt>, and <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>
-<div class="section" id="readable-iterators-lib-readable-iterators">
-<span id="readable-iterator"></span><h4><a class="toc-backref" href="#id11">Readable Iterators [lib.readable.iterators]</a></h4>
-<p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Readable Iterator</em> concept
-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
-Copy Constructible, the following expressions are valid and respect
-the stated semantics. <tt class="docutils literal"><span class="pre">U</span></tt> is the type of any specified member of
-type <tt class="docutils literal"><span class="pre">T</span></tt>.</p>
-<table border="1" class="docutils">
-<colgroup>
-<col width="28%" />
-<col width="20%" />
-<col width="52%" />
-</colgroup>
-<thead valign="bottom">
-<tr><th class="head" colspan="3">Readable Iterator Requirements (in addition to Assignable and Copy Constructible)</th>
-</tr>
-<tr><th class="head">Expression</th>
-<th class="head">Return Type</th>
-<th class="head">Note/Precondition</th>
-</tr>
-</thead>
-<tbody valign="top">
-<tr><td><tt class="docutils literal"><span class="pre">iterator_traits<X>::value_type</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">T</span></tt></td>
-<td>Any non-reference,
-non-cv-qualified type</td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">*a</span></tt></td>
-<td>Convertible to <tt class="docutils literal"><span class="pre">T</span></tt></td>
-<td><dl class="first last docutils">
-<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>
-<dd>is equivalent to <tt class="docutils literal"><span class="pre">*b</span></tt>.</dd>
-</dl>
-</td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">a->m</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">U&</span></tt></td>
-<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>
-</tr>
-</tbody>
-</table>
-<!-- We won't say anything about iterator_traits<X>::reference until the DR is resolved. -JGS -->
-</div>
-<div class="section" id="writable-iterators-lib-writable-iterators">
-<span id="writable-iterator"></span><h4><a class="toc-backref" href="#id12">Writable Iterators [lib.writable.iterators]</a></h4>
-<p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Writable Iterator</em> concept
-if, in addition to <tt class="docutils literal"><span class="pre">X</span></tt> being Copy Constructible, the following
-expressions are valid and respect the stated semantics. Writable
-Iterators have an associated <em>set of value types</em>.</p>
-<table border="1" class="docutils">
-<colgroup>
-<col width="37%" />
-<col width="21%" />
-<col width="42%" />
-</colgroup>
-<thead valign="bottom">
-<tr><th class="head" colspan="3">Writable Iterator Requirements (in addition to Copy Constructible)</th>
-</tr>
-<tr><th class="head">Expression</th>
-<th class="head">Return Type</th>
-<th class="head">Precondition</th>
-</tr>
-</thead>
-<tbody valign="top">
-<tr><td><tt class="docutils literal"><span class="pre">*a</span> <span class="pre">=</span> <span class="pre">o</span></tt></td>
-<td> </td>
-<td>pre: The type of <tt class="docutils literal"><span class="pre">o</span></tt>
-is in the set of
-value types of <tt class="docutils literal"><span class="pre">X</span></tt></td>
-</tr>
-</tbody>
-</table>
-</div>
-<div class="section" id="swappable-iterators-lib-swappable-iterators">
-<h4><a class="toc-backref" href="#id13">Swappable Iterators [lib.swappable.iterators]</a></h4>
-<p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Swappable Iterator</em> concept
-if, in addition to <tt class="docutils literal"><span class="pre">X</span></tt> being Copy Constructible, the following
-expressions are valid and respect the stated semantics.</p>
-<table border="1" class="docutils">
-<colgroup>
-<col width="37%" />
-<col width="19%" />
-<col width="43%" />
-</colgroup>
-<thead valign="bottom">
-<tr><th class="head" colspan="3">Swappable Iterator Requirements (in addition to Copy Constructible)</th>
-</tr>
-<tr><th class="head">Expression</th>
-<th class="head">Return Type</th>
-<th class="head">Postcondition</th>
-</tr>
-</thead>
-<tbody valign="top">
-<tr><td><tt class="docutils literal"><span class="pre">iter_swap(a,</span> <span class="pre">b)</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">void</span></tt></td>
-<td>the pointed to values are
-exchanged</td>
-</tr>
-</tbody>
-</table>
-<p>[<em>Note:</em> An iterator that is a model of the <a class="reference internal" href="#readable-iterator">Readable Iterator</a> and
-<a class="reference internal" href="#writable-iterator">Writable Iterator</a> concepts is also a model of <em>Swappable
-Iterator</em>. <em>--end note</em>]</p>
-</div>
-<div class="section" id="lvalue-iterators-lib-lvalue-iterators">
-<h4><a class="toc-backref" href="#id14">Lvalue Iterators [lib.lvalue.iterators]</a></h4>
-<p>The <em>Lvalue Iterator</em> concept adds the requirement that the return
-type of <tt class="docutils literal"><span class="pre">operator*</span></tt> type be a reference to the value type of the
-iterator.</p>
-<table border="1" class="docutils">
-<colgroup>
-<col width="22%" />
-<col width="19%" />
-<col width="59%" />
-</colgroup>
-<thead valign="bottom">
-<tr><th class="head" colspan="3">Lvalue Iterator Requirements</th>
-</tr>
-<tr><th class="head">Expression</th>
-<th class="head">Return Type</th>
-<th class="head">Note/Assertion</th>
-</tr>
-</thead>
-<tbody valign="top">
-<tr><td><tt class="docutils literal"><span class="pre">*a</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">T&</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">T</span></tt> is <em>cv</em>
-<tt class="docutils literal"><span class="pre">iterator_traits<X>::value_type</span></tt>
-where <em>cv</em> is an optional
-cv-qualification. pre: <tt class="docutils literal"><span class="pre">a</span></tt> is
-dereferenceable.</td>
-</tr>
-</tbody>
-</table>
-<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
-<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
-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
-<tt class="docutils literal"><span class="pre">*b</span></tt>.</p>
-</div>
-</div>
-<div class="section" id="iterator-traversal-concepts-lib-iterator-traversal">
-<h3><a class="toc-backref" href="#id15">Iterator Traversal Concepts [lib.iterator.traversal]</a></h3>
-<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
-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
-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<X>::value_type</span></tt>, and
-<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>
-<div class="section" id="incrementable-iterators-lib-incrementable-iterators">
-<h4><a class="toc-backref" href="#id16">Incrementable Iterators [lib.incrementable.iterators]</a></h4>
-<p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Incrementable Iterator</em>
-concept if, in addition to <tt class="docutils literal"><span class="pre">X</span></tt> being Assignable and Copy
-Constructible, the following expressions are valid and respect the
-stated semantics.</p>
-<table border="1" class="docutils">
-<colgroup>
-<col width="39%" />
-<col width="38%" />
-<col width="23%" />
-</colgroup>
-<thead valign="bottom">
-<tr><th class="head" colspan="3">Incrementable Iterator Requirements (in addition to Assignable, Copy Constructible)</th>
-</tr>
-<tr><th class="head">Expression</th>
-<th class="head">Return Type</th>
-<th class="head">Assertion</th>
-</tr>
-</thead>
-<tbody valign="top">
-<tr><td><tt class="docutils literal"><span class="pre">++r</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">X&</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">&r</span> <span class="pre">==</span> <span class="pre">&++r</span></tt></td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">r++</span></tt></td>
-<td> </td>
-<td> </td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">*r++</span></tt></td>
-<td> </td>
-<td> </td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">iterator_traversal<X>::type</span></tt></td>
-<td>Convertible to
-<tt class="docutils literal"><span class="pre">incrementable_traversal_tag</span></tt></td>
-<td> </td>
-</tr>
-</tbody>
-</table>
-<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
-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
-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>.
-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
-to <tt class="docutils literal"><span class="pre">T</span> <span class="pre">z(*r);</span> <span class="pre">++r;</span></tt>.</p>
-<!-- TR1: incrementable_iterator_tag changed to
-incrementable_traversal_tag for consistency. -->
-</div>
-<div class="section" id="single-pass-iterators-lib-single-pass-iterators">
-<h4><a class="toc-backref" href="#id17">Single Pass Iterators [lib.single.pass.iterators]</a></h4>
-<p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Single Pass Iterator</em>
-concept if the following expressions are valid and respect the stated
-semantics.</p>
-<table border="1" class="docutils">
-<colgroup>
-<col width="37%" />
-<col width="27%" />
-<col width="12%" />
-<col width="25%" />
-</colgroup>
-<thead valign="bottom">
-<tr><th class="head" colspan="4">Single Pass Iterator Requirements (in addition to Incrementable Iterator and Equality
-Comparable)</th>
-</tr>
-<tr><th class="head">Expression</th>
-<th class="head">Return Type</th>
-<th class="head">Operational
-Semantics</th>
-<th class="head">Assertion/
-Pre-/Post-condition</th>
-</tr>
-</thead>
-<tbody valign="top">
-<tr><td><tt class="docutils literal"><span class="pre">++r</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">X&</span></tt></td>
-<td> </td>
-<td>pre: <tt class="docutils literal"><span class="pre">r</span></tt> is
-dereferenceable; post:
-<tt class="docutils literal"><span class="pre">r</span></tt> is dereferenceable or
-<tt class="docutils literal"><span class="pre">r</span></tt> is past-the-end</td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">==</span> <span class="pre">b</span></tt></td>
-<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
-<td> </td>
-<td><tt class="docutils literal"><span class="pre">==</span></tt> is an equivalence
-relation over its domain</td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">!=</span> <span class="pre">b</span></tt></td>
-<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">!(a</span> <span class="pre">==</span> <span class="pre">b)</span></tt></td>
-<td> </td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">iterator_traits<X>::difference_type</span></tt></td>
-<td>A signed integral type
-representing the distance
-between iterators</td>
-<td> </td>
-<td> </td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">iterator_traversal<X>::type</span></tt></td>
-<td>Convertible to
-<tt class="docutils literal"><span class="pre">single_pass_traversal_tag</span></tt></td>
-<td> </td>
-<td> </td>
-</tr>
-</tbody>
-</table>
-<!-- TR1: single_pass_iterator_tag changed to
-single_pass_traversal_tag for consistency -->
-</div>
-<div class="section" id="forward-traversal-iterators-lib-forward-traversal-iterators">
-<h4><a class="toc-backref" href="#id18">Forward Traversal Iterators [lib.forward.traversal.iterators]</a></h4>
-<p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Forward Traversal Iterator</em>
-concept if, in addition to <tt class="docutils literal"><span class="pre">X</span></tt> meeting the requirements of Default
-Constructible and Single Pass Iterator, the following expressions are
-valid and respect the stated semantics.</p>
-<table border="1" class="docutils">
-<colgroup>
-<col width="38%" />
-<col width="34%" />
-<col width="27%" />
-</colgroup>
-<thead valign="bottom">
-<tr><th class="head" colspan="3">Forward Traversal Iterator Requirements (in addition to Default Constructible and Single Pass Iterator)</th>
-</tr>
-<tr><th class="head">Expression</th>
-<th class="head">Return Type</th>
-<th class="head">Assertion/Note</th>
-</tr>
-</thead>
-<tbody valign="top">
-<tr><td><tt class="docutils literal"><span class="pre">X</span> <span class="pre">u;</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">X&</span></tt></td>
-<td>note: <tt class="docutils literal"><span class="pre">u</span></tt> may have a
-singular value.</td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">++r</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">X&</span></tt></td>
-<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
-dereferenceable implies
-<tt class="docutils literal"><span class="pre">++r</span> <span class="pre">==</span> <span class="pre">++s.</span></tt></td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">iterator_traversal<X>::type</span></tt></td>
-<td>Convertible to
-<tt class="docutils literal"><span class="pre">forward_traversal_tag</span></tt></td>
-<td> </td>
-</tr>
-</tbody>
-</table>
-<!-- TR1: forward_traversal_iterator_tag changed to
-forward_traversal_tag for consistency -->
-</div>
-<div class="section" id="bidirectional-traversal-iterators-lib-bidirectional-traversal-iterators">
-<h4><a class="toc-backref" href="#id19">Bidirectional Traversal Iterators [lib.bidirectional.traversal.iterators]</a></h4>
-<p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Bidirectional Traversal
-Iterator</em> concept if, in addition to <tt class="docutils literal"><span class="pre">X</span></tt> meeting the requirements of
-Forward Traversal Iterator, the following expressions are valid and
-respect the stated semantics.</p>
-<table border="1" class="docutils">
-<colgroup>
-<col width="33%" />
-<col width="32%" />
-<col width="14%" />
-<col width="21%" />
-</colgroup>
-<thead valign="bottom">
-<tr><th class="head" colspan="4">Bidirectional Traversal Iterator Requirements (in addition to Forward Traversal
-Iterator)</th>
-</tr>
-<tr><th class="head">Expression</th>
-<th class="head">Return Type</th>
-<th class="head">Operational
-Semantics</th>
-<th class="head">Assertion/
-Pre-/Post-condition</th>
-</tr>
-</thead>
-<tbody valign="top">
-<tr><td><tt class="docutils literal"><span class="pre">--r</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">X&</span></tt></td>
-<td> </td>
-<td><p class="first">pre: there exists
-<tt class="docutils literal"><span class="pre">s</span></tt> such that <tt class="docutils literal"><span class="pre">r</span>
-<span class="pre">==</span> <span class="pre">++s</span></tt>. post:
-<tt class="docutils literal"><span class="pre">s</span></tt> is
-dereferenceable.</p>
-<p class="last"><tt class="docutils literal"><span class="pre">++(--r)</span> <span class="pre">==</span> <span class="pre">r</span></tt>.
-<tt class="docutils literal"><span class="pre">--r</span> <span class="pre">==</span> <span class="pre">--s</span></tt>
-implies <tt class="docutils literal"><span class="pre">r</span> <span class="pre">==</span>
-<span class="pre">s</span></tt>. <tt class="docutils literal"><span class="pre">&r</span> <span class="pre">==</span> <span class="pre">&--r</span></tt>.</p>
-</td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">r--</span></tt></td>
-<td>convertible to <tt class="docutils literal"><span class="pre">const</span> <span class="pre">X&</span></tt></td>
-<td><pre class="first last literal-block">
-{
- X tmp = r;
- --r;
- return tmp;
-}
-</pre>
-</td>
-<td> </td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">iterator_traversal<X>::type</span></tt></td>
-<td>Convertible to
-<tt class="docutils literal"><span class="pre">bidirectional_traversal_tag</span></tt></td>
-<td> </td>
-<td> </td>
-</tr>
-</tbody>
-</table>
-<!-- TR1: bidirectional_traversal_iterator_tag changed to
-bidirectional_traversal_tag for consistency -->
-</div>
-<div class="section" id="random-access-traversal-iterators-lib-random-access-traversal-iterators">
-<h4><a class="toc-backref" href="#id20">Random Access Traversal Iterators [lib.random.access.traversal.iterators]</a></h4>
-<p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Random Access Traversal
-Iterator</em> concept if the following expressions are valid and respect
-the stated semantics. In the table below, <tt class="docutils literal"><span class="pre">Distance</span></tt> is
-<tt class="docutils literal"><span class="pre">iterator_traits<X>::difference_type</span></tt> and <tt class="docutils literal"><span class="pre">n</span></tt> represents a
-constant object of type <tt class="docutils literal"><span class="pre">Distance</span></tt>.</p>
-<table border="1" class="docutils">
-<colgroup>
-<col width="28%" />
-<col width="30%" />
-<col width="23%" />
-<col width="20%" />
-</colgroup>
-<thead valign="bottom">
-<tr><th class="head" colspan="4">Random Access Traversal Iterator Requirements (in addition to Bidirectional Traversal Iterator)</th>
-</tr>
-<tr><th class="head">Expression</th>
-<th class="head">Return Type</th>
-<th class="head">Operational Semantics</th>
-<th class="head">Assertion/
-Precondition</th>
-</tr>
-</thead>
-<tbody valign="top">
-<tr><td><tt class="docutils literal"><span class="pre">r</span> <span class="pre">+=</span> <span class="pre">n</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">X&</span></tt></td>
-<td><pre class="first last literal-block">
-{
- Distance m = n;
- if (m >= 0)
- while (m--)
- ++r;
- else
- while (m++)
- --r;
- return r;
-}
-</pre>
-</td>
-<td> </td>
-</tr>
-<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>
-<td><tt class="docutils literal"><span class="pre">X</span></tt></td>
-<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>
-<span class="pre">+=</span> <span class="pre">n;</span> <span class="pre">}</span></tt></td>
-<td> </td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">r</span> <span class="pre">-=</span> <span class="pre">n</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">X&</span></tt></td>
-<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>
-<td> </td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">-</span> <span class="pre">n</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">X</span></tt></td>
-<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>
-<span class="pre">-=</span> <span class="pre">n;</span> <span class="pre">}</span></tt></td>
-<td> </td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">b</span> <span class="pre">-</span> <span class="pre">a</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">Distance</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">a</span> <span class="pre"><</span> <span class="pre">b</span> <span class="pre">?</span> <span class="pre">distance(a,b)</span>
-<span class="pre">:</span> <span class="pre">-distance(b,a)</span></tt></td>
-<td>pre: there exists a
-value <tt class="docutils literal"><span class="pre">n</span></tt> of
-<tt class="docutils literal"><span class="pre">Distance</span></tt> such that
-<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>
-<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>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">a[n]</span></tt></td>
-<td>convertible to T</td>
-<td><tt class="docutils literal"><span class="pre">*(a</span> <span class="pre">+</span> <span class="pre">n)</span></tt></td>
-<td>pre: a is a <a class="reference internal" href="#readable-iterator">Readable
-Iterator</a></td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">a[n]</span> <span class="pre">=</span> <span class="pre">v</span></tt></td>
-<td>convertible to T</td>
-<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>
-<td>pre: a is a <a class="reference internal" href="#writable-iterator">Writable
-Iterator</a></td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre"><</span> <span class="pre">b</span></tt></td>
-<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">b</span> <span class="pre">-</span> <span class="pre">a</span> <span class="pre">></span> <span class="pre">0</span></tt></td>
-<td><tt class="docutils literal"><span class="pre"><</span></tt> is a total
-ordering relation</td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">></span> <span class="pre">b</span></tt></td>
-<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">b</span> <span class="pre"><</span> <span class="pre">a</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">></span></tt> is a total
-ordering relation</td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">>=</span> <span class="pre">b</span></tt></td>
-<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">!(a</span> <span class="pre"><</span> <span class="pre">b)</span></tt></td>
-<td> </td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre"><=</span> <span class="pre">b</span></tt></td>
-<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">!(a</span> <span class="pre">></span> <span class="pre">b)</span></tt></td>
-<td> </td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">iterator_traversal<X>::type</span></tt></td>
-<td>Convertible to
-<tt class="docutils literal"><span class="pre">random_access_traversal_tag</span></tt></td>
-<td> </td>
-<td> </td>
-</tr>
-</tbody>
-</table>
-<!-- TR1: random_access_traversal_iterator_tag changed to
-random_access_traversal_tag for consistency -->
-</div>
-<div class="section" id="interoperable-iterators-lib-interoperable-iterators">
-<h4><a class="toc-backref" href="#id21">Interoperable Iterators [lib.interoperable.iterators]</a></h4>
-<p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> that models Single Pass Iterator is
-<em>interoperable with</em> a class or built-in type <tt class="docutils literal"><span class="pre">Y</span></tt> that also models
-Single Pass Iterator if the following expressions are valid and
-respect the stated semantics. In the tables below, <tt class="docutils literal"><span class="pre">x</span></tt> is an object
-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
-<tt class="docutils literal"><span class="pre">iterator_traits<Y>::difference_type</span></tt>, and <tt class="docutils literal"><span class="pre">n</span></tt> represents a
-constant object of type <tt class="docutils literal"><span class="pre">Distance</span></tt>.</p>
-<table border="1" class="docutils">
-<colgroup>
-<col width="13%" />
-<col width="27%" />
-<col width="60%" />
-</colgroup>
-<thead valign="bottom">
-<tr><th class="head">Expression</th>
-<th class="head">Return Type</th>
-<th class="head">Assertion/Precondition/Postcondition</th>
-</tr>
-</thead>
-<tbody valign="top">
-<tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">=</span> <span class="pre">x</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">Y</span></tt></td>
-<td>post: <tt class="docutils literal"><span class="pre">y</span> <span class="pre">==</span> <span class="pre">x</span></tt></td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">Y(x)</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">Y</span></tt></td>
-<td>post: <tt class="docutils literal"><span class="pre">Y(x)</span> <span class="pre">==</span> <span class="pre">x</span></tt></td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre">==</span> <span class="pre">y</span></tt></td>
-<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">==</span></tt> is an equivalence relation over its domain.</td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">==</span> <span class="pre">x</span></tt></td>
-<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">==</span></tt> is an equivalence relation over its domain.</td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre">!=</span> <span class="pre">y</span></tt></td>
-<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
-<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>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">!=</span> <span class="pre">x</span></tt></td>
-<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
-<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>
-</tr>
-</tbody>
-</table>
-<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
-the following additional requirements must be met.</p>
-<table border="1" class="docutils">
-<colgroup>
-<col width="12%" />
-<col width="25%" />
-<col width="23%" />
-<col width="41%" />
-</colgroup>
-<thead valign="bottom">
-<tr><th class="head">Expression</th>
-<th class="head">Return Type</th>
-<th class="head">Operational Semantics</th>
-<th class="head">Assertion/ Precondition</th>
-</tr>
-</thead>
-<tbody valign="top">
-<tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre"><</span> <span class="pre">y</span></tt></td>
-<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
-<td><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">0</span></tt></td>
-<td><tt class="docutils literal"><span class="pre"><</span></tt> is a total ordering relation</td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre"><</span> <span class="pre">x</span></tt></td>
-<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
-<td><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">0</span></tt></td>
-<td><tt class="docutils literal"><span class="pre"><</span></tt> is a total ordering relation</td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre">></span> <span class="pre">y</span></tt></td>
-<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">y</span> <span class="pre"><</span> <span class="pre">x</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">></span></tt> is a total ordering relation</td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">></span> <span class="pre">x</span></tt></td>
-<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">x</span> <span class="pre"><</span> <span class="pre">y</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">></span></tt> is a total ordering relation</td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre">>=</span> <span class="pre">y</span></tt></td>
-<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">!(x</span> <span class="pre"><</span> <span class="pre">y)</span></tt></td>
-<td> </td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">>=</span> <span class="pre">x</span></tt></td>
-<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">!(y</span> <span class="pre"><</span> <span class="pre">x)</span></tt></td>
-<td> </td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre"><=</span> <span class="pre">y</span></tt></td>
-<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">!(x</span> <span class="pre">></span> <span class="pre">y)</span></tt></td>
-<td> </td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre"><=</span> <span class="pre">x</span></tt></td>
-<td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">!(y</span> <span class="pre">></span> <span class="pre">x)</span></tt></td>
-<td> </td>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">-</span> <span class="pre">x</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">Distance</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">distance(Y(x),y)</span></tt></td>
-<td>pre: there exists a value <tt class="docutils literal"><span class="pre">n</span></tt> of
-<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>.
-<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>
-</tr>
-<tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre">-</span> <span class="pre">y</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">Distance</span></tt></td>
-<td><tt class="docutils literal"><span class="pre">distance(y,Y(x))</span></tt></td>
-<td>pre: there exists a value <tt class="docutils literal"><span class="pre">n</span></tt> of
-<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>.
-<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>
-</tr>
-</tbody>
-</table>
-</div>
-</div>
-</div>
-<div class="section" id="addition-to-lib-iterator-synopsis">
-<h2><a class="toc-backref" href="#id22">Addition to [lib.iterator.synopsis]</a></h2>
-<pre class="literal-block">
-// lib.iterator.traits, traits and tags
-template <class Iterator> struct is_readable_iterator;
-template <class Iterator> struct iterator_traversal;
-
-struct incrementable_traversal_tag { };
-struct single_pass_traversal_tag : incrementable_traversal_tag { };
-struct forward_traversal_tag : single_pass_traversal_tag { };
-struct bidirectional_traversal_tag : forward_traversal_tag { };
-struct random_access_traversal_tag : bidirectional_traversal_tag { };
-</pre>
-</div>
-<div class="section" id="addition-to-lib-iterator-traits">
-<h2><a class="toc-backref" href="#id23">Addition to [lib.iterator.traits]</a></h2>
-<p>The <tt class="docutils literal"><span class="pre">is_readable_iterator</span></tt> class
-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>
-<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<X>::value</span></tt>
-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
-convertible to <tt class="docutils literal"><span class="pre">iterator_traits<X>::value_type</span></tt>, and <tt class="docutils literal"><span class="pre">false</span></tt>
-otherwise.</p>
-<p><tt class="docutils literal"><span class="pre">iterator_traversal<X>::type</span></tt> is</p>
-<pre class="literal-block">
-<em>category-to-traversal</em>(iterator_traits<X>::iterator_category)
-</pre>
-<p>where <em>category-to-traversal</em> is defined as follows</p>
-<pre class="literal-block" id="category-to-traversal">
-<em>category-to-traversal</em>(C) =
- if (C is convertible to incrementable_traversal_tag)
- return C;
- else if (C is convertible to random_access_iterator_tag)
- return random_access_traversal_tag;
- else if (C is convertible to bidirectional_iterator_tag)
- return bidirectional_traversal_tag;
- else if (C is convertible to forward_iterator_tag)
- return forward_traversal_tag;
- else if (C is convertible to input_iterator_tag)
- return single_pass_traversal_tag;
- else if (C is convertible to output_iterator_tag)
- return incrementable_traversal_tag;
- else
- <em>the program is ill-formed</em>
-</pre>
-</div>
-</div>
-<div class="section" id="footnotes">
-<h1><a class="toc-backref" href="#id24">Footnotes</a></h1>
-<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
-considering adding the requirement that specializations are derived
-from their nested <tt class="docutils literal"><span class="pre">::type</span></tt>.</p>
-<!-- LocalWords: Abrahams Siek Witt const bool Sutter's WG int UL LI href Lvalue
-LocalWords: ReadableIterator WritableIterator SwappableIterator cv pre iter
-LocalWords: ConstantLvalueIterator MutableLvalueIterator CopyConstructible TR
-LocalWords: ForwardTraversalIterator BidirectionalTraversalIterator lvalue
-LocalWords: RandomAccessTraversalIterator dereferenceable Incrementable tmp
-LocalWords: incrementable xxx min prev inplace png oldeqnew AccessTag struct
-LocalWords: TraversalTag typename lvalues DWA Hmm JGS mis enum -->
-</div>
-</div>
-<div class="footer">
-<hr class="footer" />
-<a class="reference external" href="new-iter-concepts.rst">View document source</a>.
-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.
-
-</div>
-</body>
-</html>
projects / ceph.git / blobdiff