[ceph.git] / ceph / src / boost / libs / iterator / doc / index.html

<?xml version="1.0" encoding="utf-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" />
<title>The Boost.Iterator Library Boost</title>
<link rel="stylesheet" href="../../../rst.css" type="text/css" />
</head>
<body>
<div class="document" id="the-boost-iterator-library-logo">
<h1 class="title">The Boost.Iterator Library <a class="reference external" href="../../../index.htm"><img alt="Boost" src="../../../boost.png" /></a></h1>

<!-- Distributed under the Boost -->
<!-- Software License, Version 1.0. (See accompanying -->
<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
<hr class="docutils" />
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field"><th class="field-name">Authors:</th><td class="field-body">David Abrahams, Jeremy Siek, Thomas Witt</td>
</tr>
<tr class="field"><th class="field-name">Contact:</th><td class="field-body"><a class="reference external" href="mailto:dave&#64;boost-consulting.com">dave&#64;boost-consulting.com</a>, <a class="reference external" href="mailto:jsiek&#64;osl.iu.edu">jsiek&#64;osl.iu.edu</a>, <a class="reference external" href="mailto:witt&#64;styleadvisor.com">witt&#64;styleadvisor.com</a></td>
</tr>
<tr class="field"><th class="field-name">organizations:</th><td class="field-body"><a class="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
Lab</a>, <a class="reference external" href="http://www.styleadvisor.com">Zephyr Associates, Inc.</a></td>
</tr>
<tr class="field"><th class="field-name">date:</th><td class="field-body">$Date$</td>
</tr>
<tr class="field"><th class="field-name">copyright:</th><td class="field-body">Copyright David Abrahams, Jeremy Siek, Thomas Witt 2003.</td>
</tr>
</tbody>
</table>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field"><th class="field-name">Abstract:</th><td class="field-body">The Boost Iterator Library contains two parts. The first
is a system of <a class="reference external" href="http://www.boost.org/more/generic_programming.html#concept">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.</td>
</tr>
</tbody>
</table>
<div class="contents topic" id="table-of-contents">
<p class="topic-title first"><strong>Table of Contents</strong></p>
<ul class="simple">
<li><a class="reference internal" href="#new-style-iterators" id="id23">New-Style Iterators</a></li>
<li><a class="reference internal" href="#iterator-facade-and-adaptor" id="id24">Iterator Facade and Adaptor</a></li>
<li><a class="reference internal" href="#specialized-adaptors" id="id25">Specialized Adaptors</a></li>
<li><a class="reference internal" href="#iterator-utilities" id="id26">Iterator Utilities</a><ul>
<li><a class="reference internal" href="#traits" id="id27">Traits</a></li>
<li><a class="reference internal" href="#testing-and-concept-checking" id="id28">Testing and Concept Checking</a></li>
</ul>
</li>
<li><a class="reference internal" href="#upgrading-from-the-old-boost-iterator-adaptor-library" id="id29">Upgrading from the old Boost Iterator Adaptor Library</a></li>
<li><a class="reference internal" href="#history" id="id30">History</a></li>
</ul>
</div>
<hr class="docutils" />
<div class="section" id="new-style-iterators">
<h1><a class="toc-backref" href="#id23">New-Style Iterators</a></h1>
<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
<tt class="docutils literal"><span class="pre">vector&lt;bool&gt;::iterator</span></tt> using the C++98 categories.  This is the
infamous &quot;<tt class="docutils literal"><span class="pre">vector&lt;bool&gt;</span></tt> is not a container, and its iterators
aren't random access iterators&quot;, debacle about which Herb Sutter
wrote two papers for the standards comittee (<a class="reference external" href="http://www.gotw.ca/publications/N1185.pdf">n1185</a> and <a class="reference external" href="http://www.gotw.ca/publications/N1211.pdf">n1211</a>),
and a <a class="reference external" href="http://www.gotw.ca/gotw/050.htm">Guru of the Week</a>.  New-style iterators go well beyond
patching up <tt class="docutils literal"><span class="pre">vector&lt;bool&gt;</span></tt>, 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</p>
<blockquote>
<a class="reference external" href="new-iter-concepts.html">Standard Proposal For New-Style Iterators</a> (<a class="reference external" href="new-iter-concepts.pdf">PDF</a>)</blockquote>
</div>
<div class="section" id="iterator-facade-and-adaptor">
<h1><a class="toc-backref" href="#id24">Iterator Facade and Adaptor</a></h1>
<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 <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> 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 <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> class template, which is specially
designed to take advantage of as much of the underlying type's
behavior as possible.</p>
<p>The documentation for these two classes can be found at the following
web pages:</p>
<ul class="simple">
<li><a class="reference external" href="iterator_facade.html"><tt class="docutils literal"><span class="pre">iterator_facade</span></tt></a> (<a class="reference external" href="iterator_facade.pdf">PDF</a>)</li>
<li><a class="reference external" href="iterator_adaptor.html"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt></a> (<a class="reference external" href="iterator_adaptor.pdf">PDF</a>)</li>
</ul>
<p>Both <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> and <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> as well as many of the <a class="reference internal" href="#specialized-adaptors">specialized
adaptors</a> mentioned below have been proposed for standardization,
and accepted into the first C++ technical report; see our</p>
<blockquote>
<a class="reference external" href="facade-and-adaptor.html">Standard Proposal For Iterator Facade and Adaptor</a> (<a class="reference external" href="facade-and-adaptor.pdf">PDF</a>)</blockquote>
<p>for more details.</p>
</div>
<div class="section" id="specialized-adaptors">
<h1><a class="toc-backref" href="#id25">Specialized Adaptors</a></h1>
<p>The iterator library supplies a useful suite of standard-conforming
iterator templates based on the Boost <a class="reference internal" href="#iterator-facade-and-adaptor">iterator facade and adaptor</a>.</p>
<ul class="simple">
<li><a class="reference external" href="counting_iterator.html"><tt class="docutils literal"><span class="pre">counting_iterator</span></tt></a> (<a class="reference external" href="counting_iterator.pdf">PDF</a>): an iterator over a sequence of consecutive values.
Implements a &quot;lazy sequence&quot;</li>
<li><a class="reference external" href="filter_iterator.html"><tt class="docutils literal"><span class="pre">filter_iterator</span></tt></a> (<a class="reference external" href="filter_iterator.pdf">PDF</a>): an iterator over the subset of elements of some
sequence which satisfy a given predicate</li>
<li><a class="reference external" href="function_input_iterator.html"><tt class="docutils literal"><span class="pre">function_input_iterator</span></tt></a> (<a class="reference external" href="function_input_iterator.pdf">PDF</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><a class="reference external" href="function_output_iterator.html"><tt class="docutils literal"><span class="pre">function_output_iterator</span></tt></a> (<a class="reference external" href="function_output_iterator.pdf">PDF</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><a class="reference external" href="indirect_iterator.html"><tt class="docutils literal"><span class="pre">indirect_iterator</span></tt></a> (<a class="reference external" href="indirect_iterator.pdf">PDF</a>): an iterator over the objects <em>pointed-to</em> by the
elements of some sequence.</li>
<li><a class="reference external" href="permutation_iterator.html"><tt class="docutils literal"><span class="pre">permutation_iterator</span></tt></a> (<a class="reference external" href="permutation_iterator.pdf">PDF</a>): an iterator over the elements of some random-access
sequence, rearranged according to some sequence of integer indices.</li>
<li><a class="reference external" href="reverse_iterator.html"><tt class="docutils literal"><span class="pre">reverse_iterator</span></tt></a> (<a class="reference external" href="reverse_iterator.pdf">PDF</a>): an iterator which traverses the elements of some
bidirectional sequence in reverse.  Corrects many of the
shortcomings of C++98's <tt class="docutils literal"><span class="pre">std::reverse_iterator</span></tt>.</li>
<li><a class="reference external" href="../../utility/shared_container_iterator.html"><tt class="docutils literal"><span class="pre">shared_container_iterator</span></tt></a>: an iterator over elements of a container whose
lifetime is maintained by a <a class="reference external" href="../../smart_ptr/shared_ptr.htm"><tt class="docutils literal"><span class="pre">shared_ptr</span></tt></a> stored in the iterator.</li>
<li><a class="reference external" href="transform_iterator.html"><tt class="docutils literal"><span class="pre">transform_iterator</span></tt></a> (<a class="reference external" href="transform_iterator.pdf">PDF</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
<tt class="docutils literal"><span class="pre">projection_iterator_adaptor</span></tt>.</li>
<li><a class="reference external" href="zip_iterator.html"><tt class="docutils literal"><span class="pre">zip_iterator</span></tt></a> (<a class="reference external" href="zip_iterator.pdf">PDF</a>): an iterator over tuples of the elements at corresponding
positions of heterogeneous underlying iterators.</li>
</ul>
</div>
<div class="section" id="iterator-utilities">
<h1><a class="toc-backref" href="#id26">Iterator Utilities</a></h1>
<div class="section" id="traits">
<h2><a class="toc-backref" href="#id27">Traits</a></h2>
<ul class="simple">
<li><a class="reference external" href="pointee.html"><tt class="docutils literal"><span class="pre">pointee.hpp</span></tt></a> (<a class="reference external" href="pointee.pdf">PDF</a>): Provides the capability to deduce the referent types
of pointers, smart pointers and iterators in generic code.  Used
in <tt class="docutils literal"><span class="pre">indirect_iterator</span></tt>.</li>
<li><a class="reference external" href="iterator_traits.html"><tt class="docutils literal"><span class="pre">iterator_traits.hpp</span></tt></a> (<a class="reference external" href="iterator_traits.pdf">PDF</a>): Provides <a class="reference external" href="../../mpl/doc/index.html">MPL</a>-compatible metafunctions which
retrieve an iterator's traits.  Also corrects for the deficiencies
of broken implementations of <tt class="docutils literal"><span class="pre">std::iterator_traits</span></tt>.</li>
</ul>
<!-- * |interoperable|_ (PDF__): Provides an MPL_\ -compatible metafunction for
testing iterator interoperability -->
<!-- comment! __ interoperable.pdf -->
</div>
<div class="section" id="testing-and-concept-checking">
<h2><a class="toc-backref" href="#id28">Testing and Concept Checking</a></h2>
<ul class="simple">
<li><a class="reference external" href="iterator_concepts.html"><tt class="docutils literal"><span class="pre">iterator_concepts.hpp</span></tt></a> (<a class="reference external" href="iterator_concepts.pdf">PDF</a>): Concept checking classes for the new iterator concepts.</li>
<li><a class="reference external" href="iterator_archetypes.html"><tt class="docutils literal"><span class="pre">iterator_archetypes.hpp</span></tt></a> (<a class="reference external" href="iterator_archetypes.pdf">PDF</a>): Concept archetype classes for the new iterators concepts.</li>
</ul>
</div>
</div>
<div class="section" id="upgrading-from-the-old-boost-iterator-adaptor-library">
<h1><a class="toc-backref" href="#id29">Upgrading from the old Boost Iterator Adaptor Library</a></h1>
<p id="upgrading">If you have been using the old Boost Iterator Adaptor library to
implement iterators, you probably wrote a <tt class="docutils literal"><span class="pre">Policies</span></tt> class which
captures the core operations of your iterator.  In the new library
design, you'll move those same core operations into the body of the
iterator class itself.  If you were writing a family of iterators,
you probably wrote a <a class="reference external" href="http://www.boost.org/more/generic_programming.html#type_generator">type generator</a> to build the
<tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> specialization you needed; in the new library
design you don't need a type generator (though may want to keep it
around as a compatibility aid for older code) because, due to the
use of the Curiously Recurring Template Pattern (CRTP) <a class="citation-reference" href="#cop95" id="id22">[Cop95]</a>,
you can now define the iterator class yourself and acquire
functionality through inheritance from <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> or
<tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>.  As a result, you also get much finer control
over how your iterator works: you can add additional constructors,
or even override the iterator functionality provided by the
library.</p>
<p>If you're looking for the old <tt class="docutils literal"><span class="pre">projection_iterator</span></tt> component,
its functionality has been merged into <tt class="docutils literal"><span class="pre">transform_iterator</span></tt>: as
long as the function object's <tt class="docutils literal"><span class="pre">result_type</span></tt> (or the <tt class="docutils literal"><span class="pre">Reference</span></tt>
template argument, if explicitly specified) is a true reference
type, <tt class="docutils literal"><span class="pre">transform_iterator</span></tt> will behave like
<tt class="docutils literal"><span class="pre">projection_iterator</span></tt> used to.</p>
</div>
<div class="section" id="history">
<h1><a class="toc-backref" href="#id30">History</a></h1>
<p>In 2000 Dave Abrahams was writing an iterator for a container of
pointers, which would access the pointed-to elements when
dereferenced.  Naturally, being a library writer, he decided to
generalize the idea and the Boost Iterator Adaptor library was born.
Dave was inspired by some writings of Andrei Alexandrescu and chose a
policy based design (though he probably didn't capture Andrei's idea
very well - there was only one policy class for all the iterator's
orthogonal properties).  Soon Jeremy Siek realized he would need the
library and they worked together to produce a &quot;Boostified&quot; version,
which was reviewed and accepted into the library.  They wrote a paper
and made several important revisions of the code.</p>
<p>Eventually, several shortcomings of the older library began to make
the need for a rewrite apparent.  Dave and Jeremy started working
at the Santa Cruz C++ committee meeting in 2002, and had quickly
generated a working prototype.  At the urging of Mat Marcus, they
decided to use the GenVoca/CRTP pattern approach, and moved the
policies into the iterator class itself.  Thomas Witt expressed
interest and became the voice of strict compile-time checking for
the project, adding uses of the SFINAE technique to eliminate false
converting constructors and operators from the overload set.  He
also recognized the need for a separate <tt class="docutils literal"><span class="pre">iterator_facade</span></tt>, and
factored it out of <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>.  Finally, after a
near-complete rewrite of the prototype, they came up with the
library you see today.</p>
<table class="docutils citation" frame="void" id="cop95" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label"><a class="fn-backref" href="#id22">[Cop95]</a></td><td>[Coplien, 1995] Coplien, J., Curiously Recurring Template
Patterns, C++ Report, February 1995, pp. 24-27.</td></tr>
</tbody>
</table>
<!-- LocalWords:  Abrahams Siek Witt const bool Sutter's WG int UL LI href Lvalue
LocalWords:  ReadableIterator WritableIterator SwappableIterator cv pre iter
LocalWords:  ConstantLvalueIterator MutableLvalueIterator CopyConstructible TR
LocalWords:  ForwardTraversalIterator BidirectionalTraversalIterator lvalue
LocalWords:  RandomAccessTraversalIterator dereferenceable Incrementable tmp
LocalWords:  incrementable xxx min prev inplace png oldeqnew AccessTag struct
LocalWords:  TraversalTag typename lvalues DWA Hmm JGS -->
</div>
</div>
<div class="footer">
<hr class="footer" />
<a class="reference external" href="index.rst">View document source</a>.
Generated 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.

</div>
</body>
</html>
Commit	Line	Data
7c673cae FG	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.6: http://docutils.sourceforge.net/" />
	7	<title>The Boost.Iterator Library Boost</title>
	8	<link rel="stylesheet" href="../../../rst.css" type="text/css" />
	9	</head>
	10	<body>
	11	<div class="document" id="the-boost-iterator-library-logo">
	12	<h1 class="title">The Boost.Iterator Library <a class="reference external" href="../../../index.htm"><img alt="Boost" src="../../../boost.png" /></a></h1>
	13
	14	<!-- Distributed under the Boost -->
	15	<!-- Software License, Version 1.0. (See accompanying -->
	16	<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
	17	<hr class="docutils" />
	18	<table class="docutils field-list" frame="void" rules="none">
	19	<col class="field-name" />
	20	<col class="field-body" />
	21	<tbody valign="top">
	22	<tr class="field"><th class="field-name">Authors:</th><td class="field-body">David Abrahams, Jeremy Siek, Thomas Witt</td>
	23	</tr>
	24	<tr class="field"><th class="field-name">Contact:</th><td class="field-body"><a class="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="reference external" href="mailto:witt@styleadvisor.com">witt@styleadvisor.com</a></td>
	25	</tr>
	26	<tr class="field"><th class="field-name">organizations:</th><td class="field-body"><a class="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
	27	Lab</a>, <a class="reference external" href="http://www.styleadvisor.com">Zephyr Associates, Inc.</a></td>
	28	</tr>
	29	<tr class="field"><th class="field-name">date:</th><td class="field-body">$Date$</td>
	30	</tr>
	31	<tr class="field"><th class="field-name">copyright:</th><td class="field-body">Copyright David Abrahams, Jeremy Siek, Thomas Witt 2003.</td>
	32	</tr>
	33	</tbody>
	34	</table>
	35	<table class="docutils field-list" frame="void" rules="none">
	36	<col class="field-name" />
	37	<col class="field-body" />
	38	<tbody valign="top">
	39	<tr class="field"><th class="field-name">Abstract:</th><td class="field-body">The Boost Iterator Library contains two parts. The first
	40	is a system of <a class="reference external" href="http://www.boost.org/more/generic_programming.html#concept">concepts</a> which extend the C++ standard
	41	iterator requirements. The second is a framework of
	42	components for building iterators based on these
	43	extended concepts and includes several useful iterator
	44	adaptors. The extended iterator concepts have been
	45	carefully designed so that old-style iterators
	46	can fit in the new concepts and so that new-style
	47	iterators will be compatible with old-style algorithms,
	48	though algorithms may need to be updated if they want to
	49	take full advantage of the new-style iterator
	50	capabilities. Several components of this library have
	51	been accepted into the C++ standard technical report.
	52	The components of the Boost Iterator Library replace the
	53	older Boost Iterator Adaptor Library.</td>
	54	</tr>
	55	</tbody>
	56	</table>
	57	<div class="contents topic" id="table-of-contents">
	58	<p class="topic-title first"><strong>Table of Contents</strong></p>
	59	<ul class="simple">
	60	<li><a class="reference internal" href="#new-style-iterators" id="id23">New-Style Iterators</a></li>
	61	<li><a class="reference internal" href="#iterator-facade-and-adaptor" id="id24">Iterator Facade and Adaptor</a></li>
	62	<li><a class="reference internal" href="#specialized-adaptors" id="id25">Specialized Adaptors</a></li>
	63	<li><a class="reference internal" href="#iterator-utilities" id="id26">Iterator Utilities</a><ul>
	64	<li><a class="reference internal" href="#traits" id="id27">Traits</a></li>
65	<li><a class="reference internal" href="#testing-and-concept-checking" id="id28">Testing and Concept Checking</a></li>
66	</ul>
67	</li>
68	<li><a class="reference internal" href="#upgrading-from-the-old-boost-iterator-adaptor-library" id="id29">Upgrading from the old Boost Iterator Adaptor Library</a></li>
69	<li><a class="reference internal" href="#history" id="id30">History</a></li>
70	</ul>
71	</div>
72	<hr class="docutils" />
73	<div class="section" id="new-style-iterators">
74	<h1><a class="toc-backref" href="#id23">New-Style Iterators</a></h1>
75	<p>The iterator categories defined in C++98 are extremely limiting
76	because they bind together two orthogonal concepts: traversal and
77	element access. For example, because a random access iterator is
78	required to return a reference (and not a proxy) when dereferenced,
79	it is impossible to capture the capabilities of
80	<tt class="docutils literal"><span class="pre">vector<bool>::iterator</span></tt> using the C++98 categories. This is the
81	infamous "<tt class="docutils literal"><span class="pre">vector<bool></span></tt> is not a container, and its iterators
82	aren't random access iterators", debacle about which Herb Sutter
83	wrote two papers for the standards comittee (<a class="reference external" href="http://www.gotw.ca/publications/N1185.pdf">n1185</a> and <a class="reference external" href="http://www.gotw.ca/publications/N1211.pdf">n1211</a>),
84	and a <a class="reference external" href="http://www.gotw.ca/gotw/050.htm">Guru of the Week</a>. New-style iterators go well beyond
85	patching up <tt class="docutils literal"><span class="pre">vector<bool></span></tt>, though: there are lots of other
86	iterators already in use which can't be adequately represented by
87	the existing concepts. For details about the new iterator
88	concepts, see our</p>
89	<blockquote>
90	<a class="reference external" href="new-iter-concepts.html">Standard Proposal For New-Style Iterators</a> (<a class="reference external" href="new-iter-concepts.pdf">PDF</a>)</blockquote>
91	</div>
92	<div class="section" id="iterator-facade-and-adaptor">
93	<h1><a class="toc-backref" href="#id24">Iterator Facade and Adaptor</a></h1>
94	<p>Writing standard-conforming iterators is tricky, but the need comes
95	up often. In order to ease the implementation of new iterators,
96	the Boost.Iterator library provides the <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> class template,
97	which implements many useful defaults and compile-time checks
98	designed to help the iterator author ensure that his iterator is
99	correct.</p>
100	<p>It is also common to define a new iterator that is similar to some
101	underlying iterator or iterator-like type, but that modifies some
102	aspect of the underlying type's behavior. For that purpose, the
103	library supplies the <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> class template, which is specially
104	designed to take advantage of as much of the underlying type's
105	behavior as possible.</p>
106	<p>The documentation for these two classes can be found at the following
107	web pages:</p>
108	<ul class="simple">
109	<li><a class="reference external" href="iterator_facade.html"><tt class="docutils literal"><span class="pre">iterator_facade</span></tt></a> (<a class="reference external" href="iterator_facade.pdf">PDF</a>)</li>
110	<li><a class="reference external" href="iterator_adaptor.html"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt></a> (<a class="reference external" href="iterator_adaptor.pdf">PDF</a>)</li>
111	</ul>
112	<p>Both <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> and <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> as well as many of the <a class="reference internal" href="#specialized-adaptors">specialized
113	adaptors</a> mentioned below have been proposed for standardization,
114	and accepted into the first C++ technical report; see our</p>
115	<blockquote>
116	<a class="reference external" href="facade-and-adaptor.html">Standard Proposal For Iterator Facade and Adaptor</a> (<a class="reference external" href="facade-and-adaptor.pdf">PDF</a>)</blockquote>
117	<p>for more details.</p>
118	</div>
119	<div class="section" id="specialized-adaptors">
120	<h1><a class="toc-backref" href="#id25">Specialized Adaptors</a></h1>
121	<p>The iterator library supplies a useful suite of standard-conforming
122	iterator templates based on the Boost <a class="reference internal" href="#iterator-facade-and-adaptor">iterator facade and adaptor</a>.</p>
123	<ul class="simple">
124	<li><a class="reference external" href="counting_iterator.html"><tt class="docutils literal"><span class="pre">counting_iterator</span></tt></a> (<a class="reference external" href="counting_iterator.pdf">PDF</a>): an iterator over a sequence of consecutive values.
125	Implements a "lazy sequence"</li>
126	<li><a class="reference external" href="filter_iterator.html"><tt class="docutils literal"><span class="pre">filter_iterator</span></tt></a> (<a class="reference external" href="filter_iterator.pdf">PDF</a>): an iterator over the subset of elements of some
127	sequence which satisfy a given predicate</li>
128	<li><a class="reference external" href="function_input_iterator.html"><tt class="docutils literal"><span class="pre">function_input_iterator</span></tt></a> (<a class="reference external" href="function_input_iterator.pdf">PDF</a>): an input iterator wrapping a generator (nullary
129	function object); each time the iterator is dereferenced, the function object
130	is called to get the value to return.</li>
131	<li><a class="reference external" href="function_output_iterator.html"><tt class="docutils literal"><span class="pre">function_output_iterator</span></tt></a> (<a class="reference external" href="function_output_iterator.pdf">PDF</a>): an output iterator wrapping a unary function
132	object; each time an element is written into the dereferenced
133	iterator, it is passed as a parameter to the function object.</li>
134	<li><a class="reference external" href="indirect_iterator.html"><tt class="docutils literal"><span class="pre">indirect_iterator</span></tt></a> (<a class="reference external" href="indirect_iterator.pdf">PDF</a>): an iterator over the objects <em>pointed-to</em> by the
135	elements of some sequence.</li>
136	<li><a class="reference external" href="permutation_iterator.html"><tt class="docutils literal"><span class="pre">permutation_iterator</span></tt></a> (<a class="reference external" href="permutation_iterator.pdf">PDF</a>): an iterator over the elements of some random-access
137	sequence, rearranged according to some sequence of integer indices.</li>
138	<li><a class="reference external" href="reverse_iterator.html"><tt class="docutils literal"><span class="pre">reverse_iterator</span></tt></a> (<a class="reference external" href="reverse_iterator.pdf">PDF</a>): an iterator which traverses the elements of some
139	bidirectional sequence in reverse. Corrects many of the
140	shortcomings of C++98's <tt class="docutils literal"><span class="pre">std::reverse_iterator</span></tt>.</li>
141	<li><a class="reference external" href="../../utility/shared_container_iterator.html"><tt class="docutils literal"><span class="pre">shared_container_iterator</span></tt></a>: an iterator over elements of a container whose
142	lifetime is maintained by a <a class="reference external" href="../../smart_ptr/shared_ptr.htm"><tt class="docutils literal"><span class="pre">shared_ptr</span></tt></a> stored in the iterator.</li>
143	<li><a class="reference external" href="transform_iterator.html"><tt class="docutils literal"><span class="pre">transform_iterator</span></tt></a> (<a class="reference external" href="transform_iterator.pdf">PDF</a>): an iterator over elements which are the result of
144	applying some functional transformation to the elements of an
145	underlying sequence. This component also replaces the old
146	<tt class="docutils literal"><span class="pre">projection_iterator_adaptor</span></tt>.</li>
147	<li><a class="reference external" href="zip_iterator.html"><tt class="docutils literal"><span class="pre">zip_iterator</span></tt></a> (<a class="reference external" href="zip_iterator.pdf">PDF</a>): an iterator over tuples of the elements at corresponding
148	positions of heterogeneous underlying iterators.</li>
149	</ul>
150	</div>
151	<div class="section" id="iterator-utilities">
152	<h1><a class="toc-backref" href="#id26">Iterator Utilities</a></h1>
153	<div class="section" id="traits">
154	<h2><a class="toc-backref" href="#id27">Traits</a></h2>
155	<ul class="simple">
156	<li><a class="reference external" href="pointee.html"><tt class="docutils literal"><span class="pre">pointee.hpp</span></tt></a> (<a class="reference external" href="pointee.pdf">PDF</a>): Provides the capability to deduce the referent types
157	of pointers, smart pointers and iterators in generic code. Used
158	in <tt class="docutils literal"><span class="pre">indirect_iterator</span></tt>.</li>
159	<li><a class="reference external" href="iterator_traits.html"><tt class="docutils literal"><span class="pre">iterator_traits.hpp</span></tt></a> (<a class="reference external" href="iterator_traits.pdf">PDF</a>): Provides <a class="reference external" href="../../mpl/doc/index.html">MPL</a>-compatible metafunctions which
160	retrieve an iterator's traits. Also corrects for the deficiencies
161	of broken implementations of <tt class="docutils literal"><span class="pre">std::iterator_traits</span></tt>.</li>
162	</ul>
163	<!-- * \|interoperable\|_ (PDF__): Provides an MPL_\ -compatible metafunction for
164	testing iterator interoperability -->
165	<!-- comment! __ interoperable.pdf -->
166	</div>
167	<div class="section" id="testing-and-concept-checking">
168	<h2><a class="toc-backref" href="#id28">Testing and Concept Checking</a></h2>
169	<ul class="simple">
170	<li><a class="reference external" href="iterator_concepts.html"><tt class="docutils literal"><span class="pre">iterator_concepts.hpp</span></tt></a> (<a class="reference external" href="iterator_concepts.pdf">PDF</a>): Concept checking classes for the new iterator concepts.</li>
171	<li><a class="reference external" href="iterator_archetypes.html"><tt class="docutils literal"><span class="pre">iterator_archetypes.hpp</span></tt></a> (<a class="reference external" href="iterator_archetypes.pdf">PDF</a>): Concept archetype classes for the new iterators concepts.</li>
172	</ul>
173	</div>
174	</div>
175	<div class="section" id="upgrading-from-the-old-boost-iterator-adaptor-library">
176	<h1><a class="toc-backref" href="#id29">Upgrading from the old Boost Iterator Adaptor Library</a></h1>
177	<p id="upgrading">If you have been using the old Boost Iterator Adaptor library to
178	implement iterators, you probably wrote a <tt class="docutils literal"><span class="pre">Policies</span></tt> class which
179	captures the core operations of your iterator. In the new library
180	design, you'll move those same core operations into the body of the
181	iterator class itself. If you were writing a family of iterators,
182	you probably wrote a <a class="reference external" href="http://www.boost.org/more/generic_programming.html#type_generator">type generator</a> to build the
183	<tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> specialization you needed; in the new library
184	design you don't need a type generator (though may want to keep it
185	around as a compatibility aid for older code) because, due to the
186	use of the Curiously Recurring Template Pattern (CRTP) <a class="citation-reference" href="#cop95" id="id22">[Cop95]</a>,
187	you can now define the iterator class yourself and acquire
188	functionality through inheritance from <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> or
189	<tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>. As a result, you also get much finer control
190	over how your iterator works: you can add additional constructors,
191	or even override the iterator functionality provided by the
192	library.</p>
193	<p>If you're looking for the old <tt class="docutils literal"><span class="pre">projection_iterator</span></tt> component,
194	its functionality has been merged into <tt class="docutils literal"><span class="pre">transform_iterator</span></tt>: as
195	long as the function object's <tt class="docutils literal"><span class="pre">result_type</span></tt> (or the <tt class="docutils literal"><span class="pre">Reference</span></tt>
196	template argument, if explicitly specified) is a true reference
197	type, <tt class="docutils literal"><span class="pre">transform_iterator</span></tt> will behave like
198	<tt class="docutils literal"><span class="pre">projection_iterator</span></tt> used to.</p>
199	</div>
200	<div class="section" id="history">
201	<h1><a class="toc-backref" href="#id30">History</a></h1>
202	<p>In 2000 Dave Abrahams was writing an iterator for a container of
203	pointers, which would access the pointed-to elements when
204	dereferenced. Naturally, being a library writer, he decided to
205	generalize the idea and the Boost Iterator Adaptor library was born.
206	Dave was inspired by some writings of Andrei Alexandrescu and chose a
207	policy based design (though he probably didn't capture Andrei's idea
208	very well - there was only one policy class for all the iterator's
209	orthogonal properties). Soon Jeremy Siek realized he would need the
210	library and they worked together to produce a "Boostified" version,
211	which was reviewed and accepted into the library. They wrote a paper
212	and made several important revisions of the code.</p>
213	<p>Eventually, several shortcomings of the older library began to make
214	the need for a rewrite apparent. Dave and Jeremy started working
215	at the Santa Cruz C++ committee meeting in 2002, and had quickly
216	generated a working prototype. At the urging of Mat Marcus, they
217	decided to use the GenVoca/CRTP pattern approach, and moved the
218	policies into the iterator class itself. Thomas Witt expressed
219	interest and became the voice of strict compile-time checking for
220	the project, adding uses of the SFINAE technique to eliminate false
221	converting constructors and operators from the overload set. He
222	also recognized the need for a separate <tt class="docutils literal"><span class="pre">iterator_facade</span></tt>, and
223	factored it out of <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>. Finally, after a
224	near-complete rewrite of the prototype, they came up with the
225	library you see today.</p>
226	<table class="docutils citation" frame="void" id="cop95" rules="none">
227	<colgroup><col class="label" /><col /></colgroup>
228	<tbody valign="top">
229	<tr><td class="label"><a class="fn-backref" href="#id22">[Cop95]</a></td><td>[Coplien, 1995] Coplien, J., Curiously Recurring Template
230	Patterns, C++ Report, February 1995, pp. 24-27.</td></tr>
231	</tbody>
232	</table>
233	<!-- LocalWords: Abrahams Siek Witt const bool Sutter's WG int UL LI href Lvalue
234	LocalWords: ReadableIterator WritableIterator SwappableIterator cv pre iter
235	LocalWords: ConstantLvalueIterator MutableLvalueIterator CopyConstructible TR
236	LocalWords: ForwardTraversalIterator BidirectionalTraversalIterator lvalue
237	LocalWords: RandomAccessTraversalIterator dereferenceable Incrementable tmp
238	LocalWords: incrementable xxx min prev inplace png oldeqnew AccessTag struct
239	LocalWords: TraversalTag typename lvalues DWA Hmm JGS -->
240	</div>
241	</div>
242	<div class="footer">
243	<hr class="footer" />
244	<a class="reference external" href="index.rst">View document source</a>.
245	Generated 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.
246
247	</div>
248	</body>
249	</html>