Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/iterator/doc/facade-and-adaptor.html @ 30

Last change on this file since 30 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 156.9 KB
Line 
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>Iterator Facade and Adaptor</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<link rel="stylesheet" href="../../../rst.css" type="text/css" />
12</head>
13<body>
14<div class="document" id="iterator-facade-and-adaptor">
15<h1 class="title">Iterator Facade and Adaptor</h1>
16<table class="docinfo" frame="void" rules="none">
17<col class="docinfo-name" />
18<col class="docinfo-content" />
19<tbody valign="top">
20<tr><th class="docinfo-name">Author:</th>
21<td>David Abrahams, Jeremy Siek, Thomas Witt</td></tr>
22<tr><th class="docinfo-name">Contact:</th>
23<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>
24<tr><th class="docinfo-name">Organization:</th>
25<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
26Lab</a>, <a class="last reference external" href="http://www.styleadvisor.com">Zephyr Associates, Inc.</a></td></tr>
27<tr><th class="docinfo-name">Date:</th>
28<td>2006-09-11</td></tr>
29<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://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1530.html">N1530</a>=03-0113, which was
30accepted for Technical Report 1 by the C++ standard
31committee's library working group.</td>
32</tr>
33</tbody>
34</table>
35<!-- Distributed under the Boost -->
36<!-- Software License, Version 1.0. (See accompanying -->
37<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
38<!-- Version 1.9 of this ReStructuredText document corresponds to
39n1530_, the paper accepted by the LWG. -->
40<table class="docutils field-list" frame="void" rules="none">
41<col class="field-name" />
42<col class="field-body" />
43<tbody valign="top">
44<tr class="field"><th class="field-name">copyright:</th><td class="field-body">Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003.</td>
45</tr>
46</tbody>
47</table>
48<table class="docutils field-list" frame="void" rules="none">
49<col class="field-name" />
50<col class="field-body" />
51<tbody valign="top">
52<tr class="field"><th class="field-name">abstract:</th><td class="field-body">We propose a set of class templates that help programmers
53build standard-conforming iterators, both from scratch and
54by adapting other iterators.</td>
55</tr>
56</tbody>
57</table>
58<div class="contents topic" id="table-of-contents">
59<p class="topic-title first">Table of Contents</p>
60<ul class="simple">
61<li><a class="reference internal" href="#motivation" id="id15">Motivation</a></li>
62<li><a class="reference internal" href="#impact-on-the-standard" id="id16">Impact on the Standard</a></li>
63<li><a class="reference internal" href="#design" id="id17">Design</a><ul>
64<li><a class="reference internal" href="#iterator-concepts" id="id18">Iterator Concepts</a></li>
65<li><a class="reference internal" href="#interoperability" id="id19">Interoperability</a></li>
66<li><a class="reference internal" href="#iterator-facade" id="id20">Iterator Facade</a><ul>
67<li><a class="reference internal" href="#usage" id="id21">Usage</a></li>
68<li><a class="reference internal" href="#iterator-core-access" id="id22">Iterator Core Access</a></li>
69<li><a class="reference internal" href="#operator" id="id23"><tt class="docutils literal"><span class="pre">operator[]</span></tt></a></li>
70<li><a class="reference internal" href="#id6" id="id24"><tt class="docutils literal"><span class="pre">operator-&gt;</span></tt></a></li>
71</ul>
72</li>
73<li><a class="reference internal" href="#iterator-adaptor" id="id25">Iterator Adaptor</a></li>
74<li><a class="reference internal" href="#specialized-adaptors" id="id26">Specialized Adaptors</a></li>
75</ul>
76</li>
77<li><a class="reference internal" href="#proposed-text" id="id27">Proposed Text</a><ul>
78<li><a class="reference internal" href="#header-iterator-helper-synopsis-lib-iterator-helper-synopsis" id="id28">Header <tt class="docutils literal"><span class="pre">&lt;iterator_helper&gt;</span></tt> synopsis    [lib.iterator.helper.synopsis]</a></li>
79<li><a class="reference internal" href="#iterator-facade-lib-iterator-facade" id="id29">Iterator facade [lib.iterator.facade]</a><ul>
80<li><a class="reference internal" href="#class-template-iterator-facade" id="id30">Class template <tt class="docutils literal"><span class="pre">iterator_facade</span></tt></a></li>
81<li><a class="reference internal" href="#iterator-facade-requirements" id="id31"><tt class="docutils literal"><span class="pre">iterator_facade</span></tt> Requirements</a></li>
82<li><a class="reference internal" href="#iterator-facade-operations" id="id32"><tt class="docutils literal"><span class="pre">iterator_facade</span></tt> operations</a></li>
83</ul>
84</li>
85<li><a class="reference internal" href="#iterator-adaptor-lib-iterator-adaptor" id="id33">Iterator adaptor [lib.iterator.adaptor]</a><ul>
86<li><a class="reference internal" href="#class-template-iterator-adaptor" id="id34">Class template <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt></a></li>
87<li><a class="reference internal" href="#iterator-adaptor-requirements" id="id35"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> requirements</a></li>
88<li><a class="reference internal" href="#iterator-adaptor-base-class-parameters" id="id36"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> base class parameters</a></li>
89<li><a class="reference internal" href="#iterator-adaptor-public-operations" id="id37"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> public operations</a></li>
90<li><a class="reference internal" href="#iterator-adaptor-protected-member-functions" id="id38"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> protected member functions</a></li>
91<li><a class="reference internal" href="#iterator-adaptor-private-member-functions" id="id39"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> private member functions</a></li>
92</ul>
93</li>
94<li><a class="reference internal" href="#specialized-adaptors-lib-iterator-special-adaptors" id="id40">Specialized adaptors [lib.iterator.special.adaptors]</a><ul>
95<li><a class="reference internal" href="#indirect-iterator" id="id41">Indirect iterator</a><ul>
96<li><a class="reference internal" href="#class-template-pointee" id="id42">Class template <tt class="docutils literal"><span class="pre">pointee</span></tt></a></li>
97<li><a class="reference internal" href="#class-template-indirect-reference" id="id43">Class template <tt class="docutils literal"><span class="pre">indirect_reference</span></tt></a></li>
98<li><a class="reference internal" href="#class-template-indirect-iterator" id="id44">Class template <tt class="docutils literal"><span class="pre">indirect_iterator</span></tt></a></li>
99<li><a class="reference internal" href="#indirect-iterator-requirements" id="id45"><tt class="docutils literal"><span class="pre">indirect_iterator</span></tt> requirements</a></li>
100<li><a class="reference internal" href="#indirect-iterator-models" id="id46"><tt class="docutils literal"><span class="pre">indirect_iterator</span></tt> models</a></li>
101<li><a class="reference internal" href="#indirect-iterator-operations" id="id47"><tt class="docutils literal"><span class="pre">indirect_iterator</span></tt> operations</a></li>
102</ul>
103</li>
104<li><a class="reference internal" href="#reverse-iterator" id="id48">Reverse iterator</a><ul>
105<li><a class="reference internal" href="#class-template-reverse-iterator" id="id49">Class template <tt class="docutils literal"><span class="pre">reverse_iterator</span></tt></a></li>
106<li><a class="reference internal" href="#reverse-iterator-requirements" id="id50"><tt class="docutils literal"><span class="pre">reverse_iterator</span></tt> requirements</a></li>
107<li><a class="reference internal" href="#reverse-iterator-models" id="id51"><tt class="docutils literal"><span class="pre">reverse_iterator</span></tt> models</a></li>
108<li><a class="reference internal" href="#reverse-iterator-operations" id="id52"><tt class="docutils literal"><span class="pre">reverse_iterator</span></tt> operations</a></li>
109</ul>
110</li>
111<li><a class="reference internal" href="#transform-iterator" id="id53">Transform iterator</a><ul>
112<li><a class="reference internal" href="#class-template-transform-iterator" id="id54">Class template <tt class="docutils literal"><span class="pre">transform_iterator</span></tt></a></li>
113<li><a class="reference internal" href="#transform-iterator-requirements" id="id55"><tt class="docutils literal"><span class="pre">transform_iterator</span></tt> requirements</a></li>
114<li><a class="reference internal" href="#transform-iterator-models" id="id56"><tt class="docutils literal"><span class="pre">transform_iterator</span></tt> models</a></li>
115<li><a class="reference internal" href="#transform-iterator-operations" id="id57"><tt class="docutils literal"><span class="pre">transform_iterator</span></tt> operations</a></li>
116</ul>
117</li>
118<li><a class="reference internal" href="#filter-iterator" id="id58">Filter iterator</a><ul>
119<li><a class="reference internal" href="#class-template-filter-iterator" id="id59">Class template <tt class="docutils literal"><span class="pre">filter_iterator</span></tt></a></li>
120<li><a class="reference internal" href="#filter-iterator-requirements" id="id60"><tt class="docutils literal"><span class="pre">filter_iterator</span></tt> requirements</a></li>
121<li><a class="reference internal" href="#filter-iterator-models" id="id61"><tt class="docutils literal"><span class="pre">filter_iterator</span></tt> models</a></li>
122<li><a class="reference internal" href="#filter-iterator-operations" id="id62"><tt class="docutils literal"><span class="pre">filter_iterator</span></tt> operations</a></li>
123</ul>
124</li>
125<li><a class="reference internal" href="#counting-iterator" id="id63">Counting iterator</a><ul>
126<li><a class="reference internal" href="#class-template-counting-iterator" id="id64">Class template <tt class="docutils literal"><span class="pre">counting_iterator</span></tt></a></li>
127<li><a class="reference internal" href="#counting-iterator-requirements" id="id65"><tt class="docutils literal"><span class="pre">counting_iterator</span></tt> requirements</a></li>
128<li><a class="reference internal" href="#counting-iterator-models" id="id66"><tt class="docutils literal"><span class="pre">counting_iterator</span></tt> models</a></li>
129<li><a class="reference internal" href="#counting-iterator-operations" id="id67"><tt class="docutils literal"><span class="pre">counting_iterator</span></tt> operations</a></li>
130</ul>
131</li>
132<li><a class="reference internal" href="#function-output-iterator" id="id68">Function output iterator</a><ul>
133<li><a class="reference internal" href="#class-template-function-output-iterator" id="id69">Class template <tt class="docutils literal"><span class="pre">function_output_iterator</span></tt></a></li>
134<li><a class="reference internal" href="#header" id="id70">Header</a></li>
135<li><a class="reference internal" href="#function-output-iterator-requirements" id="id71"><tt class="docutils literal"><span class="pre">function_output_iterator</span></tt> requirements</a></li>
136<li><a class="reference internal" href="#function-output-iterator-models" id="id72"><tt class="docutils literal"><span class="pre">function_output_iterator</span></tt> models</a></li>
137<li><a class="reference internal" href="#function-output-iterator-operations" id="id73"><tt class="docutils literal"><span class="pre">function_output_iterator</span></tt> operations</a></li>
138</ul>
139</li>
140</ul>
141</li>
142</ul>
143</li>
144</ul>
145</div>
146<div class="section" id="motivation">
147<h1><a class="toc-backref" href="#id15">Motivation</a></h1>
148<p>Iterators play an important role in modern C++ programming. The
149iterator is the central abstraction of the algorithms of the Standard
150Library, allowing algorithms to be re-used in in a wide variety of
151contexts.  The C++ Standard Library contains a wide variety of useful
152iterators. Every one of the standard containers comes with constant
153and mutable iterators<a class="footnote-reference" href="#mutable" id="id1"><sup>2</sup></a>, and also reverse versions of those
154same iterators which traverse the container in the opposite direction.
155The Standard also supplies <tt class="docutils literal"><span class="pre">istream_iterator</span></tt> and
156<tt class="docutils literal"><span class="pre">ostream_iterator</span></tt> for reading from and writing to streams,
157<tt class="docutils literal"><span class="pre">insert_iterator</span></tt>, <tt class="docutils literal"><span class="pre">front_insert_iterator</span></tt> and
158<tt class="docutils literal"><span class="pre">back_insert_iterator</span></tt> for inserting elements into containers, and
159<tt class="docutils literal"><span class="pre">raw_storage_iterator</span></tt> for initializing raw memory [7].</p>
160<p>Despite the many iterators supplied by the Standard Library, obvious
161and useful iterators are missing, and creating new iterator types is
162still a common task for C++ programmers.  The literature documents
163several of these, for example line_iterator [3] and Constant_iterator
164[9].  The iterator abstraction is so powerful that we expect
165programmers will always need to invent new iterator types.</p>
166<p>Although it is easy to create iterators that <em>almost</em> conform to the
167standard, the iterator requirements contain subtleties which can make
168creating an iterator which <em>actually</em> conforms quite difficult.
169Further, the iterator interface is rich, containing many operators
170that are technically redundant and tedious to implement.  To automate
171the repetitive work of constructing iterators, we propose
172<tt class="docutils literal"><span class="pre">iterator_facade</span></tt>, an iterator base class template which provides
173the rich interface of standard iterators and delegates its
174implementation to member functions of the derived class.  In addition
175to reducing the amount of code necessary to create an iterator, the
176<tt class="docutils literal"><span class="pre">iterator_facade</span></tt> also provides compile-time error detection.
177Iterator implementation mistakes that often go unnoticed are turned
178into compile-time errors because the derived class implementation must
179match the expectations of the <tt class="docutils literal"><span class="pre">iterator_facade</span></tt>.</p>
180<p>A common pattern of iterator construction is the adaptation of one
181iterator to form a new one.  The functionality of an iterator is
182composed of four orthogonal aspects: traversal, indirection, equality
183comparison and distance measurement.  Adapting an old iterator to
184create a new one often saves work because one can reuse one aspect of
185functionality while redefining the other.  For example, the Standard
186provides <tt class="docutils literal"><span class="pre">reverse_iterator</span></tt>, which adapts any Bidirectional Iterator
187by inverting its direction of traversal.  As with plain iterators,
188iterator adaptors defined outside the Standard have become commonplace
189in the literature:</p>
190<ul class="simple">
191<li>Checked iter[13] adds bounds-checking to an existing iterator.</li>
192<li>The iterators of the View Template Library[14], which adapts
193containers, are themselves adaptors over the underlying iterators.</li>
194<li>Smart iterators [5] adapt an iterator's dereferencing behavior by
195applying a function object to the object being referenced and
196returning the result.</li>
197<li>Custom iterators [4], in which a variety of adaptor types are enumerated.</li>
198<li>Compound iterators [1], which access a slice out of a container of containers.</li>
199<li>Several iterator adaptors from the MTL [12].  The MTL contains a
200strided iterator, where each call to <tt class="docutils literal"><span class="pre">operator++()</span></tt> moves the
201iterator ahead by some constant factor, and a scaled iterator, which
202multiplies the dereferenced value by some constant.</li>
203</ul>
204<table class="docutils footnote" frame="void" id="concept" rules="none">
205<colgroup><col class="label" /><col /></colgroup>
206<tbody valign="top">
207<tr><td class="label">[1]</td><td>We use the term concept to mean a set of requirements
208that a type must satisfy to be used with a particular template
209parameter.</td></tr>
210</tbody>
211</table>
212<table class="docutils footnote" frame="void" id="mutable" rules="none">
213<colgroup><col class="label" /><col /></colgroup>
214<tbody valign="top">
215<tr><td class="label"><a class="fn-backref" href="#id1">[2]</a></td><td>The term mutable iterator refers to iterators over objects that
216can be changed by assigning to the dereferenced iterator, while
217constant iterator refers to iterators over objects that cannot be
218modified.</td></tr>
219</tbody>
220</table>
221<p>To fulfill the need for constructing adaptors, we propose the
222<tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> class template.  Instantiations of
223<tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> serve as a base classes for new iterators,
224providing the default behavior of forwarding all operations to the
225underlying iterator.  The user can selectively replace these features
226in the derived iterator class.  This proposal also includes a number
227of more specialized adaptors, such as the <tt class="docutils literal"><span class="pre">transform_iterator</span></tt> that
228applies some user-specified function during the dereference of the
229iterator.</p>
230</div>
231<div class="section" id="impact-on-the-standard">
232<h1><a class="toc-backref" href="#id16">Impact on the Standard</a></h1>
233<p>This proposal is purely an addition to the C++ standard library.
234However, note that this proposal relies on the proposal for New
235Iterator Concepts.</p>
236</div>
237<div class="section" id="design">
238<h1><a class="toc-backref" href="#id17">Design</a></h1>
239<div class="section" id="iterator-concepts">
240<h2><a class="toc-backref" href="#id18">Iterator Concepts</a></h2>
241<p>This proposal is formulated in terms of the new <tt class="docutils literal"><span class="pre">iterator</span> <span class="pre">concepts</span></tt>
242as proposed in <a class="reference external" href="http://anubis.dkuug.dk/JTC1/SC22/WG21/docs/papers/2003/n1550.html">n1550</a>, since user-defined and especially adapted
243iterators suffer from the well known categorization problems that are
244inherent to the current iterator categories.</p>
245<p>This proposal does not strictly depend on proposal <a class="reference external" href="http://anubis.dkuug.dk/JTC1/SC22/WG21/docs/papers/2003/n1550.html">n1550</a>, as there
246is a direct mapping between new and old categories. This proposal
247could be reformulated using this mapping if <a class="reference external" href="http://anubis.dkuug.dk/JTC1/SC22/WG21/docs/papers/2003/n1550.html">n1550</a> was not accepted.</p>
248</div>
249<div class="section" id="interoperability">
250<h2><a class="toc-backref" href="#id19">Interoperability</a></h2>
251<p>The question of iterator interoperability is poorly addressed in the
252current standard.  There are currently two defect reports that are
253concerned with interoperability issues.</p>
254<p>Issue <a class="reference external" href="http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#179">179</a> concerns the fact that mutable container iterator types
255are only required to be convertible to the corresponding constant
256iterator types, but objects of these types are not required to
257interoperate in comparison or subtraction expressions.  This situation
258is tedious in practice and out of line with the way built in types
259work.  This proposal implements the proposed resolution to issue
260<a class="reference external" href="http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#179">179</a>, as most standard library implementations do nowadays. In other
261words, if an iterator type A has an implicit or user defined
262conversion to an iterator type B, the iterator types are interoperable
263and the usual set of operators are available.</p>
264<p>Issue <a class="reference external" href="http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#280">280</a> concerns the current lack of interoperability between
265reverse iterator types. The proposed new reverse_iterator template
266fixes the issues raised in 280. It provides the desired
267interoperability without introducing unwanted overloads.</p>
268</div>
269<div class="section" id="iterator-facade">
270<h2><a class="toc-backref" href="#id20">Iterator Facade</a></h2>
271<!-- Distributed under the Boost -->
272<!-- Software License, Version 1.0. (See accompanying -->
273<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
274<!-- Version 1.1 of this ReStructuredText document corresponds to
275n1530_, the paper accepted by the LWG for TR1. -->
276<!-- Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003. -->
277<p>While the iterator interface is rich, there is a core subset of the
278interface that is necessary for all the functionality.  We have
279identified the following core behaviors for iterators:</p>
280<ul class="simple">
281<li>dereferencing</li>
282<li>incrementing</li>
283<li>decrementing</li>
284<li>equality comparison</li>
285<li>random-access motion</li>
286<li>distance measurement</li>
287</ul>
288<p>In addition to the behaviors listed above, the core interface elements
289include the associated types exposed through iterator traits:
290<tt class="docutils literal"><span class="pre">value_type</span></tt>, <tt class="docutils literal"><span class="pre">reference</span></tt>, <tt class="docutils literal"><span class="pre">difference_type</span></tt>, and
291<tt class="docutils literal"><span class="pre">iterator_category</span></tt>.</p>
292<p>Iterator facade uses the Curiously Recurring Template
293Pattern (CRTP) <a class="citation-reference" href="#cop95" id="id4">[Cop95]</a> so that the user can specify the behavior
294of <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> in a derived class.  Former designs used
295policy objects to specify the behavior, but that approach was
296discarded for several reasons:</p>
297<blockquote>
298<ol class="arabic simple">
299<li>the creation and eventual copying of the policy object may create
300overhead that can be avoided with the current approach.</li>
301<li>The policy object approach does not allow for custom constructors
302on the created iterator types, an essential feature if
303<tt class="docutils literal"><span class="pre">iterator_facade</span></tt> should be used in other library
304implementations.</li>
305<li>Without the use of CRTP, the standard requirement that an
306iterator's <tt class="docutils literal"><span class="pre">operator++</span></tt> returns the iterator type itself
307would mean that all iterators built with the library would
308have to be specializations of <tt class="docutils literal"><span class="pre">iterator_facade&lt;...&gt;</span></tt>, rather
309than something more descriptive like
310<tt class="docutils literal"><span class="pre">indirect_iterator&lt;T*&gt;</span></tt>.  Cumbersome type generator
311metafunctions would be needed to build new parameterized
312iterators, and a separate <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> layer would be
313impossible.</li>
314</ol>
315</blockquote>
316<div class="section" id="usage">
317<h3><a class="toc-backref" href="#id21">Usage</a></h3>
318<p>The user of <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> derives his iterator class from a
319specialization of <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> and passes the derived
320iterator class as <tt class="docutils literal"><span class="pre">iterator_facade</span></tt>'s first template parameter.
321The order of the other template parameters have been carefully
322chosen to take advantage of useful defaults.  For example, when
323defining a constant lvalue iterator, the user can pass a
324const-qualified version of the iterator's <tt class="docutils literal"><span class="pre">value_type</span></tt> as
325<tt class="docutils literal"><span class="pre">iterator_facade</span></tt>'s <tt class="docutils literal"><span class="pre">Value</span></tt> parameter and omit the
326<tt class="docutils literal"><span class="pre">Reference</span></tt> parameter which follows.</p>
327<p>The derived iterator class must define member functions implementing
328the iterator's core behaviors.  The following table describes
329expressions which are required to be valid depending on the category
330of the derived iterator type.  These member functions are described
331briefly below and in more detail in the iterator facade
332requirements.</p>
333<blockquote>
334<table border="1" class="docutils">
335<colgroup>
336<col width="44%" />
337<col width="56%" />
338</colgroup>
339<thead valign="bottom">
340<tr><th class="head">Expression</th>
341<th class="head">Effects</th>
342</tr>
343</thead>
344<tbody valign="top">
345<tr><td><tt class="docutils literal"><span class="pre">i.dereference()</span></tt></td>
346<td>Access the value referred to</td>
347</tr>
348<tr><td><tt class="docutils literal"><span class="pre">i.equal(j)</span></tt></td>
349<td>Compare for equality with <tt class="docutils literal"><span class="pre">j</span></tt></td>
350</tr>
351<tr><td><tt class="docutils literal"><span class="pre">i.increment()</span></tt></td>
352<td>Advance by one position</td>
353</tr>
354<tr><td><tt class="docutils literal"><span class="pre">i.decrement()</span></tt></td>
355<td>Retreat by one position</td>
356</tr>
357<tr><td><tt class="docutils literal"><span class="pre">i.advance(n)</span></tt></td>
358<td>Advance by <tt class="docutils literal"><span class="pre">n</span></tt> positions</td>
359</tr>
360<tr><td><tt class="docutils literal"><span class="pre">i.distance_to(j)</span></tt></td>
361<td>Measure the distance to <tt class="docutils literal"><span class="pre">j</span></tt></td>
362</tr>
363</tbody>
364</table>
365</blockquote>
366<!-- Should we add a comment that a zero overhead implementation of iterator_facade
367is possible with proper inlining? -->
368<p>In addition to implementing the core interface functions, an iterator
369derived from <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> typically defines several
370constructors. To model any of the standard iterator concepts, the
371iterator must at least have a copy constructor. Also, if the iterator
372type <tt class="docutils literal"><span class="pre">X</span></tt> is meant to be automatically interoperate with another
373iterator type <tt class="docutils literal"><span class="pre">Y</span></tt> (as with constant and mutable iterators) then
374there must be an implicit conversion from <tt class="docutils literal"><span class="pre">X</span></tt> to <tt class="docutils literal"><span class="pre">Y</span></tt> or from <tt class="docutils literal"><span class="pre">Y</span></tt>
375to <tt class="docutils literal"><span class="pre">X</span></tt> (but not both), typically implemented as a conversion
376constructor. Finally, if the iterator is to model Forward Traversal
377Iterator or a more-refined iterator concept, a default constructor is
378required.</p>
379</div>
380<div class="section" id="iterator-core-access">
381<h3><a class="toc-backref" href="#id22">Iterator Core Access</a></h3>
382<p><tt class="docutils literal"><span class="pre">iterator_facade</span></tt> and the operator implementations need to be able
383to access the core member functions in the derived class.  Making the
384core member functions public would expose an implementation detail to
385the user.  The design used here ensures that implementation details do
386not appear in the public interface of the derived iterator type.</p>
387<p>Preventing direct access to the core member functions has two
388advantages.  First, there is no possibility for the user to accidently
389use a member function of the iterator when a member of the value_type
390was intended.  This has been an issue with smart pointer
391implementations in the past.  The second and main advantage is that
392library implementers can freely exchange a hand-rolled iterator
393implementation for one based on <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> without fear of
394breaking code that was accessing the public core member functions
395directly.</p>
396<p>In a naive implementation, keeping the derived class' core member
397functions private would require it to grant friendship to
398<tt class="docutils literal"><span class="pre">iterator_facade</span></tt> and each of the seven operators.  In order to
399reduce the burden of limiting access, <tt class="docutils literal"><span class="pre">iterator_core_access</span></tt> is
400provided, a class that acts as a gateway to the core member functions
401in the derived iterator class.  The author of the derived class only
402needs to grant friendship to <tt class="docutils literal"><span class="pre">iterator_core_access</span></tt> to make his core
403member functions available to the library.</p>
404<!-- This is no long uptodate -thw -->
405<!-- Yes it is; I made sure of it! -DWA -->
406<p><tt class="docutils literal"><span class="pre">iterator_core_access</span></tt> will be typically implemented as an empty
407class containing only private static member functions which invoke the
408iterator core member functions. There is, however, no need to
409standardize the gateway protocol.  Note that even if
410<tt class="docutils literal"><span class="pre">iterator_core_access</span></tt> used public member functions it would not
411open a safety loophole, as every core member function preserves the
412invariants of the iterator.</p>
413</div>
414<div class="section" id="operator">
415<h3><a class="toc-backref" href="#id23"><tt class="docutils literal"><span class="pre">operator[]</span></tt></a></h3>
416<p>The indexing operator for a generalized iterator presents special
417challenges.  A random access iterator's <tt class="docutils literal"><span class="pre">operator[]</span></tt> is only
418required to return something convertible to its <tt class="docutils literal"><span class="pre">value_type</span></tt>.
419Requiring that it return an lvalue would rule out currently-legal
420random-access iterators which hold the referenced value in a data
421member (e.g. <a class="reference internal" href="#counting"><tt class="docutils literal"><span class="pre">counting_iterator</span></tt></a>), because <tt class="docutils literal"><span class="pre">*(p+n)</span></tt> is a reference
422into the temporary iterator <tt class="docutils literal"><span class="pre">p+n</span></tt>, which is destroyed when
423<tt class="docutils literal"><span class="pre">operator[]</span></tt> returns.</p>
424<p>Writable iterators built with <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> implement the
425semantics required by the preferred resolution to <a class="reference external" href="http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#299">issue 299</a> and
426adopted by proposal <a class="reference external" href="http://anubis.dkuug.dk/JTC1/SC22/WG21/docs/papers/2003/n1550.html">n1550</a>: the result of <tt class="docutils literal"><span class="pre">p[n]</span></tt> is an object
427convertible to the iterator's <tt class="docutils literal"><span class="pre">value_type</span></tt>, and <tt class="docutils literal"><span class="pre">p[n]</span> <span class="pre">=</span> <span class="pre">x</span></tt> is
428equivalent to <tt class="docutils literal"><span class="pre">*(p</span> <span class="pre">+</span> <span class="pre">n)</span> <span class="pre">=</span> <span class="pre">x</span></tt> (Note: This result object may be
429implemented as a proxy containing a copy of <tt class="docutils literal"><span class="pre">p+n</span></tt>).  This approach
430will work properly for any random-access iterator regardless of the
431other details of its implementation.  A user who knows more about
432the implementation of her iterator is free to implement an
433<tt class="docutils literal"><span class="pre">operator[]</span></tt> that returns an lvalue in the derived iterator
434class; it will hide the one supplied by <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> from
435clients of her iterator.</p>
436</div>
437<div class="section" id="id6">
438<span id="operator-arrow"></span><h3><a class="toc-backref" href="#id24"><tt class="docutils literal"><span class="pre">operator-&gt;</span></tt></a></h3>
439<p>The <tt class="docutils literal"><span class="pre">reference</span></tt> type of a readable iterator (and today's input
440iterator) need not in fact be a reference, so long as it is
441convertible to the iterator's <tt class="docutils literal"><span class="pre">value_type</span></tt>.  When the <tt class="docutils literal"><span class="pre">value_type</span></tt>
442is a class, however, it must still be possible to access members
443through <tt class="docutils literal"><span class="pre">operator-&gt;</span></tt>.  Therefore, an iterator whose <tt class="docutils literal"><span class="pre">reference</span></tt>
444type is not in fact a reference must return a proxy containing a copy
445of the referenced value from its <tt class="docutils literal"><span class="pre">operator-&gt;</span></tt>.</p>
446<p>The return types for <tt class="docutils literal"><span class="pre">iterator_facade</span></tt>'s <tt class="docutils literal"><span class="pre">operator-&gt;</span></tt> and
447<tt class="docutils literal"><span class="pre">operator[]</span></tt> are not explicitly specified. Instead, those types
448are described in terms of a set of requirements, which must be
449satisfied by the <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> implementation.</p>
450<table class="docutils citation" frame="void" id="cop95" rules="none">
451<colgroup><col class="label" /><col /></colgroup>
452<tbody valign="top">
453<tr><td class="label"><a class="fn-backref" href="#id4">[Cop95]</a></td><td>[Coplien, 1995] Coplien, J., Curiously Recurring Template
454Patterns, C++ Report, February 1995, pp. 24-27.</td></tr>
455</tbody>
456</table>
457</div>
458</div>
459<div class="section" id="iterator-adaptor">
460<h2><a class="toc-backref" href="#id25">Iterator Adaptor</a></h2>
461<!-- Distributed under the Boost -->
462<!-- Software License, Version 1.0. (See accompanying -->
463<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
464<!-- Version 1.2 of this ReStructuredText document corresponds to
465n1530_, the paper accepted by the LWG for TR1. -->
466<!-- Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003. -->
467<p>The <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> class template adapts some <tt class="docutils literal"><span class="pre">Base</span></tt><a class="footnote-reference" href="#base" id="id7"><sup>3</sup></a>
468type to create a new iterator.  Instantiations of <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>
469are derived from a corresponding instantiation of <tt class="docutils literal"><span class="pre">iterator_facade</span></tt>
470and implement the core behaviors in terms of the <tt class="docutils literal"><span class="pre">Base</span></tt> type. In
471essence, <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> merely forwards all operations to an
472instance of the <tt class="docutils literal"><span class="pre">Base</span></tt> type, which it stores as a member.</p>
473<table class="docutils footnote" frame="void" id="base" rules="none">
474<colgroup><col class="label" /><col /></colgroup>
475<tbody valign="top">
476<tr><td class="label"><a class="fn-backref" href="#id7">[3]</a></td><td>The term &quot;Base&quot; here does not refer to a base class and is
477not meant to imply the use of derivation. We have followed the lead
478of the standard library, which provides a base() function to access
479the underlying iterator object of a <tt class="docutils literal"><span class="pre">reverse_iterator</span></tt> adaptor.</td></tr>
480</tbody>
481</table>
482<p>The user of <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> creates a class derived from an
483instantiation of <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> and then selectively
484redefines some of the core member functions described in the
485<tt class="docutils literal"><span class="pre">iterator_facade</span></tt> core requirements table. The <tt class="docutils literal"><span class="pre">Base</span></tt> type need
486not meet the full requirements for an iterator; it need only
487support the operations used by the core interface functions of
488<tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> that have not been redefined in the user's
489derived class.</p>
490<p>Several of the template parameters of <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> default
491to <tt class="docutils literal"><span class="pre">use_default</span></tt>. This allows the
492user to make use of a default parameter even when she wants to
493specify a parameter later in the parameter list.  Also, the
494defaults for the corresponding associated types are somewhat
495complicated, so metaprogramming is required to compute them, and
496<tt class="docutils literal"><span class="pre">use_default</span></tt> can help to simplify the implementation.  Finally,
497the identity of the <tt class="docutils literal"><span class="pre">use_default</span></tt> type is not left unspecified
498because specification helps to highlight that the <tt class="docutils literal"><span class="pre">Reference</span></tt>
499template parameter may not always be identical to the iterator's
500<tt class="docutils literal"><span class="pre">reference</span></tt> type, and will keep users from making mistakes based on
501that assumption.</p>
502</div>
503<div class="section" id="specialized-adaptors">
504<h2><a class="toc-backref" href="#id26">Specialized Adaptors</a></h2>
505<p>This proposal also contains several examples of specialized adaptors
506which were easily implemented using <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>:</p>
507<ul class="simple">
508<li><tt class="docutils literal"><span class="pre">indirect_iterator</span></tt>, which iterates over iterators, pointers,
509or smart pointers and applies an extra level of dereferencing.</li>
510<li>A new <tt class="docutils literal"><span class="pre">reverse_iterator</span></tt>, which inverts the direction of a Base
511iterator's motion, while allowing adapted constant and mutable
512iterators to interact in the expected ways (unlike those in most
513implementations of C++98).</li>
514<li><tt class="docutils literal"><span class="pre">transform_iterator</span></tt>, which applies a user-defined function object
515to the underlying values when dereferenced.</li>
516<li><tt class="docutils literal"><span class="pre">filter_iterator</span></tt>, which provides a view of an iterator range in
517which some elements of the underlying range are skipped.</li>
518</ul>
519<ul class="simple" id="counting">
520<li><tt class="docutils literal"><span class="pre">counting_iterator</span></tt>, which adapts any incrementable type
521(e.g. integers, iterators) so that incrementing/decrementing the
522adapted iterator and dereferencing it produces successive values of
523the Base type.</li>
524<li><tt class="docutils literal"><span class="pre">function_output_iterator</span></tt>, which makes it easier to create custom
525output iterators.</li>
526</ul>
527<p>Based on examples in the Boost library, users have generated many new
528adaptors, among them a permutation adaptor which applies some
529permutation to a random access iterator, and a strided adaptor, which
530adapts a random access iterator by multiplying its unit of motion by a
531constant factor.  In addition, the Boost Graph Library (BGL) uses
532iterator adaptors to adapt other graph libraries, such as LEDA [10]
533and Stanford GraphBase [8], to the BGL interface (which requires C++
534Standard compliant iterators).</p>
535</div>
536</div>
537<div class="section" id="proposed-text">
538<h1><a class="toc-backref" href="#id27">Proposed Text</a></h1>
539<div class="section" id="header-iterator-helper-synopsis-lib-iterator-helper-synopsis">
540<h2><a class="toc-backref" href="#id28">Header <tt class="docutils literal"><span class="pre">&lt;iterator_helper&gt;</span></tt> synopsis    [lib.iterator.helper.synopsis]</a></h2>
541<pre class="literal-block">
542struct use_default;
543
544struct iterator_core_access { /* implementation detail */ };
545
546template &lt;
547    class Derived
548  , class Value
549  , class CategoryOrTraversal
550  , class Reference  = Value&amp;
551  , class Difference = ptrdiff_t
552&gt;
553class iterator_facade;
554
555template &lt;
556    class Derived
557  , class Base
558  , class Value      = use_default
559  , class CategoryOrTraversal  = use_default
560  , class Reference  = use_default
561  , class Difference = use_default
562&gt;
563class iterator_adaptor;
564
565template &lt;
566    class Iterator
567  , class Value = use_default
568  , class CategoryOrTraversal = use_default
569  , class Reference = use_default
570  , class Difference = use_default
571&gt;
572class indirect_iterator;
573
574template &lt;class Dereferenceable&gt;
575struct pointee;
576
577template &lt;class Dereferenceable&gt;
578struct indirect_reference;
579
580template &lt;class Iterator&gt;
581class reverse_iterator;
582
583template &lt;
584    class UnaryFunction
585  , class Iterator
586  , class Reference = use_default
587  , class Value = use_default
588&gt;
589class transform_iterator;
590
591template &lt;class Predicate, class Iterator&gt;
592class filter_iterator;
593
594template &lt;
595    class Incrementable
596  , class CategoryOrTraversal  = use_default
597  , class Difference = use_default
598&gt;
599class counting_iterator;
600
601template &lt;class UnaryFunction&gt;
602class function_output_iterator;
603</pre>
604</div>
605<div class="section" id="iterator-facade-lib-iterator-facade">
606<h2><a class="toc-backref" href="#id29">Iterator facade [lib.iterator.facade]</a></h2>
607<!-- Copyright David Abrahams 2006. Distributed under the Boost -->
608<!-- Software License, Version 1.0. (See accompanying -->
609<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
610<p><tt class="docutils literal"><span class="pre">iterator_facade</span></tt> is a base class template that implements the
611interface of standard iterators in terms of a few core functions
612and associated types, to be supplied by a derived iterator class.</p>
613<div class="section" id="class-template-iterator-facade">
614<h3><a class="toc-backref" href="#id30">Class template <tt class="docutils literal"><span class="pre">iterator_facade</span></tt></a></h3>
615<!-- Distributed under the Boost -->
616<!-- Software License, Version 1.0. (See accompanying -->
617<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
618<!-- Version 1.3 of this ReStructuredText document corresponds to
619n1530_, the paper accepted by the LWG for TR1. -->
620<!-- Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003. -->
621<pre class="literal-block">
622template &lt;
623    class Derived
624  , class Value
625  , class CategoryOrTraversal
626  , class Reference  = Value&amp;
627  , class Difference = ptrdiff_t
628&gt;
629class iterator_facade {
630 public:
631    typedef remove_const&lt;Value&gt;::type value_type;
632    typedef Reference reference;
633    typedef Value* pointer;
634    typedef Difference difference_type;
635    typedef /* see <a class="reference internal" href="#iterator-category">below</a> */ iterator_category;
636
637    reference operator*() const;
638    /* see <a class="reference internal" href="#operator-arrow">below</a> */ operator-&gt;() const;
639    /* see <a class="reference internal" href="#brackets">below</a> */ operator[](difference_type n) const;
640    Derived&amp; operator++();
641    Derived operator++(int);
642    Derived&amp; operator--();
643    Derived operator--(int);
644    Derived&amp; operator+=(difference_type n);
645    Derived&amp; operator-=(difference_type n);
646    Derived operator-(difference_type n) const;
647 protected:
648    typedef iterator_facade iterator_facade_;
649};
650
651// Comparison operators
652template &lt;class Dr1, class V1, class TC1, class R1, class D1,
653          class Dr2, class V2, class TC2, class R2, class D2&gt;
654typename enable_if_interoperable&lt;Dr1,Dr2,bool&gt;::type // exposition
655operator ==(iterator_facade&lt;Dr1,V1,TC1,R1,D1&gt; const&amp; lhs,
656            iterator_facade&lt;Dr2,V2,TC2,R2,D2&gt; const&amp; rhs);
657
658template &lt;class Dr1, class V1, class TC1, class R1, class D1,
659          class Dr2, class V2, class TC2, class R2, class D2&gt;
660typename enable_if_interoperable&lt;Dr1,Dr2,bool&gt;::type
661operator !=(iterator_facade&lt;Dr1,V1,TC1,R1,D1&gt; const&amp; lhs,
662            iterator_facade&lt;Dr2,V2,TC2,R2,D2&gt; const&amp; rhs);
663
664template &lt;class Dr1, class V1, class TC1, class R1, class D1,
665          class Dr2, class V2, class TC2, class R2, class D2&gt;
666typename enable_if_interoperable&lt;Dr1,Dr2,bool&gt;::type
667operator &lt;(iterator_facade&lt;Dr1,V1,TC1,R1,D1&gt; const&amp; lhs,
668           iterator_facade&lt;Dr2,V2,TC2,R2,D2&gt; const&amp; rhs);
669
670template &lt;class Dr1, class V1, class TC1, class R1, class D1,
671          class Dr2, class V2, class TC2, class R2, class D2&gt;
672typename enable_if_interoperable&lt;Dr1,Dr2,bool&gt;::type
673operator &lt;=(iterator_facade&lt;Dr1,V1,TC1,R1,D1&gt; const&amp; lhs,
674            iterator_facade&lt;Dr2,V2,TC2,R2,D2&gt; const&amp; rhs);
675
676template &lt;class Dr1, class V1, class TC1, class R1, class D1,
677          class Dr2, class V2, class TC2, class R2, class D2&gt;
678typename enable_if_interoperable&lt;Dr1,Dr2,bool&gt;::type
679operator &gt;(iterator_facade&lt;Dr1,V1,TC1,R1,D1&gt; const&amp; lhs,
680           iterator_facade&lt;Dr2,V2,TC2,R2,D2&gt; const&amp; rhs);
681
682template &lt;class Dr1, class V1, class TC1, class R1, class D1,
683          class Dr2, class V2, class TC2, class R2, class D2&gt;
684typename enable_if_interoperable&lt;Dr1,Dr2,bool&gt;::type
685operator &gt;=(iterator_facade&lt;Dr1,V1,TC1,R1,D1&gt; const&amp; lhs,
686            iterator_facade&lt;Dr2,V2,TC2,R2,D2&gt; const&amp; rhs);
687
688// Iterator difference
689template &lt;class Dr1, class V1, class TC1, class R1, class D1,
690          class Dr2, class V2, class TC2, class R2, class D2&gt;
691/* see <a class="reference internal" href="#minus">below</a> */
692operator-(iterator_facade&lt;Dr1,V1,TC1,R1,D1&gt; const&amp; lhs,
693          iterator_facade&lt;Dr2,V2,TC2,R2,D2&gt; const&amp; rhs);
694
695// Iterator addition
696template &lt;class Dr, class V, class TC, class R, class D&gt;
697Derived operator+ (iterator_facade&lt;Dr,V,TC,R,D&gt; const&amp;,
698                   typename Derived::difference_type n);
699
700template &lt;class Dr, class V, class TC, class R, class D&gt;
701Derived operator+ (typename Derived::difference_type n,
702                   iterator_facade&lt;Dr,V,TC,R,D&gt; const&amp;);
703</pre>
704<p id="iterator-category">The <tt class="docutils literal"><span class="pre">iterator_category</span></tt> member of <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> is</p>
705<pre class="literal-block">
706<em>iterator-category</em>(CategoryOrTraversal, value_type, reference)
707</pre>
708<p>where <em>iterator-category</em> is defined as follows:</p>
709<pre class="literal-block" id="id12">
710<em>iterator-category</em>(C,R,V) :=
711   if (C is convertible to std::input_iterator_tag
712       || C is convertible to std::output_iterator_tag
713   )
714       return C
715
716   else if (C is not convertible to incrementable_traversal_tag)
717       <em>the program is ill-formed</em>
718
719   else return a type X satisfying the following two constraints:
720
721      1. X is convertible to X1, and not to any more-derived
722         type, where X1 is defined by:
723
724           if (R is a reference type
725               &amp;&amp; C is convertible to forward_traversal_tag)
726           {
727               if (C is convertible to random_access_traversal_tag)
728                   X1 = random_access_iterator_tag
729               else if (C is convertible to bidirectional_traversal_tag)
730                   X1 = bidirectional_iterator_tag
731               else
732                   X1 = forward_iterator_tag
733           }
734           else
735           {
736               if (C is convertible to single_pass_traversal_tag
737                   &amp;&amp; R is convertible to V)
738                   X1 = input_iterator_tag
739               else
740                   X1 = C
741           }
742
743      2. <a class="reference external" href="new-iter-concepts.html#category-to-traversal"><em>category-to-traversal</em></a>(X) is convertible to the most
744         derived traversal tag type to which X is also
745         convertible, and not to any more-derived traversal tag
746         type.
747</pre>
748<p>[Note: the intention is to allow <tt class="docutils literal"><span class="pre">iterator_category</span></tt> to be one of
749the five original category tags when convertibility to one of the
750traversal tags would add no information]</p>
751<!-- Copyright David Abrahams 2004. Use, modification and distribution is -->
752<!-- subject to the Boost Software License, Version 1.0. (See accompanying -->
753<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
754<p>The <tt class="docutils literal"><span class="pre">enable_if_interoperable</span></tt> template used above is for exposition
755purposes.  The member operators should only be in an overload set
756provided the derived types <tt class="docutils literal"><span class="pre">Dr1</span></tt> and <tt class="docutils literal"><span class="pre">Dr2</span></tt> are interoperable,
757meaning that at least one of the types is convertible to the other.  The
758<tt class="docutils literal"><span class="pre">enable_if_interoperable</span></tt> approach uses SFINAE to take the operators
759out of the overload set when the types are not interoperable.
760The operators should behave <em>as-if</em> <tt class="docutils literal"><span class="pre">enable_if_interoperable</span></tt>
761were defined to be:</p>
762<pre class="literal-block">
763template &lt;bool, typename&gt; enable_if_interoperable_impl
764{};
765
766template &lt;typename T&gt; enable_if_interoperable_impl&lt;true,T&gt;
767{ typedef T type; };
768
769template&lt;typename Dr1, typename Dr2, typename T&gt;
770struct enable_if_interoperable
771  : enable_if_interoperable_impl&lt;
772        is_convertible&lt;Dr1,Dr2&gt;::value || is_convertible&lt;Dr2,Dr1&gt;::value
773      , T
774    &gt;
775{};
776</pre>
777</div>
778<div class="section" id="iterator-facade-requirements">
779<h3><a class="toc-backref" href="#id31"><tt class="docutils literal"><span class="pre">iterator_facade</span></tt> Requirements</a></h3>
780<p>The following table describes the typical valid expressions on
781<tt class="docutils literal"><span class="pre">iterator_facade</span></tt>'s <tt class="docutils literal"><span class="pre">Derived</span></tt> parameter, depending on the
782iterator concept(s) it will model.  The operations in the first
783column must be made accessible to member functions of class
784<tt class="docutils literal"><span class="pre">iterator_core_access</span></tt>.  In addition,
785<tt class="docutils literal"><span class="pre">static_cast&lt;Derived*&gt;(iterator_facade*)</span></tt> shall be well-formed.</p>
786<p>In the table below, <tt class="docutils literal"><span class="pre">F</span></tt> is <tt class="docutils literal"><span class="pre">iterator_facade&lt;X,V,C,R,D&gt;</span></tt>, <tt class="docutils literal"><span class="pre">a</span></tt> is an
787object of type <tt class="docutils literal"><span class="pre">X</span></tt>, <tt class="docutils literal"><span class="pre">b</span></tt> and <tt class="docutils literal"><span class="pre">c</span></tt> are objects of type <tt class="docutils literal"><span class="pre">const</span> <span class="pre">X</span></tt>,
788<tt class="docutils literal"><span class="pre">n</span></tt> is an object of <tt class="docutils literal"><span class="pre">F::difference_type</span></tt>, <tt class="docutils literal"><span class="pre">y</span></tt> is a constant
789object of a single pass iterator type interoperable with <tt class="docutils literal"><span class="pre">X</span></tt>, and <tt class="docutils literal"><span class="pre">z</span></tt>
790is a constant object of a random access traversal iterator type
791interoperable with <tt class="docutils literal"><span class="pre">X</span></tt>.</p>
792<div class="topic" id="core-operations">
793<p class="topic-title first"><tt class="docutils literal"><span class="pre">iterator_facade</span></tt> Core Operations</p>
794<table border="1" class="docutils">
795<colgroup>
796<col width="21%" />
797<col width="23%" />
798<col width="27%" />
799<col width="29%" />
800</colgroup>
801<thead valign="bottom">
802<tr><th class="head">Expression</th>
803<th class="head">Return Type</th>
804<th class="head">Assertion/Note</th>
805<th class="head">Used to implement Iterator
806Concept(s)</th>
807</tr>
808</thead>
809<tbody valign="top">
810<tr><td><tt class="docutils literal"><span class="pre">c.dereference()</span></tt></td>
811<td><tt class="docutils literal"><span class="pre">F::reference</span></tt></td>
812<td>&nbsp;</td>
813<td>Readable Iterator, Writable
814Iterator</td>
815</tr>
816<tr><td><tt class="docutils literal"><span class="pre">c.equal(y)</span></tt></td>
817<td>convertible to bool</td>
818<td>true iff <tt class="docutils literal"><span class="pre">c</span></tt> and <tt class="docutils literal"><span class="pre">y</span></tt>
819refer to the same
820position.</td>
821<td>Single Pass Iterator</td>
822</tr>
823<tr><td><tt class="docutils literal"><span class="pre">a.increment()</span></tt></td>
824<td>unused</td>
825<td>&nbsp;</td>
826<td>Incrementable Iterator</td>
827</tr>
828<tr><td><tt class="docutils literal"><span class="pre">a.decrement()</span></tt></td>
829<td>unused</td>
830<td>&nbsp;</td>
831<td>Bidirectional Traversal
832Iterator</td>
833</tr>
834<tr><td><tt class="docutils literal"><span class="pre">a.advance(n)</span></tt></td>
835<td>unused</td>
836<td>&nbsp;</td>
837<td>Random Access Traversal
838Iterator</td>
839</tr>
840<tr><td><tt class="docutils literal"><span class="pre">c.distance_to(z)</span></tt></td>
841<td>convertible to
842<tt class="docutils literal"><span class="pre">F::difference_type</span></tt></td>
843<td>equivalent to
844<tt class="docutils literal"><span class="pre">distance(c,</span> <span class="pre">X(z))</span></tt>.</td>
845<td>Random Access Traversal
846Iterator</td>
847</tr>
848</tbody>
849</table>
850</div>
851</div>
852<div class="section" id="iterator-facade-operations">
853<h3><a class="toc-backref" href="#id32"><tt class="docutils literal"><span class="pre">iterator_facade</span></tt> operations</a></h3>
854<p>The operations in this section are described in terms of operations on
855the core interface of <tt class="docutils literal"><span class="pre">Derived</span></tt> which may be inaccessible
856(i.e. private).  The implementation should access these operations
857through member functions of class <tt class="docutils literal"><span class="pre">iterator_core_access</span></tt>.</p>
858<p><tt class="docutils literal"><span class="pre">reference</span> <span class="pre">operator*()</span> <span class="pre">const;</span></tt></p>
859<table class="docutils field-list" frame="void" rules="none">
860<col class="field-name" />
861<col class="field-body" />
862<tbody valign="top">
863<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">static_cast&lt;Derived</span> <span class="pre">const*&gt;(this)-&gt;dereference()</span></tt></td>
864</tr>
865</tbody>
866</table>
867<p><tt class="docutils literal"><span class="pre">operator-&gt;()</span> <span class="pre">const;</span></tt> (see <a class="reference internal" href="#operator-arrow">below</a>)</p>
868<table class="docutils field-list" frame="void" rules="none">
869<col class="field-name" />
870<col class="field-body" />
871<tbody valign="top">
872<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><p class="first">If <tt class="docutils literal"><span class="pre">reference</span></tt> is a reference type, an object
873of type <tt class="docutils literal"><span class="pre">pointer</span></tt> equal to:</p>
874<pre class="literal-block">
875&amp;static_cast&lt;Derived const*&gt;(this)-&gt;dereference()
876</pre>
877<p class="last">Otherwise returns an object of unspecified type such that,
878<tt class="docutils literal"><span class="pre">(*static_cast&lt;Derived</span> <span class="pre">const*&gt;(this))-&gt;m</span></tt> is equivalent to <tt class="docutils literal"><span class="pre">(w</span> <span class="pre">=</span> <span class="pre">**static_cast&lt;Derived</span> <span class="pre">const*&gt;(this),</span>
879<span class="pre">w.m)</span></tt> for some temporary object <tt class="docutils literal"><span class="pre">w</span></tt> of type <tt class="docutils literal"><span class="pre">value_type</span></tt>.</p>
880</td>
881</tr>
882</tbody>
883</table>
884<p id="brackets"><em>unspecified</em> <tt class="docutils literal"><span class="pre">operator[](difference_type</span> <span class="pre">n)</span> <span class="pre">const;</span></tt></p>
885<table class="docutils field-list" frame="void" rules="none">
886<col class="field-name" />
887<col class="field-body" />
888<tbody valign="top">
889<tr class="field"><th class="field-name">Returns:</th><td class="field-body">an object convertible to <tt class="docutils literal"><span class="pre">value_type</span></tt>. For constant
890objects <tt class="docutils literal"><span class="pre">v</span></tt> of type <tt class="docutils literal"><span class="pre">value_type</span></tt>, and <tt class="docutils literal"><span class="pre">n</span></tt> of type
891<tt class="docutils literal"><span class="pre">difference_type</span></tt>, <tt class="docutils literal"><span class="pre">(*this)[n]</span> <span class="pre">=</span> <span class="pre">v</span></tt> is equivalent to
892<tt class="docutils literal"><span class="pre">*(*this</span> <span class="pre">+</span> <span class="pre">n)</span> <span class="pre">=</span> <span class="pre">v</span></tt>, and <tt class="docutils literal"><span class="pre">static_cast&lt;value_type</span>
893<span class="pre">const&amp;&gt;((*this)[n])</span></tt> is equivalent to
894<tt class="docutils literal"><span class="pre">static_cast&lt;value_type</span> <span class="pre">const&amp;&gt;(*(*this</span> <span class="pre">+</span> <span class="pre">n))</span></tt></td>
895</tr>
896</tbody>
897</table>
898<p><tt class="docutils literal"><span class="pre">Derived&amp;</span> <span class="pre">operator++();</span></tt></p>
899<table class="docutils field-list" frame="void" rules="none">
900<col class="field-name" />
901<col class="field-body" />
902<tbody valign="top">
903<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><pre class="first last literal-block">
904static_cast&lt;Derived*&gt;(this)-&gt;increment();
905return *static_cast&lt;Derived*&gt;(this);
906</pre>
907</td>
908</tr>
909</tbody>
910</table>
911<p><tt class="docutils literal"><span class="pre">Derived</span> <span class="pre">operator++(int);</span></tt></p>
912<table class="docutils field-list" frame="void" rules="none">
913<col class="field-name" />
914<col class="field-body" />
915<tbody valign="top">
916<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><pre class="first last literal-block">
917Derived tmp(static_cast&lt;Derived const*&gt;(this));
918++*this;
919return tmp;
920</pre>
921</td>
922</tr>
923</tbody>
924</table>
925<p><tt class="docutils literal"><span class="pre">Derived&amp;</span> <span class="pre">operator--();</span></tt></p>
926<table class="docutils field-list" frame="void" rules="none">
927<col class="field-name" />
928<col class="field-body" />
929<tbody valign="top">
930<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><pre class="first last literal-block">
931static_cast&lt;Derived*&gt;(this)-&gt;decrement();
932return *static_cast&lt;Derived*&gt;(this);
933</pre>
934</td>
935</tr>
936</tbody>
937</table>
938<p><tt class="docutils literal"><span class="pre">Derived</span> <span class="pre">operator--(int);</span></tt></p>
939<table class="docutils field-list" frame="void" rules="none">
940<col class="field-name" />
941<col class="field-body" />
942<tbody valign="top">
943<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><pre class="first last literal-block">
944Derived tmp(static_cast&lt;Derived const*&gt;(this));
945--*this;
946return tmp;
947</pre>
948</td>
949</tr>
950</tbody>
951</table>
952<p><tt class="docutils literal"><span class="pre">Derived&amp;</span> <span class="pre">operator+=(difference_type</span> <span class="pre">n);</span></tt></p>
953<table class="docutils field-list" frame="void" rules="none">
954<col class="field-name" />
955<col class="field-body" />
956<tbody valign="top">
957<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><pre class="first last literal-block">
958static_cast&lt;Derived*&gt;(this)-&gt;advance(n);
959return *static_cast&lt;Derived*&gt;(this);
960</pre>
961</td>
962</tr>
963</tbody>
964</table>
965<p><tt class="docutils literal"><span class="pre">Derived&amp;</span> <span class="pre">operator-=(difference_type</span> <span class="pre">n);</span></tt></p>
966<table class="docutils field-list" frame="void" rules="none">
967<col class="field-name" />
968<col class="field-body" />
969<tbody valign="top">
970<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><pre class="first last literal-block">
971static_cast&lt;Derived*&gt;(this)-&gt;advance(-n);
972return *static_cast&lt;Derived*&gt;(this);
973</pre>
974</td>
975</tr>
976</tbody>
977</table>
978<p><tt class="docutils literal"><span class="pre">Derived</span> <span class="pre">operator-(difference_type</span> <span class="pre">n)</span> <span class="pre">const;</span></tt></p>
979<table class="docutils field-list" frame="void" rules="none">
980<col class="field-name" />
981<col class="field-body" />
982<tbody valign="top">
983<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><pre class="first last literal-block">
984Derived tmp(static_cast&lt;Derived const*&gt;(this));
985return tmp -= n;
986</pre>
987</td>
988</tr>
989</tbody>
990</table>
991<pre class="literal-block">
992template &lt;class Dr, class V, class TC, class R, class D&gt;
993Derived operator+ (iterator_facade&lt;Dr,V,TC,R,D&gt; const&amp;,
994                   typename Derived::difference_type n);
995
996template &lt;class Dr, class V, class TC, class R, class D&gt;
997Derived operator+ (typename Derived::difference_type n,
998                   iterator_facade&lt;Dr,V,TC,R,D&gt; const&amp;);
999</pre>
1000<table class="docutils field-list" frame="void" rules="none">
1001<col class="field-name" />
1002<col class="field-body" />
1003<tbody valign="top">
1004<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><pre class="first last literal-block">
1005Derived tmp(static_cast&lt;Derived const*&gt;(this));
1006return tmp += n;
1007</pre>
1008</td>
1009</tr>
1010</tbody>
1011</table>
1012<pre class="literal-block">
1013template &lt;class Dr1, class V1, class TC1, class R1, class D1,
1014          class Dr2, class V2, class TC2, class R2, class D2&gt;
1015typename enable_if_interoperable&lt;Dr1,Dr2,bool&gt;::type
1016operator ==(iterator_facade&lt;Dr1,V1,TC1,R1,D1&gt; const&amp; lhs,
1017            iterator_facade&lt;Dr2,V2,TC2,R2,D2&gt; const&amp; rhs);
1018</pre>
1019<table class="docutils field-list" frame="void" rules="none">
1020<col class="field-name" />
1021<col class="field-body" />
1022<tbody valign="top">
1023<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><p class="first">if <tt class="docutils literal"><span class="pre">is_convertible&lt;Dr2,Dr1&gt;::value</span></tt></p>
1024<dl class="last docutils">
1025<dt>then</dt>
1026<dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr1</span> <span class="pre">const&amp;)lhs).equal((Dr2</span> <span class="pre">const&amp;)rhs)</span></tt>.</p>
1027</dd>
1028<dt>Otherwise,</dt>
1029<dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr2</span> <span class="pre">const&amp;)rhs).equal((Dr1</span> <span class="pre">const&amp;)lhs)</span></tt>.</p>
1030</dd>
1031</dl>
1032</td>
1033</tr>
1034</tbody>
1035</table>
1036<pre class="literal-block">
1037template &lt;class Dr1, class V1, class TC1, class R1, class D1,
1038          class Dr2, class V2, class TC2, class R2, class D2&gt;
1039typename enable_if_interoperable&lt;Dr1,Dr2,bool&gt;::type
1040operator !=(iterator_facade&lt;Dr1,V1,TC1,R1,D1&gt; const&amp; lhs,
1041            iterator_facade&lt;Dr2,V2,TC2,R2,D2&gt; const&amp; rhs);
1042</pre>
1043<table class="docutils field-list" frame="void" rules="none">
1044<col class="field-name" />
1045<col class="field-body" />
1046<tbody valign="top">
1047<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><p class="first">if <tt class="docutils literal"><span class="pre">is_convertible&lt;Dr2,Dr1&gt;::value</span></tt></p>
1048<dl class="last docutils">
1049<dt>then</dt>
1050<dd><p class="first last"><tt class="docutils literal"><span class="pre">!((Dr1</span> <span class="pre">const&amp;)lhs).equal((Dr2</span> <span class="pre">const&amp;)rhs)</span></tt>.</p>
1051</dd>
1052<dt>Otherwise,</dt>
1053<dd><p class="first last"><tt class="docutils literal"><span class="pre">!((Dr2</span> <span class="pre">const&amp;)rhs).equal((Dr1</span> <span class="pre">const&amp;)lhs)</span></tt>.</p>
1054</dd>
1055</dl>
1056</td>
1057</tr>
1058</tbody>
1059</table>
1060<pre class="literal-block">
1061template &lt;class Dr1, class V1, class TC1, class R1, class D1,
1062          class Dr2, class V2, class TC2, class R2, class D2&gt;
1063typename enable_if_interoperable&lt;Dr1,Dr2,bool&gt;::type
1064operator &lt;(iterator_facade&lt;Dr1,V1,TC1,R1,D1&gt; const&amp; lhs,
1065           iterator_facade&lt;Dr2,V2,TC2,R2,D2&gt; const&amp; rhs);
1066</pre>
1067<table class="docutils field-list" frame="void" rules="none">
1068<col class="field-name" />
1069<col class="field-body" />
1070<tbody valign="top">
1071<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><p class="first">if <tt class="docutils literal"><span class="pre">is_convertible&lt;Dr2,Dr1&gt;::value</span></tt></p>
1072<dl class="last docutils">
1073<dt>then</dt>
1074<dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr1</span> <span class="pre">const&amp;)lhs).distance_to((Dr2</span> <span class="pre">const&amp;)rhs)</span> <span class="pre">&lt;</span> <span class="pre">0</span></tt>.</p>
1075</dd>
1076<dt>Otherwise,</dt>
1077<dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr2</span> <span class="pre">const&amp;)rhs).distance_to((Dr1</span> <span class="pre">const&amp;)lhs)</span> <span class="pre">&gt;</span> <span class="pre">0</span></tt>.</p>
1078</dd>
1079</dl>
1080</td>
1081</tr>
1082</tbody>
1083</table>
1084<pre class="literal-block">
1085template &lt;class Dr1, class V1, class TC1, class R1, class D1,
1086          class Dr2, class V2, class TC2, class R2, class D2&gt;
1087typename enable_if_interoperable&lt;Dr1,Dr2,bool&gt;::type
1088operator &lt;=(iterator_facade&lt;Dr1,V1,TC1,R1,D1&gt; const&amp; lhs,
1089            iterator_facade&lt;Dr2,V2,TC2,R2,D2&gt; const&amp; rhs);
1090</pre>
1091<table class="docutils field-list" frame="void" rules="none">
1092<col class="field-name" />
1093<col class="field-body" />
1094<tbody valign="top">
1095<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><p class="first">if <tt class="docutils literal"><span class="pre">is_convertible&lt;Dr2,Dr1&gt;::value</span></tt></p>
1096<dl class="last docutils">
1097<dt>then</dt>
1098<dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr1</span> <span class="pre">const&amp;)lhs).distance_to((Dr2</span> <span class="pre">const&amp;)rhs)</span> <span class="pre">&lt;=</span> <span class="pre">0</span></tt>.</p>
1099</dd>
1100<dt>Otherwise,</dt>
1101<dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr2</span> <span class="pre">const&amp;)rhs).distance_to((Dr1</span> <span class="pre">const&amp;)lhs)</span> <span class="pre">&gt;=</span> <span class="pre">0</span></tt>.</p>
1102</dd>
1103</dl>
1104</td>
1105</tr>
1106</tbody>
1107</table>
1108<pre class="literal-block">
1109template &lt;class Dr1, class V1, class TC1, class R1, class D1,
1110          class Dr2, class V2, class TC2, class R2, class D2&gt;
1111typename enable_if_interoperable&lt;Dr1,Dr2,bool&gt;::type
1112operator &gt;(iterator_facade&lt;Dr1,V1,TC1,R1,D1&gt; const&amp; lhs,
1113           iterator_facade&lt;Dr2,V2,TC2,R2,D2&gt; const&amp; rhs);
1114</pre>
1115<table class="docutils field-list" frame="void" rules="none">
1116<col class="field-name" />
1117<col class="field-body" />
1118<tbody valign="top">
1119<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><p class="first">if <tt class="docutils literal"><span class="pre">is_convertible&lt;Dr2,Dr1&gt;::value</span></tt></p>
1120<dl class="last docutils">
1121<dt>then</dt>
1122<dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr1</span> <span class="pre">const&amp;)lhs).distance_to((Dr2</span> <span class="pre">const&amp;)rhs)</span> <span class="pre">&gt;</span> <span class="pre">0</span></tt>.</p>
1123</dd>
1124<dt>Otherwise,</dt>
1125<dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr2</span> <span class="pre">const&amp;)rhs).distance_to((Dr1</span> <span class="pre">const&amp;)lhs)</span> <span class="pre">&lt;</span> <span class="pre">0</span></tt>.</p>
1126</dd>
1127</dl>
1128</td>
1129</tr>
1130</tbody>
1131</table>
1132<pre class="literal-block">
1133template &lt;class Dr1, class V1, class TC1, class R1, class D1,
1134          class Dr2, class V2, class TC2, class R2, class D2&gt;
1135typename enable_if_interoperable&lt;Dr1,Dr2,bool&gt;::type
1136operator &gt;=(iterator_facade&lt;Dr1,V1,TC1,R1,D1&gt; const&amp; lhs,
1137            iterator_facade&lt;Dr2,V2,TC2,R2,D2&gt; const&amp; rhs);
1138</pre>
1139<table class="docutils field-list" frame="void" rules="none">
1140<col class="field-name" />
1141<col class="field-body" />
1142<tbody valign="top">
1143<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><p class="first">if <tt class="docutils literal"><span class="pre">is_convertible&lt;Dr2,Dr1&gt;::value</span></tt></p>
1144<dl class="last docutils">
1145<dt>then</dt>
1146<dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr1</span> <span class="pre">const&amp;)lhs).distance_to((Dr2</span> <span class="pre">const&amp;)rhs)</span> <span class="pre">&gt;=</span> <span class="pre">0</span></tt>.</p>
1147</dd>
1148<dt>Otherwise,</dt>
1149<dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr2</span> <span class="pre">const&amp;)rhs).distance_to((Dr1</span> <span class="pre">const&amp;)lhs)</span> <span class="pre">&lt;=</span> <span class="pre">0</span></tt>.</p>
1150</dd>
1151</dl>
1152</td>
1153</tr>
1154</tbody>
1155</table>
1156<pre class="literal-block" id="minus">
1157template &lt;class Dr1, class V1, class TC1, class R1, class D1,
1158          class Dr2, class V2, class TC2, class R2, class D2&gt;
1159typename enable_if_interoperable&lt;Dr1,Dr2,difference&gt;::type
1160operator -(iterator_facade&lt;Dr1,V1,TC1,R1,D1&gt; const&amp; lhs,
1161           iterator_facade&lt;Dr2,V2,TC2,R2,D2&gt; const&amp; rhs);
1162</pre>
1163<table class="docutils field-list" frame="void" rules="none">
1164<col class="field-name" />
1165<col class="field-body" />
1166<tbody valign="top">
1167<tr class="field"><th class="field-name">Return Type:</th><td class="field-body"><p class="first">if <tt class="docutils literal"><span class="pre">is_convertible&lt;Dr2,Dr1&gt;::value</span></tt></p>
1168<blockquote>
1169<dl class="docutils">
1170<dt>then</dt>
1171<dd><p class="first last"><tt class="docutils literal"><span class="pre">difference</span></tt> shall be
1172<tt class="docutils literal"><span class="pre">iterator_traits&lt;Dr1&gt;::difference_type</span></tt>.</p>
1173</dd>
1174<dt>Otherwise</dt>
1175<dd><p class="first last"><tt class="docutils literal"><span class="pre">difference</span></tt> shall be <tt class="docutils literal"><span class="pre">iterator_traits&lt;Dr2&gt;::difference_type</span></tt></p>
1176</dd>
1177</dl>
1178</blockquote>
1179</td>
1180</tr>
1181<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><p class="first">if <tt class="docutils literal"><span class="pre">is_convertible&lt;Dr2,Dr1&gt;::value</span></tt></p>
1182<dl class="last docutils">
1183<dt>then</dt>
1184<dd><p class="first last"><tt class="docutils literal"><span class="pre">-((Dr1</span> <span class="pre">const&amp;)lhs).distance_to((Dr2</span> <span class="pre">const&amp;)rhs)</span></tt>.</p>
1185</dd>
1186<dt>Otherwise,</dt>
1187<dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr2</span> <span class="pre">const&amp;)rhs).distance_to((Dr1</span> <span class="pre">const&amp;)lhs)</span></tt>.</p>
1188</dd>
1189</dl>
1190</td>
1191</tr>
1192</tbody>
1193</table>
1194</div>
1195</div>
1196<div class="section" id="iterator-adaptor-lib-iterator-adaptor">
1197<h2><a class="toc-backref" href="#id33">Iterator adaptor [lib.iterator.adaptor]</a></h2>
1198<!-- Distributed under the Boost -->
1199<!-- Software License, Version 1.0. (See accompanying -->
1200<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
1201<!-- Version 1.1 of this ReStructuredText document corresponds to
1202n1530_, the paper accepted by the LWG. -->
1203<!-- Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003. -->
1204<p>Each specialization of the <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> class template is derived from
1205a specialization of <tt class="docutils literal"><span class="pre">iterator_facade</span></tt>. The core interface functions
1206expected by <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> are implemented in terms of the
1207<tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>'s <tt class="docutils literal"><span class="pre">Base</span></tt> template parameter. A class derived
1208from <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> typically redefines some of the core
1209interface functions to adapt the behavior of the <tt class="docutils literal"><span class="pre">Base</span></tt> type.
1210Whether the derived class models any of the standard iterator concepts
1211depends on the operations supported by the <tt class="docutils literal"><span class="pre">Base</span></tt> type and which
1212core interface functions of <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> are redefined in the
1213<tt class="docutils literal"><span class="pre">Derived</span></tt> class.</p>
1214<div class="section" id="class-template-iterator-adaptor">
1215<h3><a class="toc-backref" href="#id34">Class template <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt></a></h3>
1216<!-- Distributed under the Boost -->
1217<!-- Software License, Version 1.0. (See accompanying -->
1218<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
1219<!-- Version 1.4 of this ReStructuredText document corresponds to
1220n1530_, the paper accepted by the LWG for TR1. -->
1221<!-- Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003. -->
1222<pre class="literal-block">
1223template &lt;
1224    class Derived
1225  , class Base
1226  , class Value               = use_default
1227  , class CategoryOrTraversal = use_default
1228  , class Reference           = use_default
1229  , class Difference = use_default
1230&gt;
1231class iterator_adaptor
1232  : public iterator_facade&lt;Derived, <em>V'</em>, <em>C'</em>, <em>R'</em>, <em>D'</em>&gt; // see <a class="reference internal" href="#base-parameters">details</a>
1233{
1234    friend class iterator_core_access;
1235 public:
1236    iterator_adaptor();
1237    explicit iterator_adaptor(Base const&amp; iter);
1238    typedef Base base_type;
1239    Base const&amp; base() const;
1240 protected:
1241    typedef iterator_adaptor iterator_adaptor_;
1242    Base const&amp; base_reference() const;
1243    Base&amp; base_reference();
1244 private: // Core iterator interface for iterator_facade.
1245    typename iterator_adaptor::reference dereference() const;
1246
1247    template &lt;
1248    class OtherDerived, class OtherIterator, class V, class C, class R, class D
1249    &gt;
1250    bool equal(iterator_adaptor&lt;OtherDerived, OtherIterator, V, C, R, D&gt; const&amp; x) const;
1251
1252    void advance(typename iterator_adaptor::difference_type n);
1253    void increment();
1254    void decrement();
1255
1256    template &lt;
1257        class OtherDerived, class OtherIterator, class V, class C, class R, class D
1258    &gt;
1259    typename iterator_adaptor::difference_type distance_to(
1260        iterator_adaptor&lt;OtherDerived, OtherIterator, V, C, R, D&gt; const&amp; y) const;
1261
1262 private:
1263    Base m_iterator; // exposition only
1264};
1265</pre>
1266</div>
1267<div class="section" id="iterator-adaptor-requirements">
1268<span id="requirements"></span><h3><a class="toc-backref" href="#id35"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> requirements</a></h3>
1269<p><tt class="docutils literal"><span class="pre">static_cast&lt;Derived*&gt;(iterator_adaptor*)</span></tt> shall be well-formed.
1270The <tt class="docutils literal"><span class="pre">Base</span></tt> argument shall be Assignable and Copy Constructible.</p>
1271</div>
1272<div class="section" id="iterator-adaptor-base-class-parameters">
1273<span id="base-parameters"></span><h3><a class="toc-backref" href="#id36"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> base class parameters</a></h3>
1274<p>The <em>V'</em>, <em>C'</em>, <em>R'</em>, and <em>D'</em> parameters of the <tt class="docutils literal"><span class="pre">iterator_facade</span></tt>
1275used as a base class in the summary of <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>
1276above are defined as follows:</p>
1277<pre class="literal-block">
1278<em>V'</em> = if (Value is use_default)
1279          return iterator_traits&lt;Base&gt;::value_type
1280      else
1281          return Value
1282
1283<em>C'</em> = if (CategoryOrTraversal is use_default)
1284          return iterator_traversal&lt;Base&gt;::type
1285      else
1286          return CategoryOrTraversal
1287
1288<em>R'</em> = if (Reference is use_default)
1289          if (Value is use_default)
1290              return iterator_traits&lt;Base&gt;::reference
1291          else
1292              return Value&amp;
1293      else
1294          return Reference
1295
1296<em>D'</em> = if (Difference is use_default)
1297          return iterator_traits&lt;Base&gt;::difference_type
1298      else
1299          return Difference
1300</pre>
1301<!-- ``iterator_adaptor`` models
1302- - - - - - - - - - - - - - - - - - - - - - - - - - -
1303
1304In order for ``Derived`` to model the iterator concepts corresponding
1305to ``iterator_traits<Derived>::iterator_category``, the expressions
1306involving ``m_iterator`` in the specifications of those private member
1307functions of ``iterator_adaptor`` that may be called by
1308``iterator_facade<Derived, V, C, R, D>`` in evaluating any valid
1309expression involving ``Derived`` in those concepts' requirements. -->
1310<!-- The above is confusing and needs a rewrite. -JGS -->
1311<!-- That's why it's removed.  We're embracing inheritance, remember? -->
1312</div>
1313<div class="section" id="iterator-adaptor-public-operations">
1314<h3><a class="toc-backref" href="#id37"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> public operations</a></h3>
1315<p><tt class="docutils literal"><span class="pre">iterator_adaptor();</span></tt></p>
1316<table class="docutils field-list" frame="void" rules="none">
1317<col class="field-name" />
1318<col class="field-body" />
1319<tbody valign="top">
1320<tr class="field"><th class="field-name">Requires:</th><td class="field-body">The <tt class="docutils literal"><span class="pre">Base</span></tt> type must be Default Constructible.</td>
1321</tr>
1322<tr class="field"><th class="field-name">Returns:</th><td class="field-body">An instance of <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> with
1323<tt class="docutils literal"><span class="pre">m_iterator</span></tt> default constructed.</td>
1324</tr>
1325</tbody>
1326</table>
1327<p><tt class="docutils literal"><span class="pre">explicit</span> <span class="pre">iterator_adaptor(Base</span> <span class="pre">const&amp;</span> <span class="pre">iter);</span></tt></p>
1328<table class="docutils field-list" frame="void" rules="none">
1329<col class="field-name" />
1330<col class="field-body" />
1331<tbody valign="top">
1332<tr class="field"><th class="field-name">Returns:</th><td class="field-body">An instance of <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> with
1333<tt class="docutils literal"><span class="pre">m_iterator</span></tt> copy constructed from <tt class="docutils literal"><span class="pre">iter</span></tt>.</td>
1334</tr>
1335</tbody>
1336</table>
1337<p><tt class="docutils literal"><span class="pre">Base</span> <span class="pre">const&amp;</span> <span class="pre">base()</span> <span class="pre">const;</span></tt></p>
1338<table class="docutils field-list" frame="void" rules="none">
1339<col class="field-name" />
1340<col class="field-body" />
1341<tbody valign="top">
1342<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_iterator</span></tt></td>
1343</tr>
1344</tbody>
1345</table>
1346</div>
1347<div class="section" id="iterator-adaptor-protected-member-functions">
1348<h3><a class="toc-backref" href="#id38"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> protected member functions</a></h3>
1349<p><tt class="docutils literal"><span class="pre">Base</span> <span class="pre">const&amp;</span> <span class="pre">base_reference()</span> <span class="pre">const;</span></tt></p>
1350<table class="docutils field-list" frame="void" rules="none">
1351<col class="field-name" />
1352<col class="field-body" />
1353<tbody valign="top">
1354<tr class="field"><th class="field-name">Returns:</th><td class="field-body">A const reference to <tt class="docutils literal"><span class="pre">m_iterator</span></tt>.</td>
1355</tr>
1356</tbody>
1357</table>
1358<p><tt class="docutils literal"><span class="pre">Base&amp;</span> <span class="pre">base_reference();</span></tt></p>
1359<table class="docutils field-list" frame="void" rules="none">
1360<col class="field-name" />
1361<col class="field-body" />
1362<tbody valign="top">
1363<tr class="field"><th class="field-name">Returns:</th><td class="field-body">A non-const reference to <tt class="docutils literal"><span class="pre">m_iterator</span></tt>.</td>
1364</tr>
1365</tbody>
1366</table>
1367</div>
1368<div class="section" id="iterator-adaptor-private-member-functions">
1369<h3><a class="toc-backref" href="#id39"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> private member functions</a></h3>
1370<p><tt class="docutils literal"><span class="pre">typename</span> <span class="pre">iterator_adaptor::reference</span> <span class="pre">dereference()</span> <span class="pre">const;</span></tt></p>
1371<table class="docutils field-list" frame="void" rules="none">
1372<col class="field-name" />
1373<col class="field-body" />
1374<tbody valign="top">
1375<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*m_iterator</span></tt></td>
1376</tr>
1377</tbody>
1378</table>
1379<pre class="literal-block">
1380template &lt;
1381class OtherDerived, class OtherIterator, class V, class C, class R, class D
1382&gt;
1383bool equal(iterator_adaptor&lt;OtherDerived, OtherIterator, V, C, R, D&gt; const&amp; x) const;
1384</pre>
1385<table class="docutils field-list" frame="void" rules="none">
1386<col class="field-name" />
1387<col class="field-body" />
1388<tbody valign="top">
1389<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_iterator</span> <span class="pre">==</span> <span class="pre">x.base()</span></tt></td>
1390</tr>
1391</tbody>
1392</table>
1393<p><tt class="docutils literal"><span class="pre">void</span> <span class="pre">advance(typename</span> <span class="pre">iterator_adaptor::difference_type</span> <span class="pre">n);</span></tt></p>
1394<table class="docutils field-list" frame="void" rules="none">
1395<col class="field-name" />
1396<col class="field-body" />
1397<tbody valign="top">
1398<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_iterator</span> <span class="pre">+=</span> <span class="pre">n;</span></tt></td>
1399</tr>
1400</tbody>
1401</table>
1402<p><tt class="docutils literal"><span class="pre">void</span> <span class="pre">increment();</span></tt></p>
1403<table class="docutils field-list" frame="void" rules="none">
1404<col class="field-name" />
1405<col class="field-body" />
1406<tbody valign="top">
1407<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><tt class="docutils literal"><span class="pre">++m_iterator;</span></tt></td>
1408</tr>
1409</tbody>
1410</table>
1411<p><tt class="docutils literal"><span class="pre">void</span> <span class="pre">decrement();</span></tt></p>
1412<table class="docutils field-list" frame="void" rules="none">
1413<col class="field-name" />
1414<col class="field-body" />
1415<tbody valign="top">
1416<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><tt class="docutils literal"><span class="pre">--m_iterator;</span></tt></td>
1417</tr>
1418</tbody>
1419</table>
1420<pre class="literal-block">
1421template &lt;
1422    class OtherDerived, class OtherIterator, class V, class C, class R, class D
1423&gt;
1424typename iterator_adaptor::difference_type distance_to(
1425    iterator_adaptor&lt;OtherDerived, OtherIterator, V, C, R, D&gt; const&amp; y) const;
1426</pre>
1427<table class="docutils field-list" frame="void" rules="none">
1428<col class="field-name" />
1429<col class="field-body" />
1430<tbody valign="top">
1431<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">y.base()</span> <span class="pre">-</span> <span class="pre">m_iterator</span></tt></td>
1432</tr>
1433</tbody>
1434</table>
1435</div>
1436</div>
1437<div class="section" id="specialized-adaptors-lib-iterator-special-adaptors">
1438<h2><a class="toc-backref" href="#id40">Specialized adaptors [lib.iterator.special.adaptors]</a></h2>
1439<p>The <tt class="docutils literal"><span class="pre">enable_if_convertible&lt;X,Y&gt;::type</span></tt> expression used in
1440this section is for exposition purposes. The converting constructors
1441for specialized adaptors should be only be in an overload set provided
1442that an object of type <tt class="docutils literal"><span class="pre">X</span></tt> is implicitly convertible to an object of
1443type <tt class="docutils literal"><span class="pre">Y</span></tt>.
1444The signatures involving <tt class="docutils literal"><span class="pre">enable_if_convertible</span></tt> should behave
1445<em>as-if</em> <tt class="docutils literal"><span class="pre">enable_if_convertible</span></tt> were defined to be:</p>
1446<pre class="literal-block">
1447template &lt;bool&gt; enable_if_convertible_impl
1448{};
1449
1450template &lt;&gt; enable_if_convertible_impl&lt;true&gt;
1451{ struct type; };
1452
1453template&lt;typename From, typename To&gt;
1454struct enable_if_convertible
1455  : enable_if_convertible_impl&lt;is_convertible&lt;From,To&gt;::value&gt;
1456{};
1457</pre>
1458<p>If an expression other than the default argument is used to supply
1459the value of a function parameter whose type is written in terms
1460of <tt class="docutils literal"><span class="pre">enable_if_convertible</span></tt>, the program is ill-formed, no
1461diagnostic required.</p>
1462<p>[<em>Note:</em> The <tt class="docutils literal"><span class="pre">enable_if_convertible</span></tt> approach uses SFINAE to
1463take the constructor out of the overload set when the types are not
1464implicitly convertible.
1465]</p>
1466<div class="section" id="indirect-iterator">
1467<h3><a class="toc-backref" href="#id41">Indirect iterator</a></h3>
1468<!-- Copyright David Abrahams 2006. Distributed under the Boost -->
1469<!-- Software License, Version 1.0. (See accompanying -->
1470<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
1471<p><tt class="docutils literal"><span class="pre">indirect_iterator</span></tt> adapts an iterator by applying an
1472<em>extra</em> dereference inside of <tt class="docutils literal"><span class="pre">operator*()</span></tt>. For example, this
1473iterator adaptor makes it possible to view a container of pointers
1474(e.g. <tt class="docutils literal"><span class="pre">list&lt;foo*&gt;</span></tt>) as if it were a container of the pointed-to type
1475(e.g. <tt class="docutils literal"><span class="pre">list&lt;foo&gt;</span></tt>).  <tt class="docutils literal"><span class="pre">indirect_iterator</span></tt> depends on two
1476auxiliary traits, <tt class="docutils literal"><span class="pre">pointee</span></tt> and <tt class="docutils literal"><span class="pre">indirect_reference</span></tt>, to
1477provide support for underlying iterators whose <tt class="docutils literal"><span class="pre">value_type</span></tt> is
1478not an iterator.</p>
1479<div class="section" id="class-template-pointee">
1480<h4><a class="toc-backref" href="#id42">Class template <tt class="docutils literal"><span class="pre">pointee</span></tt></a></h4>
1481<!-- Copyright David Abrahams 2004. Use, modification and distribution is -->
1482<!-- subject to the Boost Software License, Version 1.0. (See accompanying -->
1483<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
1484<pre class="literal-block">
1485template &lt;class Dereferenceable&gt;
1486struct pointee
1487{
1488    typedef /* see below */ type;
1489};
1490</pre>
1491<table class="docutils field-list" frame="void" rules="none">
1492<col class="field-name" />
1493<col class="field-body" />
1494<tbody valign="top">
1495<tr class="field"><th class="field-name">Requires:</th><td class="field-body">For an object <tt class="docutils literal"><span class="pre">x</span></tt> of type <tt class="docutils literal"><span class="pre">Dereferenceable</span></tt>, <tt class="docutils literal"><span class="pre">*x</span></tt>
1496is well-formed.  If <tt class="docutils literal"><span class="pre">++x</span></tt> is ill-formed it shall neither be
1497ambiguous nor shall it violate access control, and
1498<tt class="docutils literal"><span class="pre">Dereferenceable::element_type</span></tt> shall be an accessible type.
1499Otherwise <tt class="docutils literal"><span class="pre">iterator_traits&lt;Dereferenceable&gt;::value_type</span></tt> shall
1500be well formed.  [Note: These requirements need not apply to
1501explicit or partial specializations of <tt class="docutils literal"><span class="pre">pointee</span></tt>]</td>
1502</tr>
1503</tbody>
1504</table>
1505<p><tt class="docutils literal"><span class="pre">type</span></tt> is determined according to the following algorithm, where
1506<tt class="docutils literal"><span class="pre">x</span></tt> is an object of type <tt class="docutils literal"><span class="pre">Dereferenceable</span></tt>:</p>
1507<pre class="literal-block">
1508if ( ++x is ill-formed )
1509{
1510    return ``Dereferenceable::element_type``
1511}
1512else if (``*x`` is a mutable reference to
1513         std::iterator_traits&lt;Dereferenceable&gt;::value_type)
1514{
1515    return iterator_traits&lt;Dereferenceable&gt;::value_type
1516}
1517else
1518{
1519    return iterator_traits&lt;Dereferenceable&gt;::value_type const
1520}
1521</pre>
1522</div>
1523<div class="section" id="class-template-indirect-reference">
1524<h4><a class="toc-backref" href="#id43">Class template <tt class="docutils literal"><span class="pre">indirect_reference</span></tt></a></h4>
1525<!-- Copyright David Abrahams 2004. Use, modification and distribution is -->
1526<!-- subject to the Boost Software License, Version 1.0. (See accompanying -->
1527<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
1528<pre class="literal-block">
1529template &lt;class Dereferenceable&gt;
1530struct indirect_reference
1531{
1532    typedef /* see below */ type;
1533};
1534</pre>
1535<table class="docutils field-list" frame="void" rules="none">
1536<col class="field-name" />
1537<col class="field-body" />
1538<tbody valign="top">
1539<tr class="field"><th class="field-name">Requires:</th><td class="field-body">For an object <tt class="docutils literal"><span class="pre">x</span></tt> of type <tt class="docutils literal"><span class="pre">Dereferenceable</span></tt>, <tt class="docutils literal"><span class="pre">*x</span></tt>
1540is well-formed.  If <tt class="docutils literal"><span class="pre">++x</span></tt> is ill-formed it shall neither be
1541ambiguous nor shall it violate access control, and
1542<tt class="docutils literal"><span class="pre">pointee&lt;Dereferenceable&gt;::type&amp;</span></tt> shall be well-formed.
1543Otherwise <tt class="docutils literal"><span class="pre">iterator_traits&lt;Dereferenceable&gt;::reference</span></tt> shall
1544be well formed.  [Note: These requirements need not apply to
1545explicit or partial specializations of <tt class="docutils literal"><span class="pre">indirect_reference</span></tt>]</td>
1546</tr>
1547</tbody>
1548</table>
1549<p><tt class="docutils literal"><span class="pre">type</span></tt> is determined according to the following algorithm, where
1550<tt class="docutils literal"><span class="pre">x</span></tt> is an object of type <tt class="docutils literal"><span class="pre">Dereferenceable</span></tt>:</p>
1551<pre class="literal-block">
1552if ( ++x is ill-formed )
1553    return ``pointee&lt;Dereferenceable&gt;::type&amp;``
1554else
1555    std::iterator_traits&lt;Dereferenceable&gt;::reference
1556</pre>
1557</div>
1558<div class="section" id="class-template-indirect-iterator">
1559<h4><a class="toc-backref" href="#id44">Class template <tt class="docutils literal"><span class="pre">indirect_iterator</span></tt></a></h4>
1560<!-- Copyright David Abrahams 2006. Distributed under the Boost -->
1561<!-- Software License, Version 1.0. (See accompanying -->
1562<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
1563<pre class="literal-block">
1564template &lt;
1565    class Iterator
1566  , class Value = use_default
1567  , class CategoryOrTraversal = use_default
1568  , class Reference = use_default
1569  , class Difference = use_default
1570&gt;
1571class indirect_iterator
1572{
1573 public:
1574    typedef /* see below */ value_type;
1575    typedef /* see below */ reference;
1576    typedef /* see below */ pointer;
1577    typedef /* see below */ difference_type;
1578    typedef /* see below */ iterator_category;
1579
1580    indirect_iterator();
1581    indirect_iterator(Iterator x);
1582
1583    template &lt;
1584        class Iterator2, class Value2, class Category2
1585      , class Reference2, class Difference2
1586    &gt;
1587    indirect_iterator(
1588        indirect_iterator&lt;
1589             Iterator2, Value2, Category2, Reference2, Difference2
1590        &gt; const&amp; y
1591      , typename enable_if_convertible&lt;Iterator2, Iterator&gt;::type* = 0 // exposition
1592    );
1593
1594    Iterator const&amp; base() const;
1595    reference operator*() const;
1596    indirect_iterator&amp; operator++();
1597    indirect_iterator&amp; operator--();
1598private:
1599   Iterator m_iterator; // exposition
1600};
1601</pre>
1602<p>The member types of <tt class="docutils literal"><span class="pre">indirect_iterator</span></tt> are defined according to
1603the following pseudo-code, where <tt class="docutils literal"><span class="pre">V</span></tt> is
1604<tt class="docutils literal"><span class="pre">iterator_traits&lt;Iterator&gt;::value_type</span></tt></p>
1605<pre class="literal-block">
1606if (Value is use_default) then
1607    typedef remove_const&lt;pointee&lt;V&gt;::type&gt;::type value_type;
1608else
1609    typedef remove_const&lt;Value&gt;::type value_type;
1610
1611if (Reference is use_default) then
1612    if (Value is use_default) then
1613        typedef indirect_reference&lt;V&gt;::type reference;
1614    else
1615        typedef Value&amp; reference;
1616else
1617    typedef Reference reference;
1618
1619if (Value is use_default) then
1620    typedef pointee&lt;V&gt;::type* pointer;
1621else
1622    typedef Value* pointer;
1623
1624if (Difference is use_default)
1625    typedef iterator_traits&lt;Iterator&gt;::difference_type difference_type;
1626else
1627    typedef Difference difference_type;
1628
1629if (CategoryOrTraversal is use_default)
1630    typedef <em>iterator-category</em> (
1631        iterator_traversal&lt;Iterator&gt;::type,``reference``,``value_type``
1632    ) iterator_category;
1633else
1634    typedef <em>iterator-category</em> (
1635        CategoryOrTraversal,``reference``,``value_type``
1636    ) iterator_category;
1637</pre>
1638</div>
1639<div class="section" id="indirect-iterator-requirements">
1640<h4><a class="toc-backref" href="#id45"><tt class="docutils literal"><span class="pre">indirect_iterator</span></tt> requirements</a></h4>
1641<p>The expression <tt class="docutils literal"><span class="pre">*v</span></tt>, where <tt class="docutils literal"><span class="pre">v</span></tt> is an object of
1642<tt class="docutils literal"><span class="pre">iterator_traits&lt;Iterator&gt;::value_type</span></tt>, shall be valid
1643expression and convertible to <tt class="docutils literal"><span class="pre">reference</span></tt>.  <tt class="docutils literal"><span class="pre">Iterator</span></tt> shall
1644model the traversal concept indicated by <tt class="docutils literal"><span class="pre">iterator_category</span></tt>.
1645<tt class="docutils literal"><span class="pre">Value</span></tt>, <tt class="docutils literal"><span class="pre">Reference</span></tt>, and <tt class="docutils literal"><span class="pre">Difference</span></tt> shall be chosen so
1646that <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">difference_type</span></tt> meet
1647the requirements indicated by <tt class="docutils literal"><span class="pre">iterator_category</span></tt>.</p>
1648<p>[Note: there are further requirements on the
1649<tt class="docutils literal"><span class="pre">iterator_traits&lt;Iterator&gt;::value_type</span></tt> if the <tt class="docutils literal"><span class="pre">Value</span></tt>
1650parameter is not <tt class="docutils literal"><span class="pre">use_default</span></tt>, as implied by the algorithm for
1651deducing the default for the <tt class="docutils literal"><span class="pre">value_type</span></tt> member.]</p>
1652</div>
1653<div class="section" id="indirect-iterator-models">
1654<h4><a class="toc-backref" href="#id46"><tt class="docutils literal"><span class="pre">indirect_iterator</span></tt> models</a></h4>
1655<p>In addition to the concepts indicated by <tt class="docutils literal"><span class="pre">iterator_category</span></tt>
1656and by <tt class="docutils literal"><span class="pre">iterator_traversal&lt;indirect_iterator&gt;::type</span></tt>, a
1657specialization of <tt class="docutils literal"><span class="pre">indirect_iterator</span></tt> models the following
1658concepts, Where <tt class="docutils literal"><span class="pre">v</span></tt> is an object of
1659<tt class="docutils literal"><span class="pre">iterator_traits&lt;Iterator&gt;::value_type</span></tt>:</p>
1660<blockquote>
1661<ul class="simple">
1662<li>Readable Iterator if <tt class="docutils literal"><span class="pre">reference(*v)</span></tt> is convertible to
1663<tt class="docutils literal"><span class="pre">value_type</span></tt>.</li>
1664<li>Writable Iterator if <tt class="docutils literal"><span class="pre">reference(*v)</span> <span class="pre">=</span> <span class="pre">t</span></tt> is a valid
1665expression (where <tt class="docutils literal"><span class="pre">t</span></tt> is an object of type
1666<tt class="docutils literal"><span class="pre">indirect_iterator::value_type</span></tt>)</li>
1667<li>Lvalue Iterator if <tt class="docutils literal"><span class="pre">reference</span></tt> is a reference type.</li>
1668</ul>
1669</blockquote>
1670<p><tt class="docutils literal"><span class="pre">indirect_iterator&lt;X,V1,C1,R1,D1&gt;</span></tt> is interoperable with
1671<tt class="docutils literal"><span class="pre">indirect_iterator&lt;Y,V2,C2,R2,D2&gt;</span></tt> if and only if <tt class="docutils literal"><span class="pre">X</span></tt> is
1672interoperable with <tt class="docutils literal"><span class="pre">Y</span></tt>.</p>
1673</div>
1674<div class="section" id="indirect-iterator-operations">
1675<h4><a class="toc-backref" href="#id47"><tt class="docutils literal"><span class="pre">indirect_iterator</span></tt> operations</a></h4>
1676<p>In addition to the operations required by the concepts described
1677above, specializations of <tt class="docutils literal"><span class="pre">indirect_iterator</span></tt> provide the
1678following operations.</p>
1679<p><tt class="docutils literal"><span class="pre">indirect_iterator();</span></tt></p>
1680<table class="docutils field-list" frame="void" rules="none">
1681<col class="field-name" />
1682<col class="field-body" />
1683<tbody valign="top">
1684<tr class="field"><th class="field-name">Requires:</th><td class="field-body"><tt class="docutils literal"><span class="pre">Iterator</span></tt> must be Default Constructible.</td>
1685</tr>
1686<tr class="field"><th class="field-name">Effects:</th><td class="field-body">Constructs an instance of <tt class="docutils literal"><span class="pre">indirect_iterator</span></tt> with
1687a default-constructed <tt class="docutils literal"><span class="pre">m_iterator</span></tt>.</td>
1688</tr>
1689</tbody>
1690</table>
1691<p><tt class="docutils literal"><span class="pre">indirect_iterator(Iterator</span> <span class="pre">x);</span></tt></p>
1692<table class="docutils field-list" frame="void" rules="none">
1693<col class="field-name" />
1694<col class="field-body" />
1695<tbody valign="top">
1696<tr class="field"><th class="field-name">Effects:</th><td class="field-body">Constructs an instance of <tt class="docutils literal"><span class="pre">indirect_iterator</span></tt> with
1697<tt class="docutils literal"><span class="pre">m_iterator</span></tt> copy constructed from <tt class="docutils literal"><span class="pre">x</span></tt>.</td>
1698</tr>
1699</tbody>
1700</table>
1701<pre class="literal-block">
1702template &lt;
1703    class Iterator2, class Value2, unsigned Access, class Traversal
1704  , class Reference2, class Difference2
1705&gt;
1706indirect_iterator(
1707    indirect_iterator&lt;
1708         Iterator2, Value2, Access, Traversal, Reference2, Difference2
1709    &gt; const&amp; y
1710  , typename enable_if_convertible&lt;Iterator2, Iterator&gt;::type* = 0 // exposition
1711);
1712</pre>
1713<table class="docutils field-list" frame="void" rules="none">
1714<col class="field-name" />
1715<col class="field-body" />
1716<tbody valign="top">
1717<tr class="field"><th class="field-name">Requires:</th><td class="field-body"><tt class="docutils literal"><span class="pre">Iterator2</span></tt> is implicitly convertible to <tt class="docutils literal"><span class="pre">Iterator</span></tt>.</td>
1718</tr>
1719<tr class="field"><th class="field-name">Effects:</th><td class="field-body">Constructs an instance of <tt class="docutils literal"><span class="pre">indirect_iterator</span></tt> whose
1720<tt class="docutils literal"><span class="pre">m_iterator</span></tt> subobject is constructed from <tt class="docutils literal"><span class="pre">y.base()</span></tt>.</td>
1721</tr>
1722</tbody>
1723</table>
1724<p><tt class="docutils literal"><span class="pre">Iterator</span> <span class="pre">const&amp;</span> <span class="pre">base()</span> <span class="pre">const;</span></tt></p>
1725<table class="docutils field-list" frame="void" rules="none">
1726<col class="field-name" />
1727<col class="field-body" />
1728<tbody valign="top">
1729<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_iterator</span></tt></td>
1730</tr>
1731</tbody>
1732</table>
1733<p><tt class="docutils literal"><span class="pre">reference</span> <span class="pre">operator*()</span> <span class="pre">const;</span></tt></p>
1734<table class="docutils field-list" frame="void" rules="none">
1735<col class="field-name" />
1736<col class="field-body" />
1737<tbody valign="top">
1738<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">**m_iterator</span></tt></td>
1739</tr>
1740</tbody>
1741</table>
1742<p><tt class="docutils literal"><span class="pre">indirect_iterator&amp;</span> <span class="pre">operator++();</span></tt></p>
1743<table class="docutils field-list" frame="void" rules="none">
1744<col class="field-name" />
1745<col class="field-body" />
1746<tbody valign="top">
1747<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><tt class="docutils literal"><span class="pre">++m_iterator</span></tt></td>
1748</tr>
1749<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*this</span></tt></td>
1750</tr>
1751</tbody>
1752</table>
1753<p><tt class="docutils literal"><span class="pre">indirect_iterator&amp;</span> <span class="pre">operator--();</span></tt></p>
1754<table class="docutils field-list" frame="void" rules="none">
1755<col class="field-name" />
1756<col class="field-body" />
1757<tbody valign="top">
1758<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><tt class="docutils literal"><span class="pre">--m_iterator</span></tt></td>
1759</tr>
1760<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*this</span></tt></td>
1761</tr>
1762</tbody>
1763</table>
1764</div>
1765</div>
1766<div class="section" id="reverse-iterator">
1767<h3><a class="toc-backref" href="#id48">Reverse iterator</a></h3>
1768<!-- Copyright David Abrahams 2006. Distributed under the Boost -->
1769<!-- Software License, Version 1.0. (See accompanying -->
1770<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
1771<p>The reverse iterator adaptor iterates through the adapted iterator
1772range in the opposite direction.</p>
1773<div class="section" id="class-template-reverse-iterator">
1774<h4><a class="toc-backref" href="#id49">Class template <tt class="docutils literal"><span class="pre">reverse_iterator</span></tt></a></h4>
1775<!-- Copyright David Abrahams 2006. Distributed under the Boost -->
1776<!-- Software License, Version 1.0. (See accompanying -->
1777<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
1778<pre class="literal-block">
1779template &lt;class Iterator&gt;
1780class reverse_iterator
1781{
1782public:
1783  typedef iterator_traits&lt;Iterator&gt;::value_type value_type;
1784  typedef iterator_traits&lt;Iterator&gt;::reference reference;
1785  typedef iterator_traits&lt;Iterator&gt;::pointer pointer;
1786  typedef iterator_traits&lt;Iterator&gt;::difference_type difference_type;
1787  typedef /* see below */ iterator_category;
1788
1789  reverse_iterator() {}
1790  explicit reverse_iterator(Iterator x) ;
1791
1792  template&lt;class OtherIterator&gt;
1793  reverse_iterator(
1794      reverse_iterator&lt;OtherIterator&gt; const&amp; r
1795    , typename enable_if_convertible&lt;OtherIterator, Iterator&gt;::type* = 0 // exposition
1796  );
1797  Iterator const&amp; base() const;
1798  reference operator*() const;
1799  reverse_iterator&amp; operator++();
1800  reverse_iterator&amp; operator--();
1801private:
1802  Iterator m_iterator; // exposition
1803};
1804</pre>
1805<p>If <tt class="docutils literal"><span class="pre">Iterator</span></tt> models Random Access Traversal Iterator and Readable
1806Lvalue Iterator, then <tt class="docutils literal"><span class="pre">iterator_category</span></tt> is convertible to
1807<tt class="docutils literal"><span class="pre">random_access_iterator_tag</span></tt>. Otherwise, if
1808<tt class="docutils literal"><span class="pre">Iterator</span></tt> models Bidirectional Traversal Iterator and Readable
1809Lvalue Iterator, then <tt class="docutils literal"><span class="pre">iterator_category</span></tt> is convertible to
1810<tt class="docutils literal"><span class="pre">bidirectional_iterator_tag</span></tt>. Otherwise, <tt class="docutils literal"><span class="pre">iterator_category</span></tt> is
1811convertible to <tt class="docutils literal"><span class="pre">input_iterator_tag</span></tt>.</p>
1812</div>
1813<div class="section" id="reverse-iterator-requirements">
1814<h4><a class="toc-backref" href="#id50"><tt class="docutils literal"><span class="pre">reverse_iterator</span></tt> requirements</a></h4>
1815<p><tt class="docutils literal"><span class="pre">Iterator</span></tt> must be a model of Bidirectional Traversal Iterator.  The
1816type <tt class="docutils literal"><span class="pre">iterator_traits&lt;Iterator&gt;::reference</span></tt> must be the type of
1817<tt class="docutils literal"><span class="pre">*i</span></tt>, where <tt class="docutils literal"><span class="pre">i</span></tt> is an object of type <tt class="docutils literal"><span class="pre">Iterator</span></tt>.</p>
1818</div>
1819<div class="section" id="reverse-iterator-models">
1820<h4><a class="toc-backref" href="#id51"><tt class="docutils literal"><span class="pre">reverse_iterator</span></tt> models</a></h4>
1821<p>A specialization of <tt class="docutils literal"><span class="pre">reverse_iterator</span></tt> models the same iterator
1822traversal and iterator access concepts modeled by its <tt class="docutils literal"><span class="pre">Iterator</span></tt>
1823argument.  In addition, it may model old iterator concepts
1824specified in the following table:</p>
1825<table border="1" class="docutils">
1826<colgroup>
1827<col width="53%" />
1828<col width="47%" />
1829</colgroup>
1830<thead valign="bottom">
1831<tr><th class="head">If <tt class="docutils literal"><span class="pre">I</span></tt> models</th>
1832<th class="head">then <tt class="docutils literal"><span class="pre">reverse_iterator&lt;I&gt;</span></tt> models</th>
1833</tr>
1834</thead>
1835<tbody valign="top">
1836<tr><td>Readable Lvalue Iterator,
1837Bidirectional Traversal Iterator</td>
1838<td>Bidirectional Iterator</td>
1839</tr>
1840<tr><td>Writable Lvalue Iterator,
1841Bidirectional Traversal Iterator</td>
1842<td>Mutable Bidirectional Iterator</td>
1843</tr>
1844<tr><td>Readable Lvalue Iterator,
1845Random Access Traversal Iterator</td>
1846<td>Random Access Iterator</td>
1847</tr>
1848<tr><td>Writable Lvalue Iterator,
1849Random Access Traversal Iterator</td>
1850<td>Mutable Random Access Iterator</td>
1851</tr>
1852</tbody>
1853</table>
1854<p><tt class="docutils literal"><span class="pre">reverse_iterator&lt;X&gt;</span></tt> is interoperable with
1855<tt class="docutils literal"><span class="pre">reverse_iterator&lt;Y&gt;</span></tt> if and only if <tt class="docutils literal"><span class="pre">X</span></tt> is interoperable with
1856<tt class="docutils literal"><span class="pre">Y</span></tt>.</p>
1857</div>
1858<div class="section" id="reverse-iterator-operations">
1859<h4><a class="toc-backref" href="#id52"><tt class="docutils literal"><span class="pre">reverse_iterator</span></tt> operations</a></h4>
1860<p>In addition to the operations required by the concepts modeled by
1861<tt class="docutils literal"><span class="pre">reverse_iterator</span></tt>, <tt class="docutils literal"><span class="pre">reverse_iterator</span></tt> provides the following
1862operations.</p>
1863<p><tt class="docutils literal"><span class="pre">reverse_iterator();</span></tt></p>
1864<table class="docutils field-list" frame="void" rules="none">
1865<col class="field-name" />
1866<col class="field-body" />
1867<tbody valign="top">
1868<tr class="field"><th class="field-name">Requires:</th><td class="field-body"><tt class="docutils literal"><span class="pre">Iterator</span></tt> must be Default Constructible.</td>
1869</tr>
1870<tr class="field"><th class="field-name">Effects:</th><td class="field-body">Constructs an instance of <tt class="docutils literal"><span class="pre">reverse_iterator</span></tt> with <tt class="docutils literal"><span class="pre">m_iterator</span></tt>
1871default constructed.</td>
1872</tr>
1873</tbody>
1874</table>
1875<p><tt class="docutils literal"><span class="pre">explicit</span> <span class="pre">reverse_iterator(Iterator</span> <span class="pre">x);</span></tt></p>
1876<table class="docutils field-list" frame="void" rules="none">
1877<col class="field-name" />
1878<col class="field-body" />
1879<tbody valign="top">
1880<tr class="field"><th class="field-name">Effects:</th><td class="field-body">Constructs an instance of <tt class="docutils literal"><span class="pre">reverse_iterator</span></tt> with
1881<tt class="docutils literal"><span class="pre">m_iterator</span></tt> copy constructed from <tt class="docutils literal"><span class="pre">x</span></tt>.</td>
1882</tr>
1883</tbody>
1884</table>
1885<pre class="literal-block">
1886template&lt;class OtherIterator&gt;
1887reverse_iterator(
1888    reverse_iterator&lt;OtherIterator&gt; const&amp; r
1889  , typename enable_if_convertible&lt;OtherIterator, Iterator&gt;::type* = 0 // exposition
1890);
1891</pre>
1892<table class="docutils field-list" frame="void" rules="none">
1893<col class="field-name" />
1894<col class="field-body" />
1895<tbody valign="top">
1896<tr class="field"><th class="field-name">Requires:</th><td class="field-body"><tt class="docutils literal"><span class="pre">OtherIterator</span></tt> is implicitly convertible to <tt class="docutils literal"><span class="pre">Iterator</span></tt>.</td>
1897</tr>
1898<tr class="field"><th class="field-name">Effects:</th><td class="field-body">Constructs instance of <tt class="docutils literal"><span class="pre">reverse_iterator</span></tt> whose
1899<tt class="docutils literal"><span class="pre">m_iterator</span></tt> subobject is constructed from <tt class="docutils literal"><span class="pre">y.base()</span></tt>.</td>
1900</tr>
1901</tbody>
1902</table>
1903<p><tt class="docutils literal"><span class="pre">Iterator</span> <span class="pre">const&amp;</span> <span class="pre">base()</span> <span class="pre">const;</span></tt></p>
1904<table class="docutils field-list" frame="void" rules="none">
1905<col class="field-name" />
1906<col class="field-body" />
1907<tbody valign="top">
1908<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_iterator</span></tt></td>
1909</tr>
1910</tbody>
1911</table>
1912<p><tt class="docutils literal"><span class="pre">reference</span> <span class="pre">operator*()</span> <span class="pre">const;</span></tt></p>
1913<table class="docutils field-list" frame="void" rules="none">
1914<col class="field-name" />
1915<col class="field-body" />
1916<tbody valign="top">
1917<tr class="field"><th class="field-name">Effects:</th><td class="field-body"></td>
1918</tr>
1919</tbody>
1920</table>
1921<pre class="literal-block">
1922Iterator tmp = m_iterator;
1923return *--tmp;
1924</pre>
1925<p><tt class="docutils literal"><span class="pre">reverse_iterator&amp;</span> <span class="pre">operator++();</span></tt></p>
1926<table class="docutils field-list" frame="void" rules="none">
1927<col class="field-name" />
1928<col class="field-body" />
1929<tbody valign="top">
1930<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><tt class="docutils literal"><span class="pre">--m_iterator</span></tt></td>
1931</tr>
1932<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*this</span></tt></td>
1933</tr>
1934</tbody>
1935</table>
1936<p><tt class="docutils literal"><span class="pre">reverse_iterator&amp;</span> <span class="pre">operator--();</span></tt></p>
1937<table class="docutils field-list" frame="void" rules="none">
1938<col class="field-name" />
1939<col class="field-body" />
1940<tbody valign="top">
1941<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><tt class="docutils literal"><span class="pre">++m_iterator</span></tt></td>
1942</tr>
1943<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*this</span></tt></td>
1944</tr>
1945</tbody>
1946</table>
1947</div>
1948</div>
1949<div class="section" id="transform-iterator">
1950<h3><a class="toc-backref" href="#id53">Transform iterator</a></h3>
1951<!-- Copyright David Abrahams 2006. Distributed under the Boost -->
1952<!-- Software License, Version 1.0. (See accompanying -->
1953<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
1954<p>The transform iterator adapts an iterator by modifying the
1955<tt class="docutils literal"><span class="pre">operator*</span></tt> to apply a function object to the result of
1956dereferencing the iterator and returning the result.</p>
1957<div class="section" id="class-template-transform-iterator">
1958<h4><a class="toc-backref" href="#id54">Class template <tt class="docutils literal"><span class="pre">transform_iterator</span></tt></a></h4>
1959<!-- Copyright David Abrahams 2006. Distributed under the Boost -->
1960<!-- Software License, Version 1.0. (See accompanying -->
1961<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
1962<!-- Version 1.3 of this document was accepted for TR1 -->
1963<pre class="literal-block">
1964template &lt;class UnaryFunction,
1965          class Iterator,
1966          class Reference = use_default,
1967          class Value = use_default&gt;
1968class transform_iterator
1969{
1970public:
1971  typedef /* see below */ value_type;
1972  typedef /* see below */ reference;
1973  typedef /* see below */ pointer;
1974  typedef iterator_traits&lt;Iterator&gt;::difference_type difference_type;
1975  typedef /* see below */ iterator_category;
1976
1977  transform_iterator();
1978  transform_iterator(Iterator const&amp; x, UnaryFunction f);
1979
1980  template&lt;class F2, class I2, class R2, class V2&gt;
1981  transform_iterator(
1982        transform_iterator&lt;F2, I2, R2, V2&gt; const&amp; t
1983      , typename enable_if_convertible&lt;I2, Iterator&gt;::type* = 0      // exposition only
1984      , typename enable_if_convertible&lt;F2, UnaryFunction&gt;::type* = 0 // exposition only
1985  );
1986  UnaryFunction functor() const;
1987  Iterator const&amp; base() const;
1988  reference operator*() const;
1989  transform_iterator&amp; operator++();
1990  transform_iterator&amp; operator--();
1991private:
1992  Iterator m_iterator; // exposition only
1993  UnaryFunction m_f;   // exposition only
1994};
1995</pre>
1996<p>If <tt class="docutils literal"><span class="pre">Reference</span></tt> is <tt class="docutils literal"><span class="pre">use_default</span></tt> then the <tt class="docutils literal"><span class="pre">reference</span></tt> member of
1997<tt class="docutils literal"><span class="pre">transform_iterator</span></tt> is
1998<tt class="docutils literal"><span class="pre">result_of&lt;UnaryFunction(iterator_traits&lt;Iterator&gt;::reference)&gt;::type</span></tt>.
1999Otherwise, <tt class="docutils literal"><span class="pre">reference</span></tt> is <tt class="docutils literal"><span class="pre">Reference</span></tt>.</p>
2000<p>If <tt class="docutils literal"><span class="pre">Value</span></tt> is <tt class="docutils literal"><span class="pre">use_default</span></tt> then the <tt class="docutils literal"><span class="pre">value_type</span></tt> member is
2001<tt class="docutils literal"><span class="pre">remove_cv&lt;remove_reference&lt;reference&gt;</span> <span class="pre">&gt;::type</span></tt>.  Otherwise,
2002<tt class="docutils literal"><span class="pre">value_type</span></tt> is <tt class="docutils literal"><span class="pre">Value</span></tt>.</p>
2003<p>If <tt class="docutils literal"><span class="pre">Iterator</span></tt> models Readable Lvalue Iterator and if <tt class="docutils literal"><span class="pre">Iterator</span></tt>
2004models Random Access Traversal Iterator, then <tt class="docutils literal"><span class="pre">iterator_category</span></tt> is
2005convertible to <tt class="docutils literal"><span class="pre">random_access_iterator_tag</span></tt>. Otherwise, if
2006<tt class="docutils literal"><span class="pre">Iterator</span></tt> models Bidirectional Traversal Iterator, then
2007<tt class="docutils literal"><span class="pre">iterator_category</span></tt> is convertible to
2008<tt class="docutils literal"><span class="pre">bidirectional_iterator_tag</span></tt>.  Otherwise <tt class="docutils literal"><span class="pre">iterator_category</span></tt> is
2009convertible to <tt class="docutils literal"><span class="pre">forward_iterator_tag</span></tt>. If <tt class="docutils literal"><span class="pre">Iterator</span></tt> does not
2010model Readable Lvalue Iterator then <tt class="docutils literal"><span class="pre">iterator_category</span></tt> is
2011convertible to <tt class="docutils literal"><span class="pre">input_iterator_tag</span></tt>.</p>
2012</div>
2013<div class="section" id="transform-iterator-requirements">
2014<h4><a class="toc-backref" href="#id55"><tt class="docutils literal"><span class="pre">transform_iterator</span></tt> requirements</a></h4>
2015<p>The type <tt class="docutils literal"><span class="pre">UnaryFunction</span></tt> must be Assignable, Copy Constructible, and
2016the expression <tt class="docutils literal"><span class="pre">f(*i)</span></tt> must be valid where <tt class="docutils literal"><span class="pre">f</span></tt> is an object of
2017type <tt class="docutils literal"><span class="pre">UnaryFunction</span></tt>, <tt class="docutils literal"><span class="pre">i</span></tt> is an object of type <tt class="docutils literal"><span class="pre">Iterator</span></tt>, and
2018where the type of <tt class="docutils literal"><span class="pre">f(*i)</span></tt> must be
2019<tt class="docutils literal"><span class="pre">result_of&lt;UnaryFunction(iterator_traits&lt;Iterator&gt;::reference)&gt;::type</span></tt>.</p>
2020<p>The argument <tt class="docutils literal"><span class="pre">Iterator</span></tt> shall model Readable Iterator.</p>
2021</div>
2022<div class="section" id="transform-iterator-models">
2023<h4><a class="toc-backref" href="#id56"><tt class="docutils literal"><span class="pre">transform_iterator</span></tt> models</a></h4>
2024<p>The resulting <tt class="docutils literal"><span class="pre">transform_iterator</span></tt> models the most refined of the
2025following that is also modeled by <tt class="docutils literal"><span class="pre">Iterator</span></tt>.</p>
2026<blockquote>
2027<ul class="simple">
2028<li>Writable Lvalue Iterator if <tt class="docutils literal"><span class="pre">transform_iterator::reference</span></tt> is a non-const reference.</li>
2029<li>Readable Lvalue Iterator if <tt class="docutils literal"><span class="pre">transform_iterator::reference</span></tt> is a const reference.</li>
2030<li>Readable Iterator otherwise.</li>
2031</ul>
2032</blockquote>
2033<p>The <tt class="docutils literal"><span class="pre">transform_iterator</span></tt> models the most refined standard traversal
2034concept that is modeled by the <tt class="docutils literal"><span class="pre">Iterator</span></tt> argument.</p>
2035<p>If <tt class="docutils literal"><span class="pre">transform_iterator</span></tt> is a model of Readable Lvalue Iterator then
2036it models the following original iterator concepts depending on what
2037the <tt class="docutils literal"><span class="pre">Iterator</span></tt> argument models.</p>
2038<table border="1" class="docutils">
2039<colgroup>
2040<col width="47%" />
2041<col width="53%" />
2042</colgroup>
2043<thead valign="bottom">
2044<tr><th class="head">If <tt class="docutils literal"><span class="pre">Iterator</span></tt> models</th>
2045<th class="head">then <tt class="docutils literal"><span class="pre">transform_iterator</span></tt> models</th>
2046</tr>
2047</thead>
2048<tbody valign="top">
2049<tr><td>Single Pass Iterator</td>
2050<td>Input Iterator</td>
2051</tr>
2052<tr><td>Forward Traversal Iterator</td>
2053<td>Forward Iterator</td>
2054</tr>
2055<tr><td>Bidirectional Traversal Iterator</td>
2056<td>Bidirectional Iterator</td>
2057</tr>
2058<tr><td>Random Access Traversal Iterator</td>
2059<td>Random Access Iterator</td>
2060</tr>
2061</tbody>
2062</table>
2063<p>If <tt class="docutils literal"><span class="pre">transform_iterator</span></tt> models Writable Lvalue Iterator then it is a
2064mutable iterator (as defined in the old iterator requirements).</p>
2065<p><tt class="docutils literal"><span class="pre">transform_iterator&lt;F1,</span> <span class="pre">X,</span> <span class="pre">R1,</span> <span class="pre">V1&gt;</span></tt> is interoperable with
2066<tt class="docutils literal"><span class="pre">transform_iterator&lt;F2,</span> <span class="pre">Y,</span> <span class="pre">R2,</span> <span class="pre">V2&gt;</span></tt> if and only if <tt class="docutils literal"><span class="pre">X</span></tt> is
2067interoperable with <tt class="docutils literal"><span class="pre">Y</span></tt>.</p>
2068</div>
2069<div class="section" id="transform-iterator-operations">
2070<h4><a class="toc-backref" href="#id57"><tt class="docutils literal"><span class="pre">transform_iterator</span></tt> operations</a></h4>
2071<p>In addition to the operations required by the concepts modeled by
2072<tt class="docutils literal"><span class="pre">transform_iterator</span></tt>, <tt class="docutils literal"><span class="pre">transform_iterator</span></tt> provides the following
2073operations.</p>
2074<p><tt class="docutils literal"><span class="pre">transform_iterator();</span></tt></p>
2075<table class="docutils field-list" frame="void" rules="none">
2076<col class="field-name" />
2077<col class="field-body" />
2078<tbody valign="top">
2079<tr class="field"><th class="field-name">Returns:</th><td class="field-body">An instance of <tt class="docutils literal"><span class="pre">transform_iterator</span></tt> with <tt class="docutils literal"><span class="pre">m_f</span></tt>
2080and <tt class="docutils literal"><span class="pre">m_iterator</span></tt> default constructed.</td>
2081</tr>
2082</tbody>
2083</table>
2084<p><tt class="docutils literal"><span class="pre">transform_iterator(Iterator</span> <span class="pre">const&amp;</span> <span class="pre">x,</span> <span class="pre">UnaryFunction</span> <span class="pre">f);</span></tt></p>
2085<table class="docutils field-list" frame="void" rules="none">
2086<col class="field-name" />
2087<col class="field-body" />
2088<tbody valign="top">
2089<tr class="field"><th class="field-name">Returns:</th><td class="field-body">An instance of <tt class="docutils literal"><span class="pre">transform_iterator</span></tt> with <tt class="docutils literal"><span class="pre">m_f</span></tt>
2090initialized to <tt class="docutils literal"><span class="pre">f</span></tt> and <tt class="docutils literal"><span class="pre">m_iterator</span></tt> initialized to <tt class="docutils literal"><span class="pre">x</span></tt>.</td>
2091</tr>
2092</tbody>
2093</table>
2094<pre class="literal-block">
2095template&lt;class F2, class I2, class R2, class V2&gt;
2096transform_iterator(
2097      transform_iterator&lt;F2, I2, R2, V2&gt; const&amp; t
2098    , typename enable_if_convertible&lt;I2, Iterator&gt;::type* = 0      // exposition only
2099    , typename enable_if_convertible&lt;F2, UnaryFunction&gt;::type* = 0 // exposition only
2100);
2101</pre>
2102<table class="docutils field-list" frame="void" rules="none">
2103<col class="field-name" />
2104<col class="field-body" />
2105<tbody valign="top">
2106<tr class="field"><th class="field-name">Returns:</th><td class="field-body">An instance of <tt class="docutils literal"><span class="pre">transform_iterator</span></tt> with <tt class="docutils literal"><span class="pre">m_f</span></tt>
2107initialized to <tt class="docutils literal"><span class="pre">t.functor()</span></tt> and <tt class="docutils literal"><span class="pre">m_iterator</span></tt> initialized to
2108<tt class="docutils literal"><span class="pre">t.base()</span></tt>.</td>
2109</tr>
2110<tr class="field"><th class="field-name">Requires:</th><td class="field-body"><tt class="docutils literal"><span class="pre">OtherIterator</span></tt> is implicitly convertible to <tt class="docutils literal"><span class="pre">Iterator</span></tt>.</td>
2111</tr>
2112</tbody>
2113</table>
2114<p><tt class="docutils literal"><span class="pre">UnaryFunction</span> <span class="pre">functor()</span> <span class="pre">const;</span></tt></p>
2115<table class="docutils field-list" frame="void" rules="none">
2116<col class="field-name" />
2117<col class="field-body" />
2118<tbody valign="top">
2119<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_f</span></tt></td>
2120</tr>
2121</tbody>
2122</table>
2123<p><tt class="docutils literal"><span class="pre">Iterator</span> <span class="pre">const&amp;</span> <span class="pre">base()</span> <span class="pre">const;</span></tt></p>
2124<table class="docutils field-list" frame="void" rules="none">
2125<col class="field-name" />
2126<col class="field-body" />
2127<tbody valign="top">
2128<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_iterator</span></tt></td>
2129</tr>
2130</tbody>
2131</table>
2132<p><tt class="docutils literal"><span class="pre">reference</span> <span class="pre">operator*()</span> <span class="pre">const;</span></tt></p>
2133<table class="docutils field-list" frame="void" rules="none">
2134<col class="field-name" />
2135<col class="field-body" />
2136<tbody valign="top">
2137<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_f(*m_iterator)</span></tt></td>
2138</tr>
2139</tbody>
2140</table>
2141<p><tt class="docutils literal"><span class="pre">transform_iterator&amp;</span> <span class="pre">operator++();</span></tt></p>
2142<table class="docutils field-list" frame="void" rules="none">
2143<col class="field-name" />
2144<col class="field-body" />
2145<tbody valign="top">
2146<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><tt class="docutils literal"><span class="pre">++m_iterator</span></tt></td>
2147</tr>
2148<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*this</span></tt></td>
2149</tr>
2150</tbody>
2151</table>
2152<p><tt class="docutils literal"><span class="pre">transform_iterator&amp;</span> <span class="pre">operator--();</span></tt></p>
2153<table class="docutils field-list" frame="void" rules="none">
2154<col class="field-name" />
2155<col class="field-body" />
2156<tbody valign="top">
2157<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><tt class="docutils literal"><span class="pre">--m_iterator</span></tt></td>
2158</tr>
2159<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*this</span></tt></td>
2160</tr>
2161</tbody>
2162</table>
2163</div>
2164</div>
2165<div class="section" id="filter-iterator">
2166<h3><a class="toc-backref" href="#id58">Filter iterator</a></h3>
2167<!-- Copyright David Abrahams 2006. Distributed under the Boost -->
2168<!-- Software License, Version 1.0. (See accompanying -->
2169<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
2170<p>The filter iterator adaptor creates a view of an iterator range in
2171which some elements of the range are skipped. A predicate function
2172object controls which elements are skipped. When the predicate is
2173applied to an element, if it returns <tt class="docutils literal"><span class="pre">true</span></tt> then the element is
2174retained and if it returns <tt class="docutils literal"><span class="pre">false</span></tt> then the element is skipped
2175over. When skipping over elements, it is necessary for the filter
2176adaptor to know when to stop so as to avoid going past the end of the
2177underlying range. A filter iterator is therefore constructed with pair
2178of iterators indicating the range of elements in the unfiltered
2179sequence to be traversed.</p>
2180<div class="section" id="class-template-filter-iterator">
2181<h4><a class="toc-backref" href="#id59">Class template <tt class="docutils literal"><span class="pre">filter_iterator</span></tt></a></h4>
2182<!-- Copyright David Abrahams, Jeremy Siek, and Thomas Witt -->
2183<!-- 2004. Use, modification and distribution is subject to the Boost -->
2184<!-- Software License, Version 1.0. (See accompanying  file -->
2185<!-- LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
2186<pre class="literal-block">
2187template &lt;class Predicate, class Iterator&gt;
2188class filter_iterator
2189{
2190 public:
2191    typedef iterator_traits&lt;Iterator&gt;::value_type value_type;
2192    typedef iterator_traits&lt;Iterator&gt;::reference reference;
2193    typedef iterator_traits&lt;Iterator&gt;::pointer pointer;
2194    typedef iterator_traits&lt;Iterator&gt;::difference_type difference_type;
2195    typedef /* see below */ iterator_category;
2196
2197    filter_iterator();
2198    filter_iterator(Predicate f, Iterator x, Iterator end = Iterator());
2199    filter_iterator(Iterator x, Iterator end = Iterator());
2200    template&lt;class OtherIterator&gt;
2201    filter_iterator(
2202        filter_iterator&lt;Predicate, OtherIterator&gt; const&amp; t
2203        , typename enable_if_convertible&lt;OtherIterator, Iterator&gt;::type* = 0 // exposition
2204        );
2205    Predicate predicate() const;
2206    Iterator end() const;
2207    Iterator const&amp; base() const;
2208    reference operator*() const;
2209    filter_iterator&amp; operator++();
2210private:
2211    Predicate m_pred; // exposition only
2212    Iterator m_iter;  // exposition only
2213    Iterator m_end;   // exposition only
2214};
2215</pre>
2216<p>If <tt class="docutils literal"><span class="pre">Iterator</span></tt> models Readable Lvalue Iterator and Bidirectional Traversal
2217Iterator then <tt class="docutils literal"><span class="pre">iterator_category</span></tt> is convertible to
2218<tt class="docutils literal"><span class="pre">std::bidirectional_iterator_tag</span></tt>.
2219Otherwise, if <tt class="docutils literal"><span class="pre">Iterator</span></tt> models Readable Lvalue Iterator and Forward Traversal
2220Iterator then <tt class="docutils literal"><span class="pre">iterator_category</span></tt> is convertible to
2221<tt class="docutils literal"><span class="pre">std::forward_iterator_tag</span></tt>.
2222Otherwise <tt class="docutils literal"><span class="pre">iterator_category</span></tt> is
2223convertible to <tt class="docutils literal"><span class="pre">std::input_iterator_tag</span></tt>.</p>
2224</div>
2225<div class="section" id="filter-iterator-requirements">
2226<h4><a class="toc-backref" href="#id60"><tt class="docutils literal"><span class="pre">filter_iterator</span></tt> requirements</a></h4>
2227<p>The <tt class="docutils literal"><span class="pre">Iterator</span></tt> argument shall meet the requirements of Readable
2228Iterator and Single Pass Iterator or it shall meet the requirements of
2229Input Iterator.</p>
2230<p>The <tt class="docutils literal"><span class="pre">Predicate</span></tt> argument must be Assignable, Copy Constructible, and
2231the expression <tt class="docutils literal"><span class="pre">p(x)</span></tt> must be valid where <tt class="docutils literal"><span class="pre">p</span></tt> is an object of type
2232<tt class="docutils literal"><span class="pre">Predicate</span></tt>, <tt class="docutils literal"><span class="pre">x</span></tt> is an object of type
2233<tt class="docutils literal"><span class="pre">iterator_traits&lt;Iterator&gt;::value_type</span></tt>, and where the type of
2234<tt class="docutils literal"><span class="pre">p(x)</span></tt> must be convertible to <tt class="docutils literal"><span class="pre">bool</span></tt>.</p>
2235</div>
2236<div class="section" id="filter-iterator-models">
2237<h4><a class="toc-backref" href="#id61"><tt class="docutils literal"><span class="pre">filter_iterator</span></tt> models</a></h4>
2238<p>The concepts that <tt class="docutils literal"><span class="pre">filter_iterator</span></tt> models are dependent on which
2239concepts the <tt class="docutils literal"><span class="pre">Iterator</span></tt> argument models, as specified in the
2240following tables.</p>
2241<table border="1" class="docutils">
2242<colgroup>
2243<col width="44%" />
2244<col width="56%" />
2245</colgroup>
2246<thead valign="bottom">
2247<tr><th class="head">If <tt class="docutils literal"><span class="pre">Iterator</span></tt> models</th>
2248<th class="head">then <tt class="docutils literal"><span class="pre">filter_iterator</span></tt> models</th>
2249</tr>
2250</thead>
2251<tbody valign="top">
2252<tr><td>Single Pass Iterator</td>
2253<td>Single Pass Iterator</td>
2254</tr>
2255<tr><td>Forward Traversal Iterator</td>
2256<td>Forward Traversal Iterator</td>
2257</tr>
2258<tr><td>Bidirectional Traversal Iterator</td>
2259<td>Bidirectional Traversal Iterator</td>
2260</tr>
2261</tbody>
2262</table>
2263<table border="1" class="docutils">
2264<colgroup>
2265<col width="41%" />
2266<col width="59%" />
2267</colgroup>
2268<thead valign="bottom">
2269<tr><th class="head">If <tt class="docutils literal"><span class="pre">Iterator</span></tt> models</th>
2270<th class="head">then <tt class="docutils literal"><span class="pre">filter_iterator</span></tt> models</th>
2271</tr>
2272</thead>
2273<tbody valign="top">
2274<tr><td>Readable Iterator</td>
2275<td>Readable Iterator</td>
2276</tr>
2277<tr><td>Writable Iterator</td>
2278<td>Writable Iterator</td>
2279</tr>
2280<tr><td>Lvalue Iterator</td>
2281<td>Lvalue Iterator</td>
2282</tr>
2283</tbody>
2284</table>
2285<table border="1" class="docutils">
2286<colgroup>
2287<col width="63%" />
2288<col width="38%" />
2289</colgroup>
2290<thead valign="bottom">
2291<tr><th class="head">If <tt class="docutils literal"><span class="pre">Iterator</span></tt> models</th>
2292<th class="head">then <tt class="docutils literal"><span class="pre">filter_iterator</span></tt> models</th>
2293</tr>
2294</thead>
2295<tbody valign="top">
2296<tr><td>Readable Iterator, Single Pass Iterator</td>
2297<td>Input Iterator</td>
2298</tr>
2299<tr><td>Readable Lvalue Iterator, Forward Traversal Iterator</td>
2300<td>Forward Iterator</td>
2301</tr>
2302<tr><td>Writable Lvalue Iterator, Forward Traversal Iterator</td>
2303<td>Mutable Forward Iterator</td>
2304</tr>
2305<tr><td>Writable Lvalue Iterator, Bidirectional Iterator</td>
2306<td>Mutable Bidirectional Iterator</td>
2307</tr>
2308</tbody>
2309</table>
2310<p><tt class="docutils literal"><span class="pre">filter_iterator&lt;P1,</span> <span class="pre">X&gt;</span></tt> is interoperable with <tt class="docutils literal"><span class="pre">filter_iterator&lt;P2,</span> <span class="pre">Y&gt;</span></tt>
2311if and only if <tt class="docutils literal"><span class="pre">X</span></tt> is interoperable with <tt class="docutils literal"><span class="pre">Y</span></tt>.</p>
2312</div>
2313<div class="section" id="filter-iterator-operations">
2314<h4><a class="toc-backref" href="#id62"><tt class="docutils literal"><span class="pre">filter_iterator</span></tt> operations</a></h4>
2315<p>In addition to those operations required by the concepts that
2316<tt class="docutils literal"><span class="pre">filter_iterator</span></tt> models, <tt class="docutils literal"><span class="pre">filter_iterator</span></tt> provides the following
2317operations.</p>
2318<p><tt class="docutils literal"><span class="pre">filter_iterator();</span></tt></p>
2319<table class="docutils field-list" frame="void" rules="none">
2320<col class="field-name" />
2321<col class="field-body" />
2322<tbody valign="top">
2323<tr class="field"><th class="field-name">Requires:</th><td class="field-body"><tt class="docutils literal"><span class="pre">Predicate</span></tt> and <tt class="docutils literal"><span class="pre">Iterator</span></tt> must be Default Constructible.</td>
2324</tr>
2325<tr class="field"><th class="field-name">Effects:</th><td class="field-body">Constructs a <tt class="docutils literal"><span class="pre">filter_iterator</span></tt> whose``m_pred``,  <tt class="docutils literal"><span class="pre">m_iter</span></tt>, and <tt class="docutils literal"><span class="pre">m_end</span></tt>
2326members are a default constructed.</td>
2327</tr>
2328</tbody>
2329</table>
2330<p><tt class="docutils literal"><span class="pre">filter_iterator(Predicate</span> <span class="pre">f,</span> <span class="pre">Iterator</span> <span class="pre">x,</span> <span class="pre">Iterator</span> <span class="pre">end</span> <span class="pre">=</span> <span class="pre">Iterator());</span></tt></p>
2331<table class="docutils field-list" frame="void" rules="none">
2332<col class="field-name" />
2333<col class="field-body" />
2334<tbody valign="top">
2335<tr class="field"><th class="field-name">Effects:</th><td class="field-body">Constructs a <tt class="docutils literal"><span class="pre">filter_iterator</span></tt> where <tt class="docutils literal"><span class="pre">m_iter</span></tt> is either
2336the first position in the range <tt class="docutils literal"><span class="pre">[x,end)</span></tt> such that <tt class="docutils literal"><span class="pre">f(*m_iter)</span> <span class="pre">==</span> <span class="pre">true</span></tt>
2337or else``m_iter == end``. The member <tt class="docutils literal"><span class="pre">m_pred</span></tt> is constructed from
2338<tt class="docutils literal"><span class="pre">f</span></tt> and <tt class="docutils literal"><span class="pre">m_end</span></tt> from <tt class="docutils literal"><span class="pre">end</span></tt>.</td>
2339</tr>
2340</tbody>
2341</table>
2342<p><tt class="docutils literal"><span class="pre">filter_iterator(Iterator</span> <span class="pre">x,</span> <span class="pre">Iterator</span> <span class="pre">end</span> <span class="pre">=</span> <span class="pre">Iterator());</span></tt></p>
2343<table class="docutils field-list" frame="void" rules="none">
2344<col class="field-name" />
2345<col class="field-body" />
2346<tbody valign="top">
2347<tr class="field"><th class="field-name">Requires:</th><td class="field-body"><tt class="docutils literal"><span class="pre">Predicate</span></tt> must be Default Constructible and
2348<tt class="docutils literal"><span class="pre">Predicate</span></tt> is a class type (not a function pointer).</td>
2349</tr>
2350<tr class="field"><th class="field-name">Effects:</th><td class="field-body">Constructs a <tt class="docutils literal"><span class="pre">filter_iterator</span></tt> where <tt class="docutils literal"><span class="pre">m_iter</span></tt> is either
2351the first position in the range <tt class="docutils literal"><span class="pre">[x,end)</span></tt> such that <tt class="docutils literal"><span class="pre">m_pred(*m_iter)</span> <span class="pre">==</span> <span class="pre">true</span></tt>
2352or else``m_iter == end``. The member <tt class="docutils literal"><span class="pre">m_pred</span></tt> is default constructed.</td>
2353</tr>
2354</tbody>
2355</table>
2356<pre class="literal-block">
2357template &lt;class OtherIterator&gt;
2358filter_iterator(
2359    filter_iterator&lt;Predicate, OtherIterator&gt; const&amp; t
2360    , typename enable_if_convertible&lt;OtherIterator, Iterator&gt;::type* = 0 // exposition
2361    );``
2362</pre>
2363<table class="docutils field-list" frame="void" rules="none">
2364<col class="field-name" />
2365<col class="field-body" />
2366<tbody valign="top">
2367<tr class="field"><th class="field-name">Requires:</th><td class="field-body"><tt class="docutils literal"><span class="pre">OtherIterator</span></tt> is implicitly convertible to <tt class="docutils literal"><span class="pre">Iterator</span></tt>.</td>
2368</tr>
2369<tr class="field"><th class="field-name">Effects:</th><td class="field-body">Constructs a filter iterator whose members are copied from <tt class="docutils literal"><span class="pre">t</span></tt>.</td>
2370</tr>
2371</tbody>
2372</table>
2373<p><tt class="docutils literal"><span class="pre">Predicate</span> <span class="pre">predicate()</span> <span class="pre">const;</span></tt></p>
2374<table class="docutils field-list" frame="void" rules="none">
2375<col class="field-name" />
2376<col class="field-body" />
2377<tbody valign="top">
2378<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_pred</span></tt></td>
2379</tr>
2380</tbody>
2381</table>
2382<p><tt class="docutils literal"><span class="pre">Iterator</span> <span class="pre">end()</span> <span class="pre">const;</span></tt></p>
2383<table class="docutils field-list" frame="void" rules="none">
2384<col class="field-name" />
2385<col class="field-body" />
2386<tbody valign="top">
2387<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_end</span></tt></td>
2388</tr>
2389</tbody>
2390</table>
2391<p><tt class="docutils literal"><span class="pre">Iterator</span> <span class="pre">const&amp;</span> <span class="pre">base()</span> <span class="pre">const;</span></tt></p>
2392<table class="docutils field-list" frame="void" rules="none">
2393<col class="field-name" />
2394<col class="field-body" />
2395<tbody valign="top">
2396<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_iterator</span></tt></td>
2397</tr>
2398</tbody>
2399</table>
2400<p><tt class="docutils literal"><span class="pre">reference</span> <span class="pre">operator*()</span> <span class="pre">const;</span></tt></p>
2401<table class="docutils field-list" frame="void" rules="none">
2402<col class="field-name" />
2403<col class="field-body" />
2404<tbody valign="top">
2405<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*m_iter</span></tt></td>
2406</tr>
2407</tbody>
2408</table>
2409<p><tt class="docutils literal"><span class="pre">filter_iterator&amp;</span> <span class="pre">operator++();</span></tt></p>
2410<table class="docutils field-list" frame="void" rules="none">
2411<col class="field-name" />
2412<col class="field-body" />
2413<tbody valign="top">
2414<tr class="field"><th class="field-name">Effects:</th><td class="field-body">Increments <tt class="docutils literal"><span class="pre">m_iter</span></tt> and then continues to
2415increment <tt class="docutils literal"><span class="pre">m_iter</span></tt> until either <tt class="docutils literal"><span class="pre">m_iter</span> <span class="pre">==</span> <span class="pre">m_end</span></tt>
2416or <tt class="docutils literal"><span class="pre">m_pred(*m_iter)</span> <span class="pre">==</span> <span class="pre">true</span></tt>.</td>
2417</tr>
2418<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*this</span></tt></td>
2419</tr>
2420</tbody>
2421</table>
2422</div>
2423</div>
2424<div class="section" id="counting-iterator">
2425<h3><a class="toc-backref" href="#id63">Counting iterator</a></h3>
2426<!-- Copyright David Abrahams 2006. Distributed under the Boost -->
2427<!-- Software License, Version 1.0. (See accompanying -->
2428<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
2429<p><tt class="docutils literal"><span class="pre">counting_iterator</span></tt> adapts an object by adding an <tt class="docutils literal"><span class="pre">operator*</span></tt> that
2430returns the current value of the object. All other iterator operations
2431are forwarded to the adapted object.</p>
2432<div class="section" id="class-template-counting-iterator">
2433<h4><a class="toc-backref" href="#id64">Class template <tt class="docutils literal"><span class="pre">counting_iterator</span></tt></a></h4>
2434<!-- Copyright David Abrahams 2006. Distributed under the Boost -->
2435<!-- Software License, Version 1.0. (See accompanying -->
2436<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
2437<pre class="literal-block">
2438template &lt;
2439    class Incrementable
2440  , class CategoryOrTraversal = use_default
2441  , class Difference = use_default
2442&gt;
2443class counting_iterator
2444{
2445public:
2446    typedef Incrementable value_type;
2447    typedef const Incrementable&amp; reference;
2448    typedef const Incrementable* pointer;
2449    typedef /* see below */ difference_type;
2450    typedef /* see below */ iterator_category;
2451
2452    counting_iterator();
2453    counting_iterator(counting_iterator const&amp; rhs);
2454    explicit counting_iterator(Incrementable x);
2455    Incrementable const&amp; base() const;
2456    reference operator*() const;
2457    counting_iterator&amp; operator++();
2458    counting_iterator&amp; operator--();
2459private:
2460    Incrementable m_inc; // exposition
2461};
2462</pre>
2463<p>If the <tt class="docutils literal"><span class="pre">Difference</span></tt> argument is <tt class="docutils literal"><span class="pre">use_default</span></tt> then
2464<tt class="docutils literal"><span class="pre">difference_type</span></tt> is an unspecified signed integral
2465type. Otherwise <tt class="docutils literal"><span class="pre">difference_type</span></tt> is <tt class="docutils literal"><span class="pre">Difference</span></tt>.</p>
2466<p><tt class="docutils literal"><span class="pre">iterator_category</span></tt> is determined according to the following
2467algorithm:</p>
2468<pre class="literal-block">
2469if (CategoryOrTraversal is not use_default)
2470    return CategoryOrTraversal
2471else if (numeric_limits&lt;Incrementable&gt;::is_specialized)
2472    return <a class="reference internal" href="#id12"><em>iterator-category</em></a>(
2473        random_access_traversal_tag, Incrementable, const Incrementable&amp;)
2474else
2475    return <a class="reference internal" href="#id12"><em>iterator-category</em></a>(
2476         iterator_traversal&lt;Incrementable&gt;::type,
2477         Incrementable, const Incrementable&amp;)
2478</pre>
2479<dl class="docutils">
2480<dt>[<em>Note:</em> implementers are encouraged to provide an implementation of</dt>
2481<dd><tt class="docutils literal"><span class="pre">operator-</span></tt> and a <tt class="docutils literal"><span class="pre">difference_type</span></tt> that avoids overflows in
2482the cases where <tt class="docutils literal"><span class="pre">std::numeric_limits&lt;Incrementable&gt;::is_specialized</span></tt>
2483is true.]</dd>
2484</dl>
2485</div>
2486<div class="section" id="counting-iterator-requirements">
2487<h4><a class="toc-backref" href="#id65"><tt class="docutils literal"><span class="pre">counting_iterator</span></tt> requirements</a></h4>
2488<p>The <tt class="docutils literal"><span class="pre">Incrementable</span></tt> argument shall be Copy Constructible and Assignable.</p>
2489<p>If <tt class="docutils literal"><span class="pre">iterator_category</span></tt> is convertible to <tt class="docutils literal"><span class="pre">forward_iterator_tag</span></tt>
2490or <tt class="docutils literal"><span class="pre">forward_traversal_tag</span></tt>, the following must be well-formed:</p>
2491<pre class="literal-block">
2492Incrementable i, j;
2493++i;         // pre-increment
2494i == j;      // operator equal
2495</pre>
2496<p>If <tt class="docutils literal"><span class="pre">iterator_category</span></tt> is convertible to
2497<tt class="docutils literal"><span class="pre">bidirectional_iterator_tag</span></tt> or <tt class="docutils literal"><span class="pre">bidirectional_traversal_tag</span></tt>,
2498the following expression must also be well-formed:</p>
2499<pre class="literal-block">
2500--i
2501</pre>
2502<p>If <tt class="docutils literal"><span class="pre">iterator_category</span></tt> is convertible to
2503<tt class="docutils literal"><span class="pre">random_access_iterator_tag</span></tt> or <tt class="docutils literal"><span class="pre">random_access_traversal_tag</span></tt>,
2504the following must must also be valid:</p>
2505<pre class="literal-block">
2506counting_iterator::difference_type n;
2507i += n;
2508n = i - j;
2509i &lt; j;
2510</pre>
2511</div>
2512<div class="section" id="counting-iterator-models">
2513<h4><a class="toc-backref" href="#id66"><tt class="docutils literal"><span class="pre">counting_iterator</span></tt> models</a></h4>
2514<p>Specializations of <tt class="docutils literal"><span class="pre">counting_iterator</span></tt> model Readable Lvalue
2515Iterator. In addition, they model the concepts corresponding to the
2516iterator tags to which their <tt class="docutils literal"><span class="pre">iterator_category</span></tt> is convertible.
2517Also, if <tt class="docutils literal"><span class="pre">CategoryOrTraversal</span></tt> is not <tt class="docutils literal"><span class="pre">use_default</span></tt> then
2518<tt class="docutils literal"><span class="pre">counting_iterator</span></tt> models the concept corresponding to the iterator
2519tag <tt class="docutils literal"><span class="pre">CategoryOrTraversal</span></tt>.  Otherwise, if
2520<tt class="docutils literal"><span class="pre">numeric_limits&lt;Incrementable&gt;::is_specialized</span></tt>, then
2521<tt class="docutils literal"><span class="pre">counting_iterator</span></tt> models Random Access Traversal Iterator.
2522Otherwise, <tt class="docutils literal"><span class="pre">counting_iterator</span></tt> models the same iterator traversal
2523concepts modeled by <tt class="docutils literal"><span class="pre">Incrementable</span></tt>.</p>
2524<p><tt class="docutils literal"><span class="pre">counting_iterator&lt;X,C1,D1&gt;</span></tt> is interoperable with
2525<tt class="docutils literal"><span class="pre">counting_iterator&lt;Y,C2,D2&gt;</span></tt> if and only if <tt class="docutils literal"><span class="pre">X</span></tt> is
2526interoperable with <tt class="docutils literal"><span class="pre">Y</span></tt>.</p>
2527</div>
2528<div class="section" id="counting-iterator-operations">
2529<h4><a class="toc-backref" href="#id67"><tt class="docutils literal"><span class="pre">counting_iterator</span></tt> operations</a></h4>
2530<p>In addition to the operations required by the concepts modeled by
2531<tt class="docutils literal"><span class="pre">counting_iterator</span></tt>, <tt class="docutils literal"><span class="pre">counting_iterator</span></tt> provides the following
2532operations.</p>
2533<p><tt class="docutils literal"><span class="pre">counting_iterator();</span></tt></p>
2534<table class="docutils field-list" frame="void" rules="none">
2535<col class="field-name" />
2536<col class="field-body" />
2537<tbody valign="top">
2538<tr class="field"><th class="field-name">Requires:</th><td class="field-body"><tt class="docutils literal"><span class="pre">Incrementable</span></tt> is Default Constructible.</td>
2539</tr>
2540<tr class="field"><th class="field-name">Effects:</th><td class="field-body">Default construct the member <tt class="docutils literal"><span class="pre">m_inc</span></tt>.</td>
2541</tr>
2542</tbody>
2543</table>
2544<p><tt class="docutils literal"><span class="pre">counting_iterator(counting_iterator</span> <span class="pre">const&amp;</span> <span class="pre">rhs);</span></tt></p>
2545<table class="docutils field-list" frame="void" rules="none">
2546<col class="field-name" />
2547<col class="field-body" />
2548<tbody valign="top">
2549<tr class="field"><th class="field-name">Effects:</th><td class="field-body">Construct member <tt class="docutils literal"><span class="pre">m_inc</span></tt> from <tt class="docutils literal"><span class="pre">rhs.m_inc</span></tt>.</td>
2550</tr>
2551</tbody>
2552</table>
2553<p><tt class="docutils literal"><span class="pre">explicit</span> <span class="pre">counting_iterator(Incrementable</span> <span class="pre">x);</span></tt></p>
2554<table class="docutils field-list" frame="void" rules="none">
2555<col class="field-name" />
2556<col class="field-body" />
2557<tbody valign="top">
2558<tr class="field"><th class="field-name">Effects:</th><td class="field-body">Construct member <tt class="docutils literal"><span class="pre">m_inc</span></tt> from <tt class="docutils literal"><span class="pre">x</span></tt>.</td>
2559</tr>
2560</tbody>
2561</table>
2562<p><tt class="docutils literal"><span class="pre">reference</span> <span class="pre">operator*()</span> <span class="pre">const;</span></tt></p>
2563<table class="docutils field-list" frame="void" rules="none">
2564<col class="field-name" />
2565<col class="field-body" />
2566<tbody valign="top">
2567<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_inc</span></tt></td>
2568</tr>
2569</tbody>
2570</table>
2571<p><tt class="docutils literal"><span class="pre">counting_iterator&amp;</span> <span class="pre">operator++();</span></tt></p>
2572<table class="docutils field-list" frame="void" rules="none">
2573<col class="field-name" />
2574<col class="field-body" />
2575<tbody valign="top">
2576<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><tt class="docutils literal"><span class="pre">++m_inc</span></tt></td>
2577</tr>
2578<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*this</span></tt></td>
2579</tr>
2580</tbody>
2581</table>
2582<p><tt class="docutils literal"><span class="pre">counting_iterator&amp;</span> <span class="pre">operator--();</span></tt></p>
2583<table class="docutils field-list" frame="void" rules="none">
2584<col class="field-name" />
2585<col class="field-body" />
2586<tbody valign="top">
2587<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><tt class="docutils literal"><span class="pre">--m_inc</span></tt></td>
2588</tr>
2589<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*this</span></tt></td>
2590</tr>
2591</tbody>
2592</table>
2593<p><tt class="docutils literal"><span class="pre">Incrementable</span> <span class="pre">const&amp;</span> <span class="pre">base()</span> <span class="pre">const;</span></tt></p>
2594<table class="docutils field-list" frame="void" rules="none">
2595<col class="field-name" />
2596<col class="field-body" />
2597<tbody valign="top">
2598<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_inc</span></tt></td>
2599</tr>
2600</tbody>
2601</table>
2602</div>
2603</div>
2604<div class="section" id="function-output-iterator">
2605<h3><a class="toc-backref" href="#id68">Function output iterator</a></h3>
2606<!-- Copyright David Abrahams 2006. Distributed under the Boost -->
2607<!-- Software License, Version 1.0. (See accompanying -->
2608<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
2609<p>The function output iterator adaptor makes it easier to create custom
2610output iterators. The adaptor takes a unary function and creates a
2611model of Output Iterator. Each item assigned to the output iterator is
2612passed as an argument to the unary function.  The motivation for this
2613iterator is that creating a conforming output iterator is non-trivial,
2614particularly because the proper implementation usually requires a
2615proxy object.</p>
2616<div class="section" id="class-template-function-output-iterator">
2617<h4><a class="toc-backref" href="#id69">Class template <tt class="docutils literal"><span class="pre">function_output_iterator</span></tt></a></h4>
2618<!-- Copyright David Abrahams 2006. Distributed under the Boost -->
2619<!-- Software License, Version 1.0. (See accompanying -->
2620<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
2621</div>
2622<div class="section" id="header">
2623<h4><a class="toc-backref" href="#id70">Header</a></h4>
2624<pre class="literal-block">
2625#include &lt;boost/function_output_iterator.hpp&gt;
2626</pre>
2627<pre class="literal-block">
2628template &lt;class UnaryFunction&gt;
2629class function_output_iterator {
2630public:
2631  typedef std::output_iterator_tag iterator_category;
2632  typedef void                     value_type;
2633  typedef void                     difference_type;
2634  typedef void                     pointer;
2635  typedef void                     reference;
2636
2637  explicit function_output_iterator();
2638
2639  explicit function_output_iterator(const UnaryFunction&amp; f);
2640
2641  /* see below */ operator*();
2642  function_output_iterator&amp; operator++();
2643  function_output_iterator&amp; operator++(int);
2644private:
2645  UnaryFunction m_f;     // exposition only
2646};
2647</pre>
2648</div>
2649<div class="section" id="function-output-iterator-requirements">
2650<h4><a class="toc-backref" href="#id71"><tt class="docutils literal"><span class="pre">function_output_iterator</span></tt> requirements</a></h4>
2651<p><tt class="docutils literal"><span class="pre">UnaryFunction</span></tt> must be Assignable and Copy Constructible.</p>
2652</div>
2653<div class="section" id="function-output-iterator-models">
2654<h4><a class="toc-backref" href="#id72"><tt class="docutils literal"><span class="pre">function_output_iterator</span></tt> models</a></h4>
2655<p><tt class="docutils literal"><span class="pre">function_output_iterator</span></tt> is a model of the Writable and
2656Incrementable Iterator concepts.</p>
2657</div>
2658<div class="section" id="function-output-iterator-operations">
2659<h4><a class="toc-backref" href="#id73"><tt class="docutils literal"><span class="pre">function_output_iterator</span></tt> operations</a></h4>
2660<p><tt class="docutils literal"><span class="pre">explicit</span> <span class="pre">function_output_iterator(const</span> <span class="pre">UnaryFunction&amp;</span> <span class="pre">f</span> <span class="pre">=</span> <span class="pre">UnaryFunction());</span></tt></p>
2661<table class="docutils field-list" frame="void" rules="none">
2662<col class="field-name" />
2663<col class="field-body" />
2664<tbody valign="top">
2665<tr class="field"><th class="field-name">Effects:</th><td class="field-body">Constructs an instance of <tt class="docutils literal"><span class="pre">function_output_iterator</span></tt>
2666with <tt class="docutils literal"><span class="pre">m_f</span></tt> constructed from <tt class="docutils literal"><span class="pre">f</span></tt>.</td>
2667</tr>
2668</tbody>
2669</table>
2670<p><tt class="docutils literal"><span class="pre">operator*();</span></tt></p>
2671<table class="docutils field-list" frame="void" rules="none">
2672<col class="field-name" />
2673<col class="field-body" />
2674<tbody valign="top">
2675<tr class="field"><th class="field-name">Returns:</th><td class="field-body">An object <tt class="docutils literal"><span class="pre">r</span></tt> of unspecified type such that <tt class="docutils literal"><span class="pre">r</span> <span class="pre">=</span> <span class="pre">t</span></tt>
2676is equivalent to <tt class="docutils literal"><span class="pre">m_f(t)</span></tt> for all <tt class="docutils literal"><span class="pre">t</span></tt>.</td>
2677</tr>
2678</tbody>
2679</table>
2680<p><tt class="docutils literal"><span class="pre">function_output_iterator&amp;</span> <span class="pre">operator++();</span></tt></p>
2681<table class="docutils field-list" frame="void" rules="none">
2682<col class="field-name" />
2683<col class="field-body" />
2684<tbody valign="top">
2685<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*this</span></tt></td>
2686</tr>
2687</tbody>
2688</table>
2689<p><tt class="docutils literal"><span class="pre">function_output_iterator&amp;</span> <span class="pre">operator++(int);</span></tt></p>
2690<table class="docutils field-list" frame="void" rules="none">
2691<col class="field-name" />
2692<col class="field-body" />
2693<tbody valign="top">
2694<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*this</span></tt></td>
2695</tr>
2696</tbody>
2697</table>
2698<!-- LocalWords:  Abrahams Siek Witt istream ostream iter MTL strided interoperate
2699LocalWords:  CRTP metafunctions inlining lvalue JGS incrementable BGL LEDA cv
2700LocalWords:  GraphBase struct ptrdiff UnaryFunction const int typename bool pp
2701LocalWords:  lhs rhs SFINAE markup iff tmp OtherDerived OtherIterator DWA foo
2702LocalWords:  dereferenceable subobject AdaptableUnaryFunction impl pre ifdef'd
2703LocalWords:  OtherIncrementable Coplien -->
2704</div>
2705</div>
2706</div>
2707</div>
2708</div>
2709<div class="footer">
2710<hr class="footer" />
2711<a class="reference external" href="facade-and-adaptor.rst">View document source</a>.
2712Generated 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.
2713
2714</div>
2715</body>
2716</html>
Note: See TracBrowser for help on using the repository browser.