libs/iterator/doc/html/index.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>Chapter&#160;1.&#160;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&#160;1.&#160;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&#160;1.&#160;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 &#169; 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 &lt;ulink url="http://www.boost.org/LICENSE_1_0.txt"&gt;
  40         http://www.boost.org/LICENSE_1_0.txt &lt;/ulink&gt;)
  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">&lt;</span><span class="keyword">bool</span><span class="special">&gt;::</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">&lt;</span><span class="keyword">bool</span><span class="special">&gt;</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">&lt;</span><span class="keyword">bool</span><span class="special">&gt;</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: December 10, 2019 at 00:22:40 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>