1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Chapter 1. Boost.Iterator</title> 5<link rel="stylesheet" href="../../../../doc/src/boostbook.css" type="text/css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="index.html" title="Chapter 1. Boost.Iterator"> 8<link rel="next" href="iterator/concepts.html" title="Iterator Concepts"> 9</head> 10<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 11<table cellpadding="2" width="100%"><tr> 12<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../boost.png"></td> 13<td align="center"><a href="../../../../index.html">Home</a></td> 14<td align="center"><a href="../../../../libs/libraries.htm">Libraries</a></td> 15<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 16<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 17<td align="center"><a href="../../../../more/index.htm">More</a></td> 18</tr></table> 19<hr> 20<div class="spirit-nav"><a accesskey="n" href="iterator/concepts.html"><img src="../../../../doc/src/images/next.png" alt="Next"></a></div> 21<div class="chapter"> 22<div class="titlepage"><div> 23<div><h2 class="title"> 24<a name="iterator"></a>Chapter 1. Boost.Iterator</h2></div> 25<div><div class="author"><h3 class="author"> 26<span class="firstname">David</span> <span class="surname">Abrahams</span> 27</h3></div></div> 28<div><div class="author"><h3 class="author"> 29<span class="firstname">Jeremy</span> <span class="surname">Siek</span> 30</h3></div></div> 31<div><div class="author"><h3 class="author"> 32<span class="firstname">Thomas</span> <span class="surname">Witt</span> 33</h3></div></div> 34<div><p class="copyright">Copyright © 2003, 2005 David Abrahams Jeremy Siek Thomas 35 Witt</p></div> 36<div><div class="legalnotice"> 37<a name="iterator.legal"></a><p> 38 Distributed under the Boost Software License, Version 1.0. (See accompanying 39 file LICENSE_1_0.txt or copy at <ulink url="http://www.boost.org/LICENSE_1_0.txt"> 40 http://www.boost.org/LICENSE_1_0.txt </ulink>) 41 </p> 42</div></div> 43</div></div> 44<div class="toc"> 45<p><b>Table of Contents</b></p> 46<dl class="toc"> 47<dt><span class="section"><a href="index.html#iterator.intro">Introduction</a></span></dt> 48<dt><span class="section"><a href="iterator/concepts.html">Iterator Concepts</a></span></dt> 49<dd><dl> 50<dt><span class="section"><a href="iterator/concepts.html#iterator.concepts.access">Access</a></span></dt> 51<dd><dl> 52<dt><span class="section"><a href="iterator/concepts.html#iterator.concepts.access.readable">Readable Iterator 53 Concept</a></span></dt> 54<dt><span class="section"><a href="iterator/concepts.html#iterator.concepts.access.writable">Writable Iterator 55 Concept</a></span></dt> 56<dt><span class="section"><a href="iterator/concepts.html#iterator.concepts.access.swappable">Swappable Iterator 57 Concept</a></span></dt> 58<dt><span class="section"><a href="iterator/concepts.html#iterator.concepts.access.lvalue">Lvalue Iterator Concept</a></span></dt> 59</dl></dd> 60<dt><span class="section"><a href="iterator/concepts/traversal.html">Traversal</a></span></dt> 61<dd><dl> 62<dt><span class="section"><a href="iterator/concepts/traversal.html#iterator.concepts.traversal.incrementable">Incrementable 63 Iterator Concept</a></span></dt> 64<dt><span class="section"><a href="iterator/concepts/traversal.html#iterator.concepts.traversal.single_pass">Single Pass 65 Iterator Concept</a></span></dt> 66<dt><span class="section"><a href="iterator/concepts/traversal.html#iterator.concepts.traversal.forward">Forward Traversal 67 Concept</a></span></dt> 68<dt><span class="section"><a href="iterator/concepts/traversal.html#iterator.concepts.traversal.bidirectional">Bidirectional 69 Traversal Concept</a></span></dt> 70<dt><span class="section"><a href="iterator/concepts/traversal.html#iterator.concepts.traversal.random_access">Random Access 71 Traversal Concept</a></span></dt> 72</dl></dd> 73</dl></dd> 74<dt><span class="section"><a href="iterator/generic.html">Generic Iterators</a></span></dt> 75<dd><dl> 76<dt><span class="section"><a href="iterator/generic.html#iterator.generic.facade">Iterator Facade</a></span></dt> 77<dd><dl> 78<dt><span class="section"><a href="iterator/generic.html#iterator.generic.facade.facade_reference">Reference</a></span></dt> 79<dt><span class="section"><a href="iterator/generic.html#iterator.generic.facade.facade_tutorial">Tutorial</a></span></dt> 80</dl></dd> 81<dt><span class="section"><a href="iterator/generic/adaptor.html">Iterator Adaptor</a></span></dt> 82<dd><dl> 83<dt><span class="section"><a href="iterator/generic/adaptor.html#iterator.generic.adaptor.adaptor_reference">Reference</a></span></dt> 84<dt><span class="section"><a href="iterator/generic/adaptor.html#iterator.generic.adaptor.adaptor_tutorial">Tutorial</a></span></dt> 85</dl></dd> 86</dl></dd> 87<dt><span class="section"><a href="iterator/specialized.html">Specialized Adaptors</a></span></dt> 88<dd><dl> 89<dt><span class="section"><a href="iterator/specialized.html#iterator.specialized.counting">Counting Iterator</a></span></dt> 90<dt><span class="section"><a href="iterator/specialized/filter.html">Filter Iterator</a></span></dt> 91<dt><span class="section"><a href="iterator/specialized/function_output.html">Function Output 92 Iterator</a></span></dt> 93<dt><span class="section"><a href="iterator/specialized/indirect.html">Indirect Iterator</a></span></dt> 94<dt><span class="section"><a href="iterator/specialized/permutation.html">Permutation Iterator</a></span></dt> 95<dt><span class="section"><a href="iterator/specialized/reverse.html">Reverse Iterator</a></span></dt> 96<dt><span class="section"><a href="iterator/specialized/shared_container.html">Shared Container 97 Iterator</a></span></dt> 98<dd><dl> 99<dt><span class="section"><a href="iterator/specialized/shared_container.html#iterator.specialized.shared_container.shared_container_type">The 100 Shared Container Iterator Type</a></span></dt> 101<dt><span class="section"><a href="iterator/specialized/shared_container.html#iterator.specialized.shared_container.shared_container_object_generator">The 102 Shared Container Iterator Object Generator</a></span></dt> 103<dt><span class="section"><a href="iterator/specialized/shared_container.html#iterator.specialized.shared_container.shared_container_generator">The 104 Shared Container Iterator Range Generator</a></span></dt> 105</dl></dd> 106<dt><span class="section"><a href="iterator/specialized/transform.html">Transform Iterator</a></span></dt> 107<dt><span class="section"><a href="iterator/specialized/zip.html">Zip Iterator</a></span></dt> 108<dd><dl> 109<dt><span class="section"><a href="iterator/specialized/zip.html#iterator.specialized.zip.zip_example">Example</a></span></dt> 110<dt><span class="section"><a href="iterator/specialized/zip.html#iterator.specialized.zip.zip_reference">Reference</a></span></dt> 111</dl></dd> 112</dl></dd> 113<dt><span class="section"><a href="iterator/utilities.html">Utilities</a></span></dt> 114<dd><dl> 115<dt><span class="section"><a href="iterator/utilities.html#iterator.utilities.archetypes">Iterator Archetypes</a></span></dt> 116<dt><span class="section"><a href="iterator/utilities/concept_checking.html">Concept Checking</a></span></dt> 117<dt><span class="section"><a href="iterator/utilities/iterator_traits.html">Iterator Traits</a></span></dt> 118<dt><span class="section"><a href="iterator/utilities/traits.html">Type Traits</a></span></dt> 119</dl></dd> 120<dt><span class="section"><a href="iterator/algorithms.html">Algorithms</a></span></dt> 121<dd><dl> 122<dt><span class="section"><a href="iterator/algorithms.html#iterator.algorithms.advance">Function template <code class="computeroutput"><span class="identifier">advance</span><span class="special">()</span></code></a></span></dt> 123<dt><span class="section"><a href="iterator/algorithms/distance.html">Function template <code class="computeroutput"><span class="identifier">distance</span><span class="special">()</span></code></a></span></dt> 124<dt><span class="section"><a href="iterator/algorithms/next_prior.html">Function templates <code class="computeroutput"><span class="identifier">next</span><span class="special">()</span></code> and 125 <code class="computeroutput"><span class="identifier">prior</span><span class="special">()</span></code></a></span></dt> 126</dl></dd> 127<dt><span class="section"><a href="iterator/upgrading.html">Upgrading from the old Boost Iterator 128 Adaptor Library</a></span></dt> 129<dt><span class="section"><a href="iterator/history.html">History</a></span></dt> 130</dl> 131</div> 132<div class="section"> 133<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 134<a name="iterator.intro"></a><a class="link" href="index.html#iterator.intro" title="Introduction">Introduction</a> 135</h2></div></div></div> 136<p> 137 The Boost Iterator Library contains two parts. The first is a system of <a href="http://www.boost.org/more/generic_programming.html#concept" target="_top">concepts</a> 138 which extend the C++ standard iterator requirements. The second is a framework 139 of components for building iterators based on these extended concepts and includes 140 several useful iterator adaptors. The extended iterator concepts have been 141 carefully designed so that old-style iterators can fit in the new concepts 142 and so that new-style iterators will be compatible with old-style algorithms, 143 though algorithms may need to be updated if they want to take full advantage 144 of the new-style iterator capabilities. Several components of this library 145 have been accepted into the C++ standard technical report. The components of 146 the Boost Iterator Library replace the older Boost Iterator Adaptor Library. 147 </p> 148<h3> 149<a name="iterator.intro.h0"></a> 150 <span class="phrase"><a name="iterator.intro.new_style_iterators"></a></span><a class="link" href="index.html#iterator.intro.new_style_iterators">New-Style 151 Iterators</a> 152 </h3> 153<p> 154 The iterator categories defined in C++98 are extremely limiting because they 155 bind together two orthogonal concepts: traversal and element access. For example, 156 because a random access iterator is required to return a reference (and not 157 a proxy) when dereferenced, it is impossible to capture the capabilities of 158 <code class="computeroutput"><span class="identifier">vector</span><span class="special"><</span><span class="keyword">bool</span><span class="special">>::</span><span class="identifier">iterator</span></code> 159 using the C++98 categories. This is the infamous "<code class="computeroutput"><span class="identifier">vector</span><span class="special"><</span><span class="keyword">bool</span><span class="special">></span></code> 160 is not a container, and its iterators aren't random access iterators", 161 debacle about which Herb Sutter wrote two papers for the standards comittee 162 (<a href="http://www.gotw.ca/publications/N1185.pdf" target="_top">N1185</a> and 163 <a href="http://www.gotw.ca/publications/N1211.pdf" target="_top">N1211</a>), and 164 a <a href="http://www.gotw.ca/gotw/050.htm" target="_top">Guru of the Week</a>. New-style 165 iterators go well beyond patching up <code class="computeroutput"><span class="identifier">vector</span><span class="special"><</span><span class="keyword">bool</span><span class="special">></span></code>, 166 though: there are lots of other iterators already in use which can't be adequately 167 represented by the existing concepts. For details about the new iterator concepts, 168 see our <a href="../new-iter-concepts.html" target="_top">Standard Proposal for New-Style 169 Iterators</a>. 170 </p> 171<h3> 172<a name="iterator.intro.h1"></a> 173 <span class="phrase"><a name="iterator.intro.iterator_facade_and_adaptor"></a></span><a class="link" href="index.html#iterator.intro.iterator_facade_and_adaptor">Iterator 174 Facade and Adaptor</a> 175 </h3> 176<p> 177 Writing standard-conforming iterators is tricky, but the need comes up often. 178 In order to ease the implementation of new iterators, the Boost.Iterator library 179 provides the <a href="../iterator_facade.html" target="_top">facade</a> class template, 180 which implements many useful defaults and compile-time checks designed to help 181 the iterator author ensure that his iterator is correct. 182 </p> 183<p> 184 It is also common to define a new iterator that is similar to some underlying 185 iterator or iterator-like type, but that modifies some aspect of the underlying 186 type's behavior. For that purpose, the library supplies the <a href="../iterator_adaptor.html" target="_top">adaptor</a> 187 class template, which is specially designed to take advantage of as much of 188 the underlying type's behavior as possible. 189 </p> 190<p> 191 Both <a href="../iterator_facade.html" target="_top">facade</a> and <a href="../iterator_adaptor.html" target="_top">adaptor</a> 192 as well as many of the <a class="link" href="iterator/specialized.html" title="Specialized Adaptors">specialized adaptors</a> 193 mentioned below have been proposed for standardization (<a href="../facade-and-adaptor.html" target="_top">Standard 194 Proposal For Iterator Facade and Adaptor</a>). 195 </p> 196<h3> 197<a name="iterator.intro.h2"></a> 198 <span class="phrase"><a name="iterator.intro.specialized_adaptors"></a></span><a class="link" href="index.html#iterator.intro.specialized_adaptors">Specialized 199 Adaptors</a> 200 </h3> 201<p> 202 The iterator library supplies a useful suite of standard-conforming iterator 203 templates based on the Boost <a class="link" href="index.html#iterator.intro.iterator_facade_and_adaptor">iterator 204 facade and adaptor</a> templates. 205 </p> 206<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 207<li class="listitem"> 208 <a class="link" href="iterator/specialized.html#iterator.specialized.counting" title="Counting Iterator"><code class="computeroutput"><span class="identifier">counting_iterator</span></code></a>: 209 an iterator over a sequence of consecutive values. Implements a "lazy 210 sequence" 211 </li> 212<li class="listitem"> 213 <a class="link" href="iterator/specialized/filter.html" title="Filter Iterator"><code class="computeroutput"><span class="identifier">filter_iterator</span></code></a>: 214 an iterator over the subset of elements of some sequence which satisfy 215 a given predicate 216 </li> 217<li class="listitem"> 218 <a href="../function_input_iterator.html" target="_top"><code class="computeroutput"><span class="identifier">function_input_iterator</span></code></a>: 219 an input iterator wrapping a generator (nullary function object); each 220 time the iterator is dereferenced, the function object is called to get 221 the value to return. 222 </li> 223<li class="listitem"> 224 <a class="link" href="iterator/specialized/function_output.html" title="Function Output Iterator"><code class="computeroutput"><span class="identifier">function_output_iterator</span></code></a>: 225 an output iterator wrapping a unary function object; each time an element 226 is written into the dereferenced iterator, it is passed as a parameter 227 to the function object. 228 </li> 229<li class="listitem"> 230 <a href="../generator_iterator.htm" target="_top"><code class="computeroutput"><span class="identifier">generator_iterator</span></code></a>: 231 an input iterator wrapping a generator (nullary function object); each 232 time the iterator is dereferenced, the function object is called to get 233 the value to return. An outdated analogue of <a href="../function_input_iterator.html" target="_top"><code class="computeroutput"><span class="identifier">function_input_iterator</span></code></a>. 234 </li> 235<li class="listitem"> 236 <a class="link" href="iterator/specialized/indirect.html" title="Indirect Iterator"><code class="computeroutput"><span class="identifier">indirect_iterator</span></code></a>: 237 an iterator over the objects <span class="bold"><strong>pointed-to</strong></span> 238 by the elements of some sequence. 239 </li> 240<li class="listitem"> 241 <a class="link" href="iterator/specialized/permutation.html" title="Permutation Iterator"><code class="computeroutput"><span class="identifier">permutation_iterator</span></code></a>: 242 an iterator over the elements of some random-access sequence, rearranged 243 according to some sequence of integer indices. 244 </li> 245<li class="listitem"> 246 <a class="link" href="iterator/specialized/reverse.html" title="Reverse Iterator"><code class="computeroutput"><span class="identifier">reverse_iterator</span></code></a>: 247 an iterator which traverses the elements of some bidirectional sequence 248 in reverse. Corrects many of the shortcomings of C++98's <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">reverse_iterator</span></code>. 249 </li> 250<li class="listitem"> 251 <a class="link" href="iterator/specialized/shared_container.html" title="Shared Container Iterator"><code class="computeroutput"><span class="identifier">shared_container_iterator</span></code></a>: 252 an iterator over elements of a container whose lifetime is maintained by 253 a <a href="../../smart_ptr/shared_ptr.htm" target="_top"><code class="computeroutput"><span class="identifier">shared_ptr</span></code></a> 254 stored in the iterator. 255 </li> 256<li class="listitem"> 257 <a class="link" href="iterator/specialized/transform.html" title="Transform Iterator"><code class="computeroutput"><span class="identifier">transform_iterator</span></code></a>: 258 an iterator over elements which are the result of applying some functional 259 transformation to the elements of an underlying sequence. This component 260 also replaces the old <code class="computeroutput"><span class="identifier">projection_iterator_adaptor</span></code>. 261 </li> 262<li class="listitem"> 263 <a class="link" href="iterator/specialized/zip.html" title="Zip Iterator"><code class="computeroutput"><span class="identifier">zip_iterator</span></code></a>: 264 an iterator over tuples of the elements at corresponding positions of heterogeneous 265 underlying iterators. 266 </li> 267</ul></div> 268<h3> 269<a name="iterator.intro.h3"></a> 270 <span class="phrase"><a name="iterator.intro.iterator_utilities"></a></span><a class="link" href="index.html#iterator.intro.iterator_utilities">Iterator 271 Utilities</a> 272 </h3> 273<h4> 274<a name="iterator.intro.h4"></a> 275 <span class="phrase"><a name="iterator.intro.traits"></a></span><a class="link" href="index.html#iterator.intro.traits">Traits</a> 276 </h4> 277<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 278<li class="listitem"> 279 <a class="link" href="iterator/utilities/traits.html" title="Type Traits"><code class="computeroutput"><span class="identifier">pointee</span><span class="special">.</span><span class="identifier">hpp</span></code></a>: 280 Provides the capability to deduce the referent types of pointers, smart 281 pointers and iterators in generic code. Used in <a class="link" href="iterator/specialized/indirect.html" title="Indirect Iterator"><code class="computeroutput"><span class="identifier">indirect_iterator</span></code></a>. 282 </li> 283<li class="listitem"> 284 <a class="link" href="iterator/utilities/iterator_traits.html" title="Iterator Traits"><code class="computeroutput"><span class="identifier">iterator_traits</span><span class="special">.</span><span class="identifier">hpp</span></code></a>: 285 Provides <a href="../../mpl/doc/index.html" target="_top"><span class="bold"><strong>MPL</strong></span></a> 286 compatible metafunctions which retrieve an iterator's traits. Also corrects 287 for the deficiencies of broken implementations of <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">iterator_traits</span></code>. 288 </li> 289</ul></div> 290<h4> 291<a name="iterator.intro.h5"></a> 292 <span class="phrase"><a name="iterator.intro.testing_and_concept_checking"></a></span><a class="link" href="index.html#iterator.intro.testing_and_concept_checking">Testing 293 and Concept Checking</a> 294 </h4> 295<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 296<li class="listitem"> 297 <a class="link" href="iterator/concepts.html" title="Iterator Concepts"><code class="computeroutput"><span class="identifier">iterator_concepts</span><span class="special">.</span><span class="identifier">hpp</span></code></a>: 298 Concept checking classes for the new iterator concepts. 299 </li> 300<li class="listitem"> 301 <a class="link" href="iterator/utilities.html#iterator.utilities.archetypes" title="Iterator Archetypes"><code class="computeroutput"><span class="identifier">iterator_archetypes</span><span class="special">.</span><span class="identifier">hpp</span></code></a>: 302 Concept archetype classes for the new iterators concepts. 303 </li> 304</ul></div> 305<h3> 306<a name="iterator.intro.h6"></a> 307 <span class="phrase"><a name="iterator.intro.iterator_algorithms"></a></span><a class="link" href="index.html#iterator.intro.iterator_algorithms">Iterator 308 Algorithms</a> 309 </h3> 310<p> 311 The library provides a number of generic algorithms for use with iterators. 312 These algorithms take advantage of the new concepts defined by the library 313 to provide better performance and functionality. 314 </p> 315<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 316<li class="listitem"> 317 <a class="link" href="iterator/algorithms.html#iterator.algorithms.advance" title="Function template advance()"><code class="computeroutput"><span class="identifier">advance</span><span class="special">.</span><span class="identifier">hpp</span></code></a>: 318 Provides <code class="computeroutput"><span class="identifier">advance</span><span class="special">()</span></code> 319 function for advancing an iterator a given number of positions forward 320 or backward. 321 </li> 322<li class="listitem"> 323 <a class="link" href="iterator/algorithms/distance.html" title="Function template distance()"><code class="computeroutput"><span class="identifier">distance</span><span class="special">.</span><span class="identifier">hpp</span></code></a>: 324 Provides <code class="computeroutput"><span class="identifier">distance</span><span class="special">()</span></code> 325 function for computing distance between two iterators. 326 </li> 327<li class="listitem"> 328 <a class="link" href="iterator/algorithms/next_prior.html" title="Function templates next() and prior()"><code class="computeroutput"><span class="identifier">next_prior</span><span class="special">.</span><span class="identifier">hpp</span></code></a>: 329 Provides <code class="computeroutput"><span class="identifier">next</span><span class="special">()</span></code> 330 and <code class="computeroutput"><span class="identifier">prior</span><span class="special">()</span></code> 331 functions for obtaining next and prior iterators to a given iterator. The 332 functions are also compatible with non-iterator types. 333 </li> 334</ul></div> 335</div> 336</div> 337<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 338<td align="left"><p><small>Last revised: August 11, 2020 at 15:00:12 GMT</small></p></td> 339<td align="right"><div class="copyright-footer"></div></td> 340</tr></table> 341<hr> 342<div class="spirit-nav"><a accesskey="n" href="iterator/concepts.html"><img src="../../../../doc/src/images/next.png" alt="Next"></a></div> 343</body> 344</html> 345
