Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/iterator/doc/facade-and-adaptor.html @ 12

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

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