libs/iterator/doc/index.html

   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&#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>
  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&lt;bool&gt;::iterator</span></tt> using the C++98 categories.  This is the
  81 infamous &quot;<tt class="docutils literal"><span class="pre">vector&lt;bool&gt;</span></tt> is not a container, and its iterators
  82 aren't random access iterators&quot;, 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&lt;bool&gt;</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 &quot;lazy sequence&quot;</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 &quot;Boostified&quot; 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>