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