123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344 |
- <html>
- <head>
- <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
- <title>Chapter 1. Boost.Iterator</title>
- <link rel="stylesheet" href="../../../../doc/src/boostbook.css" type="text/css">
- <meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
- <link rel="home" href="index.html" title="Chapter 1. Boost.Iterator">
- <link rel="next" href="iterator/concepts.html" title="Iterator Concepts">
- </head>
- <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
- <table cellpadding="2" width="100%"><tr>
- <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../boost.png"></td>
- <td align="center"><a href="../../../../index.html">Home</a></td>
- <td align="center"><a href="../../../../libs/libraries.htm">Libraries</a></td>
- <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
- <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
- <td align="center"><a href="../../../../more/index.htm">More</a></td>
- </tr></table>
- <hr>
- <div class="spirit-nav"><a accesskey="n" href="iterator/concepts.html"><img src="../../../../doc/src/images/next.png" alt="Next"></a></div>
- <div class="chapter">
- <div class="titlepage"><div>
- <div><h2 class="title">
- <a name="iterator"></a>Chapter 1. Boost.Iterator</h2></div>
- <div><div class="author"><h3 class="author">
- <span class="firstname">David</span> <span class="surname">Abrahams</span>
- </h3></div></div>
- <div><div class="author"><h3 class="author">
- <span class="firstname">Jeremy</span> <span class="surname">Siek</span>
- </h3></div></div>
- <div><div class="author"><h3 class="author">
- <span class="firstname">Thomas</span> <span class="surname">Witt</span>
- </h3></div></div>
- <div><p class="copyright">Copyright © 2003, 2005 David Abrahams Jeremy Siek Thomas
- Witt</p></div>
- <div><div class="legalnotice">
- <a name="iterator.legal"></a><p>
- Distributed under the Boost Software License, Version 1.0. (See accompanying
- file LICENSE_1_0.txt or copy at <ulink url="http://www.boost.org/LICENSE_1_0.txt">
- http://www.boost.org/LICENSE_1_0.txt </ulink>)
- </p>
- </div></div>
- </div></div>
- <div class="toc">
- <p><b>Table of Contents</b></p>
- <dl class="toc">
- <dt><span class="section"><a href="index.html#iterator.intro">Introduction</a></span></dt>
- <dt><span class="section"><a href="iterator/concepts.html">Iterator Concepts</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="iterator/concepts.html#iterator.concepts.access">Access</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="iterator/concepts.html#iterator.concepts.access.readable">Readable Iterator
- Concept</a></span></dt>
- <dt><span class="section"><a href="iterator/concepts.html#iterator.concepts.access.writable">Writable Iterator
- Concept</a></span></dt>
- <dt><span class="section"><a href="iterator/concepts.html#iterator.concepts.access.swappable">Swappable Iterator
- Concept</a></span></dt>
- <dt><span class="section"><a href="iterator/concepts.html#iterator.concepts.access.lvalue">Lvalue Iterator Concept</a></span></dt>
- </dl></dd>
- <dt><span class="section"><a href="iterator/concepts/traversal.html">Traversal</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="iterator/concepts/traversal.html#iterator.concepts.traversal.incrementable">Incrementable
- Iterator Concept</a></span></dt>
- <dt><span class="section"><a href="iterator/concepts/traversal.html#iterator.concepts.traversal.single_pass">Single Pass
- Iterator Concept</a></span></dt>
- <dt><span class="section"><a href="iterator/concepts/traversal.html#iterator.concepts.traversal.forward">Forward Traversal
- Concept</a></span></dt>
- <dt><span class="section"><a href="iterator/concepts/traversal.html#iterator.concepts.traversal.bidirectional">Bidirectional
- Traversal Concept</a></span></dt>
- <dt><span class="section"><a href="iterator/concepts/traversal.html#iterator.concepts.traversal.random_access">Random Access
- Traversal Concept</a></span></dt>
- </dl></dd>
- </dl></dd>
- <dt><span class="section"><a href="iterator/generic.html">Generic Iterators</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="iterator/generic.html#iterator.generic.facade">Iterator Facade</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="iterator/generic.html#iterator.generic.facade.facade_reference">Reference</a></span></dt>
- <dt><span class="section"><a href="iterator/generic.html#iterator.generic.facade.facade_tutorial">Tutorial</a></span></dt>
- </dl></dd>
- <dt><span class="section"><a href="iterator/generic/adaptor.html">Iterator Adaptor</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="iterator/generic/adaptor.html#iterator.generic.adaptor.adaptor_reference">Reference</a></span></dt>
- <dt><span class="section"><a href="iterator/generic/adaptor.html#iterator.generic.adaptor.adaptor_tutorial">Tutorial</a></span></dt>
- </dl></dd>
- </dl></dd>
- <dt><span class="section"><a href="iterator/specialized.html">Specialized Adaptors</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="iterator/specialized.html#iterator.specialized.counting">Counting Iterator</a></span></dt>
- <dt><span class="section"><a href="iterator/specialized/filter.html">Filter Iterator</a></span></dt>
- <dt><span class="section"><a href="iterator/specialized/function_output.html">Function Output
- Iterator</a></span></dt>
- <dt><span class="section"><a href="iterator/specialized/indirect.html">Indirect Iterator</a></span></dt>
- <dt><span class="section"><a href="iterator/specialized/permutation.html">Permutation Iterator</a></span></dt>
- <dt><span class="section"><a href="iterator/specialized/reverse.html">Reverse Iterator</a></span></dt>
- <dt><span class="section"><a href="iterator/specialized/shared_container.html">Shared Container
- Iterator</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="iterator/specialized/shared_container.html#iterator.specialized.shared_container.shared_container_type">The
- Shared Container Iterator Type</a></span></dt>
- <dt><span class="section"><a href="iterator/specialized/shared_container.html#iterator.specialized.shared_container.shared_container_object_generator">The
- Shared Container Iterator Object Generator</a></span></dt>
- <dt><span class="section"><a href="iterator/specialized/shared_container.html#iterator.specialized.shared_container.shared_container_generator">The
- Shared Container Iterator Range Generator</a></span></dt>
- </dl></dd>
- <dt><span class="section"><a href="iterator/specialized/transform.html">Transform Iterator</a></span></dt>
- <dt><span class="section"><a href="iterator/specialized/zip.html">Zip Iterator</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="iterator/specialized/zip.html#iterator.specialized.zip.zip_example">Example</a></span></dt>
- <dt><span class="section"><a href="iterator/specialized/zip.html#iterator.specialized.zip.zip_reference">Reference</a></span></dt>
- </dl></dd>
- </dl></dd>
- <dt><span class="section"><a href="iterator/utilities.html">Utilities</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="iterator/utilities.html#iterator.utilities.archetypes">Iterator Archetypes</a></span></dt>
- <dt><span class="section"><a href="iterator/utilities/concept_checking.html">Concept Checking</a></span></dt>
- <dt><span class="section"><a href="iterator/utilities/iterator_traits.html">Iterator Traits</a></span></dt>
- <dt><span class="section"><a href="iterator/utilities/traits.html">Type Traits</a></span></dt>
- </dl></dd>
- <dt><span class="section"><a href="iterator/algorithms.html">Algorithms</a></span></dt>
- <dd><dl>
- <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>
- <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>
- <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
- <code class="computeroutput"><span class="identifier">prior</span><span class="special">()</span></code></a></span></dt>
- </dl></dd>
- <dt><span class="section"><a href="iterator/upgrading.html">Upgrading from the old Boost Iterator
- Adaptor Library</a></span></dt>
- <dt><span class="section"><a href="iterator/history.html">History</a></span></dt>
- </dl>
- </div>
- <div class="section">
- <div class="titlepage"><div><div><h2 class="title" style="clear: both">
- <a name="iterator.intro"></a><a class="link" href="index.html#iterator.intro" title="Introduction">Introduction</a>
- </h2></div></div></div>
- <p>
- 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>
- which extend the C++ standard iterator requirements. The second is a framework
- of components for building iterators based on these extended concepts and includes
- several useful iterator adaptors. The extended iterator concepts have been
- carefully designed so that old-style iterators can fit in the new concepts
- and so that new-style iterators will be compatible with old-style algorithms,
- though algorithms may need to be updated if they want to take full advantage
- of the new-style iterator capabilities. Several components of this library
- have been accepted into the C++ standard technical report. The components of
- the Boost Iterator Library replace the older Boost Iterator Adaptor Library.
- </p>
- <h3>
- <a name="iterator.intro.h0"></a>
- <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
- Iterators</a>
- </h3>
- <p>
- The iterator categories defined in C++98 are extremely limiting because they
- bind together two orthogonal concepts: traversal and element access. For example,
- because a random access iterator is required to return a reference (and not
- a proxy) when dereferenced, it is impossible to capture the capabilities of
- <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>
- 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>
- is not a container, and its iterators aren't random access iterators",
- debacle about which Herb Sutter wrote two papers for the standards comittee
- (<a href="http://www.gotw.ca/publications/N1185.pdf" target="_top">N1185</a> and
- <a href="http://www.gotw.ca/publications/N1211.pdf" target="_top">N1211</a>), and
- a <a href="http://www.gotw.ca/gotw/050.htm" target="_top">Guru of the Week</a>. New-style
- 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>,
- though: there are lots of other iterators already in use which can't be adequately
- represented by the existing concepts. For details about the new iterator concepts,
- see our <a href="../new-iter-concepts.html" target="_top">Standard Proposal for New-Style
- Iterators</a>.
- </p>
- <h3>
- <a name="iterator.intro.h1"></a>
- <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
- Facade and Adaptor</a>
- </h3>
- <p>
- Writing standard-conforming iterators is tricky, but the need comes up often.
- In order to ease the implementation of new iterators, the Boost.Iterator library
- provides the <a href="../iterator_facade.html" target="_top">facade</a> class template,
- which implements many useful defaults and compile-time checks designed to help
- the iterator author ensure that his iterator is correct.
- </p>
- <p>
- It is also common to define a new iterator that is similar to some underlying
- iterator or iterator-like type, but that modifies some aspect of the underlying
- type's behavior. For that purpose, the library supplies the <a href="../iterator_adaptor.html" target="_top">adaptor</a>
- class template, which is specially designed to take advantage of as much of
- the underlying type's behavior as possible.
- </p>
- <p>
- Both <a href="../iterator_facade.html" target="_top">facade</a> and <a href="../iterator_adaptor.html" target="_top">adaptor</a>
- as well as many of the <a class="link" href="iterator/specialized.html" title="Specialized Adaptors">specialized adaptors</a>
- mentioned below have been proposed for standardization (<a href="../facade-and-adaptor.html" target="_top">Standard
- Proposal For Iterator Facade and Adaptor</a>).
- </p>
- <h3>
- <a name="iterator.intro.h2"></a>
- <span class="phrase"><a name="iterator.intro.specialized_adaptors"></a></span><a class="link" href="index.html#iterator.intro.specialized_adaptors">Specialized
- Adaptors</a>
- </h3>
- <p>
- The iterator library supplies a useful suite of standard-conforming iterator
- templates based on the Boost <a class="link" href="index.html#iterator.intro.iterator_facade_and_adaptor">iterator
- facade and adaptor</a> templates.
- </p>
- <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
- <li class="listitem">
- <a class="link" href="iterator/specialized.html#iterator.specialized.counting" title="Counting Iterator"><code class="computeroutput"><span class="identifier">counting_iterator</span></code></a>:
- an iterator over a sequence of consecutive values. Implements a "lazy
- sequence"
- </li>
- <li class="listitem">
- <a class="link" href="iterator/specialized/filter.html" title="Filter Iterator"><code class="computeroutput"><span class="identifier">filter_iterator</span></code></a>:
- an iterator over the subset of elements of some sequence which satisfy
- a given predicate
- </li>
- <li class="listitem">
- <a href="../function_input_iterator.html" target="_top"><code class="computeroutput"><span class="identifier">function_input_iterator</span></code></a>:
- an input iterator wrapping a generator (nullary function object); each
- time the iterator is dereferenced, the function object is called to get
- the value to return.
- </li>
- <li class="listitem">
- <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>:
- an output iterator wrapping a unary function object; each time an element
- is written into the dereferenced iterator, it is passed as a parameter
- to the function object.
- </li>
- <li class="listitem">
- <a href="../generator_iterator.htm" target="_top"><code class="computeroutput"><span class="identifier">generator_iterator</span></code></a>:
- an input iterator wrapping a generator (nullary function object); each
- time the iterator is dereferenced, the function object is called to get
- 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>.
- </li>
- <li class="listitem">
- <a class="link" href="iterator/specialized/indirect.html" title="Indirect Iterator"><code class="computeroutput"><span class="identifier">indirect_iterator</span></code></a>:
- an iterator over the objects <span class="bold"><strong>pointed-to</strong></span>
- by the elements of some sequence.
- </li>
- <li class="listitem">
- <a class="link" href="iterator/specialized/permutation.html" title="Permutation Iterator"><code class="computeroutput"><span class="identifier">permutation_iterator</span></code></a>:
- an iterator over the elements of some random-access sequence, rearranged
- according to some sequence of integer indices.
- </li>
- <li class="listitem">
- <a class="link" href="iterator/specialized/reverse.html" title="Reverse Iterator"><code class="computeroutput"><span class="identifier">reverse_iterator</span></code></a>:
- an iterator which traverses the elements of some bidirectional sequence
- 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>.
- </li>
- <li class="listitem">
- <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>:
- an iterator over elements of a container whose lifetime is maintained by
- a <a href="../../smart_ptr/shared_ptr.htm" target="_top"><code class="computeroutput"><span class="identifier">shared_ptr</span></code></a>
- stored in the iterator.
- </li>
- <li class="listitem">
- <a class="link" href="iterator/specialized/transform.html" title="Transform Iterator"><code class="computeroutput"><span class="identifier">transform_iterator</span></code></a>:
- an iterator over elements which are the result of applying some functional
- transformation to the elements of an underlying sequence. This component
- also replaces the old <code class="computeroutput"><span class="identifier">projection_iterator_adaptor</span></code>.
- </li>
- <li class="listitem">
- <a class="link" href="iterator/specialized/zip.html" title="Zip Iterator"><code class="computeroutput"><span class="identifier">zip_iterator</span></code></a>:
- an iterator over tuples of the elements at corresponding positions of heterogeneous
- underlying iterators.
- </li>
- </ul></div>
- <h3>
- <a name="iterator.intro.h3"></a>
- <span class="phrase"><a name="iterator.intro.iterator_utilities"></a></span><a class="link" href="index.html#iterator.intro.iterator_utilities">Iterator
- Utilities</a>
- </h3>
- <h4>
- <a name="iterator.intro.h4"></a>
- <span class="phrase"><a name="iterator.intro.traits"></a></span><a class="link" href="index.html#iterator.intro.traits">Traits</a>
- </h4>
- <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
- <li class="listitem">
- <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>:
- Provides the capability to deduce the referent types of pointers, smart
- 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>.
- </li>
- <li class="listitem">
- <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>:
- Provides <a href="../../mpl/doc/index.html" target="_top"><span class="bold"><strong>MPL</strong></span></a>
- compatible metafunctions which retrieve an iterator's traits. Also corrects
- 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>.
- </li>
- </ul></div>
- <h4>
- <a name="iterator.intro.h5"></a>
- <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
- and Concept Checking</a>
- </h4>
- <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
- <li class="listitem">
- <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>:
- Concept checking classes for the new iterator concepts.
- </li>
- <li class="listitem">
- <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>:
- Concept archetype classes for the new iterators concepts.
- </li>
- </ul></div>
- <h3>
- <a name="iterator.intro.h6"></a>
- <span class="phrase"><a name="iterator.intro.iterator_algorithms"></a></span><a class="link" href="index.html#iterator.intro.iterator_algorithms">Iterator
- Algorithms</a>
- </h3>
- <p>
- The library provides a number of generic algorithms for use with iterators.
- These algorithms take advantage of the new concepts defined by the library
- to provide better performance and functionality.
- </p>
- <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
- <li class="listitem">
- <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>:
- Provides <code class="computeroutput"><span class="identifier">advance</span><span class="special">()</span></code>
- function for advancing an iterator a given number of positions forward
- or backward.
- </li>
- <li class="listitem">
- <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>:
- Provides <code class="computeroutput"><span class="identifier">distance</span><span class="special">()</span></code>
- function for computing distance between two iterators.
- </li>
- <li class="listitem">
- <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>:
- Provides <code class="computeroutput"><span class="identifier">next</span><span class="special">()</span></code>
- and <code class="computeroutput"><span class="identifier">prior</span><span class="special">()</span></code>
- functions for obtaining next and prior iterators to a given iterator. The
- functions are also compatible with non-iterator types.
- </li>
- </ul></div>
- </div>
- </div>
- <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
- <td align="left"><p><small>Last revised: December 10, 2019 at 00:22:40 GMT</small></p></td>
- <td align="right"><div class="copyright-footer"></div></td>
- </tr></table>
- <hr>
- <div class="spirit-nav"><a accesskey="n" href="iterator/concepts.html"><img src="../../../../doc/src/images/next.png" alt="Next"></a></div>
- </body>
- </html>
|