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 27Lab</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 40is a system of <a class="reference external" href="http://www.boost.org/more/generic_programming.html#concept">concepts</a> which extend the C++ standard 41iterator requirements. The second is a framework of 42components for building iterators based on these 43extended concepts and includes several useful iterator 44adaptors. The extended iterator concepts have been 45carefully designed so that old-style iterators 46can fit in the new concepts and so that new-style 47iterators will be compatible with old-style algorithms, 48though algorithms may need to be updated if they want to 49take full advantage of the new-style iterator 50capabilities. Several components of this library have 51been accepted into the C++ standard technical report. 52The components of the Boost Iterator Library replace the 53older 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 76because they bind together two orthogonal concepts: traversal and 77element access. For example, because a random access iterator is 78required to return a reference (and not a proxy) when dereferenced, 79it 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 81infamous "<tt class="docutils literal"><span class="pre">vector<bool></span></tt> is not a container, and its iterators 82aren't random access iterators", debacle about which Herb Sutter 83wrote 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>), 84and a <a class="reference external" href="http://www.gotw.ca/gotw/050.htm">Guru of the Week</a>. New-style iterators go well beyond 85patching up <tt class="docutils literal"><span class="pre">vector<bool></span></tt>, though: there are lots of other 86iterators already in use which can't be adequately represented by 87the existing concepts. For details about the new iterator 88concepts, 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 95up often. In order to ease the implementation of new iterators, 96the Boost.Iterator library provides the <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> class template, 97which implements many useful defaults and compile-time checks 98designed to help the iterator author ensure that his iterator is 99correct.</p> 100<p>It is also common to define a new iterator that is similar to some 101underlying iterator or iterator-like type, but that modifies some 102aspect of the underlying type's behavior. For that purpose, the 103library supplies the <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> class template, which is specially 104designed to take advantage of as much of the underlying type's 105behavior as possible.</p> 106<p>The documentation for these two classes can be found at the following 107web 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 113adaptors</a> mentioned below have been proposed for standardization, 114and 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 122iterator 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. 125Implements 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 127sequence 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 129function object); each time the iterator is dereferenced, the function object 130is 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 132object; each time an element is written into the dereferenced 133iterator, it is passed as a parameter to the function object.</li> 134<li><a class="reference external" href="generator_iterator.htm"><tt class="docutils literal"><span class="pre">generator_iterator</span></tt></a>: an input iterator wrapping a reference to a generator (nullary function object); 135each time the iterator is dereferenced, the function object 136is called to get the value to return. This is a more outdated analogue of <tt class="docutils literal"><span class="pre">function_input_iterator</span></tt>.</li> 137<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 138elements of some sequence.</li> 139<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 140sequence, rearranged according to some sequence of integer indices.</li> 141<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 142bidirectional sequence in reverse. Corrects many of the 143shortcomings of C++98's <tt class="docutils literal"><span class="pre">std::reverse_iterator</span></tt>.</li> 144<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 145lifetime 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> 146<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 147applying some functional transformation to the elements of an 148underlying sequence. This component also replaces the old 149<tt class="docutils literal"><span class="pre">projection_iterator_adaptor</span></tt>.</li> 150<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 151positions of heterogeneous underlying iterators.</li> 152</ul> 153</div> 154<div class="section" id="iterator-utilities"> 155<h1><a class="toc-backref" href="#id26">Iterator Utilities</a></h1> 156<div class="section" id="traits"> 157<h2><a class="toc-backref" href="#id27">Traits</a></h2> 158<ul class="simple"> 159<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 160of pointers, smart pointers and iterators in generic code. Used 161in <tt class="docutils literal"><span class="pre">indirect_iterator</span></tt>.</li> 162<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 163retrieve an iterator's traits. Also corrects for the deficiencies 164of broken implementations of <tt class="docutils literal"><span class="pre">std::iterator_traits</span></tt>.</li> 165</ul> 166<!-- * |interoperable|_ (PDF__): Provides an MPL_\ -compatible metafunction for 167testing iterator interoperability --> 168<!-- comment! __ interoperable.pdf --> 169</div> 170<div class="section" id="testing-and-concept-checking"> 171<h2><a class="toc-backref" href="#id28">Testing and Concept Checking</a></h2> 172<ul class="simple"> 173<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> 174<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> 175</ul> 176</div> 177</div> 178<div class="section" id="upgrading-from-the-old-boost-iterator-adaptor-library"> 179<h1><a class="toc-backref" href="#id29">Upgrading from the old Boost Iterator Adaptor Library</a></h1> 180<p id="upgrading">If you have been using the old Boost Iterator Adaptor library to 181implement iterators, you probably wrote a <tt class="docutils literal"><span class="pre">Policies</span></tt> class which 182captures the core operations of your iterator. In the new library 183design, you'll move those same core operations into the body of the 184iterator class itself. If you were writing a family of iterators, 185you probably wrote a <a class="reference external" href="http://www.boost.org/more/generic_programming.html#type_generator">type generator</a> to build the 186<tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> specialization you needed; in the new library 187design you don't need a type generator (though may want to keep it 188around as a compatibility aid for older code) because, due to the 189use of the Curiously Recurring Template Pattern (CRTP) <a class="citation-reference" href="#cop95" id="id22">[Cop95]</a>, 190you can now define the iterator class yourself and acquire 191functionality through inheritance from <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> or 192<tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>. As a result, you also get much finer control 193over how your iterator works: you can add additional constructors, 194or even override the iterator functionality provided by the 195library.</p> 196<p>If you're looking for the old <tt class="docutils literal"><span class="pre">projection_iterator</span></tt> component, 197its functionality has been merged into <tt class="docutils literal"><span class="pre">transform_iterator</span></tt>: as 198long 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> 199template argument, if explicitly specified) is a true reference 200type, <tt class="docutils literal"><span class="pre">transform_iterator</span></tt> will behave like 201<tt class="docutils literal"><span class="pre">projection_iterator</span></tt> used to.</p> 202</div> 203<div class="section" id="history"> 204<h1><a class="toc-backref" href="#id30">History</a></h1> 205<p>In 2000 Dave Abrahams was writing an iterator for a container of 206pointers, which would access the pointed-to elements when 207dereferenced. Naturally, being a library writer, he decided to 208generalize the idea and the Boost Iterator Adaptor library was born. 209Dave was inspired by some writings of Andrei Alexandrescu and chose a 210policy based design (though he probably didn't capture Andrei's idea 211very well - there was only one policy class for all the iterator's 212orthogonal properties). Soon Jeremy Siek realized he would need the 213library and they worked together to produce a "Boostified" version, 214which was reviewed and accepted into the library. They wrote a paper 215and made several important revisions of the code.</p> 216<p>Eventually, several shortcomings of the older library began to make 217the need for a rewrite apparent. Dave and Jeremy started working 218at the Santa Cruz C++ committee meeting in 2002, and had quickly 219generated a working prototype. At the urging of Mat Marcus, they 220decided to use the GenVoca/CRTP pattern approach, and moved the 221policies into the iterator class itself. Thomas Witt expressed 222interest and became the voice of strict compile-time checking for 223the project, adding uses of the SFINAE technique to eliminate false 224converting constructors and operators from the overload set. He 225also recognized the need for a separate <tt class="docutils literal"><span class="pre">iterator_facade</span></tt>, and 226factored it out of <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>. Finally, after a 227near-complete rewrite of the prototype, they came up with the 228library you see today.</p> 229<table class="docutils citation" frame="void" id="cop95" rules="none"> 230<colgroup><col class="label" /><col /></colgroup> 231<tbody valign="top"> 232<tr><td class="label"><a class="fn-backref" href="#id22">[Cop95]</a></td><td>[Coplien, 1995] Coplien, J., Curiously Recurring Template 233Patterns, C++ Report, February 1995, pp. 24-27.</td></tr> 234</tbody> 235</table> 236<!-- LocalWords: Abrahams Siek Witt const bool Sutter's WG int UL LI href Lvalue 237LocalWords: ReadableIterator WritableIterator SwappableIterator cv pre iter 238LocalWords: ConstantLvalueIterator MutableLvalueIterator CopyConstructible TR 239LocalWords: ForwardTraversalIterator BidirectionalTraversalIterator lvalue 240LocalWords: RandomAccessTraversalIterator dereferenceable Incrementable tmp 241LocalWords: incrementable xxx min prev inplace png oldeqnew AccessTag struct 242LocalWords: TraversalTag typename lvalues DWA Hmm JGS --> 243</div> 244</div> 245<div class="footer"> 246<hr class="footer" /> 247<a class="reference external" href="index.rst">View document source</a>. 248Generated 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. 249 250</div> 251</body> 252</html> 253
