File: iterator_adaptors.htm

package info (click to toggle)
boost 1.27.0-3
links: PTS
area: main
in suites: woody
size: 19,908 kB
ctags: 26,546
sloc: cpp: 122,225; ansic: 10,956; python: 4,412; sh: 855; yacc: 803; makefile: 257; perl: 165; lex: 90; csh: 6
file content (939 lines) | stat: -rw-r--r-- 38,555 bytes
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">

<html>
<head>
    <meta name="generator" content="HTML Tidy, see www.w3.org">
    <meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
    <meta name="GENERATOR" content="Microsoft FrontPage 4.0">
    <meta name="ProgId" content="FrontPage.Editor.Document">

    <title>Boost Iterator Adaptor Library</title>
</head>

<body bgcolor="#FFFFFF" text="#000000">

    <img src="../../c++boost.gif" alt="c++boost.gif (8819 bytes)" align=
    "center" width="277" height="86"> 

    <h1>Boost Iterator Adaptor Library</h1>

    <h2>Introduction</h2>

    <p>The Iterator Adaptor library allows you transform an arbitrary ``base''
    type into a standard-conforming iterator with the behaviors you choose.
    Doing so is especially easy if the ``base'' type is itself an iterator. The
    library also supplies several example <a href=
    "../../more/generic_programming.html#adaptors">adaptors</a> which apply
    specific useful behaviors to arbitrary base iterators.

    <h2>Backward Compatibility Note</h2>

    <p>The library's interface has changed since it was first released, breaking
    backward compatibility:

    <ol>

    <li><a href="#policies">Policies classes</a> now operate on instances of the
    whole <tt>iterator_adaptor</tt> object, rather than just operating on the
    <tt>Base</tt> object. This change not only gives the policies class access
    to both members of a pair of interacting iterators, but also eliminates the
    need for the ugly <tt>type&lt;Reference&gt;</tt> and
    <tt>type&lt;Difference&gt;</tt> parameters to various policy functions.

    <li>The <a href="#named_template_parameters">Named Template Parameter</a>
    interface has been made simpler, easier to use, and compatible with more
    compilers.

    </ol>

    <h2>Other Documentation</h2>

    <p><a href="iterator_adaptors.pdf">``Policy Adaptors and the Boost Iterator
    Adaptor Library''</a> is a technical paper describing this library and the
    powerful design pattern on which it is based. It was presented at the <a
    href="http://www.oonumerics.org/tmpw01">C++ Template Workshop</a> at OOPSLA
    2001; the slides from the talk are available <a
    href="iterator_adaptors.ppt">here</a>. Please note that while the slides
    incorporate the minor interface changes described in the previous section,
    the paper does not.

    <h2>Table of Contents</h2>

    <ul>
      <li>
        Header <tt><a href=
        "../../boost/iterator_adaptors.hpp">boost/iterator_adaptors.hpp</a></tt>
        

        <ul>
          <li>
            Generalized Iterator Adaptor 

            <ul>
              <li>Class template <tt><a href=
              "#iterator_adaptor">iterator_adaptor</a></tt>

              <li><a href="#template_parameters">Template Parameters</a>

              <li><a href="#named_template_parameters">Named Template Parameters</a>

              <li><a href="#policies">The Policies Class</a>

              <li><a href="#additional_members">Additional Class Members</a>

              <li><a href="#example">Example</a>

              <li>(<tt>const</tt>/non-<tt>const</tt>) <a href=
              "#iterator_interactions">Iterator Interactions</a>

              <li><a href="#challenge">Challenge</a>

              <li><a href="#concept_model">Concept Model</a>

              <li><a href="#declaration_synopsis">Declaration Synopsis</a>

              <li><a href="#notes">Notes</a>
            </ul>

          <li>
            <a name="specialized_adaptors">Specialized Iterator Adaptors</a> 

            <ul>
              <li><a href="indirect_iterator.htm">Indirect Iterator Adaptor</a>

              <li><a href="reverse_iterator.htm">Reverse Iterator Adaptor</a>

              <li><a href="transform_iterator.htm">Transform Iterator
              Adaptor</a>

              <li><a href="projection_iterator.htm">Projection Iterator
              Adaptor</a>

              <li><a href="filter_iterator.htm">Filter Iterator Adaptor</a>
            </ul>
        </ul>

      <li>Header <tt><a href=
      "../../boost/counting_iterator.hpp">boost/counting_iterator.hpp</a></tt><br>

       <a href="counting_iterator.htm">Counting Iterator Adaptor</a>

      <li>Header <tt><a href=
      "../../boost/function_output_iterator.hpp">boost/function_output_iterator.hpp</a></tt><br>

       <a href="function_output_iterator.htm">Function Output Iterator Adaptor</a>
      <li>Header <tt><a href="../../boost/generator_iterator.hpp">boost/generator_iterator.hpp</a></tt><br>
       <a href="generator_iterator.htm">Generator Iterator Adaptor</a>
      <li>Header <tt><a href="../../boost/permutation_iterator.hpp">boost/permutation_iterator.hpp</a></tt><br>
       <a href="permutation_iterator.htm">Permutation Iterator Adaptor</a>
    </ul>

    <p><b><a href="../../people/dave_abrahams.htm">Dave
    Abrahams</a></b> started the library, applying <a href=
    "../../more/generic_programming.html#policy">policy class</a> technique and
    handling const/non-const iterator interactions. He also contributed the
    <tt><a href="indirect_iterator.htm">indirect_</a></tt> and <tt><a href=
    "reverse_iterator.htm">reverse_</a></tt> iterator generators, and expanded
    <tt><a href="counting_iterator.htm">counting_iterator_generator</a></tt> to
    cover all incrementable types. He edited most of the documentation,
    sometimes heavily.<br>
     <b><a href="../../people/jeremy_siek.htm">Jeremy
    Siek</a></b> contributed the <a href="transform_iterator.htm">transform
    iterator</a> adaptor, the integer-only version of <tt><a href=
    "counting_iterator.htm">counting_iterator_generator</a></tt>, 
    the <a href="function_output_iterator.htm">function output iterator</a> 
    adaptor, and most of the documentation.<br>
     <b><a href="http://www.boost.org/people/john_potter.htm">John
    Potter</a></b> contributed the <tt><a href=
    "projection_iterator.htm">projection_</a></tt> and <tt><a href=
    "filter_iterator.htm">filter_</a></tt> iterator generators and made some
    simplifications to the main <tt><a href=
    "#iterator_adaptor">iterator_adaptor</a></tt> template.<br>
    <b><a href="../../people/jens_maurer.htm">Jens Maurer</a></b>
    contributed the <a href="generator_iterator.htm">generator iterator</a>
    adaptor.<br>
    Toon Knapen contributed the <a href="permutation_iterator.htm">permutation
    iterator</a> adaptor.<br>

    <h2><a name="iterator_adaptor">Class template</a>
    <tt>iterator_adaptor</tt></h2>
    Implementing standard conforming iterators is a non-trivial task. There are
    some fine points such as the interactions between an iterator and its
    corresponding const_iterator, and there are myriad operators that should be
    implemented but are easily forgotten or mishandled, such as
    <tt>operator-&gt;()</tt>. Using <tt>iterator_adaptor</tt>, you can easily
    implement an iterator class, and even more easily extend and <a href=
    "../../more/generic_programming.html#adaptors">adapt</a> existing iterator
    types. Moreover, it is easy to make a pair of interoperable <tt>const</tt>
    and <tt>non-const</tt> iterators. 

    <p><tt>iterator_adaptor</tt> is declared like this:
<pre>
template &lt;class Base, class Policies, 
    class ValueOrNamedParam = typename std::iterator_traits&lt;Base&gt;::value_type,
    class ReferenceOrNamedParam = <i>...(see below)</i>,
    class PointerOrNamedParam = <i>...(see below)</i>,
    class CategoryOrNamedParam = typename std::iterator_traits&lt;Base&gt;::iterator_category,
    class DistanceOrNamedParam = typename std::iterator_traits&lt;Base&gt;::difference_type&gt;
struct iterator_adaptor;
</pre>

    <h3><a name="template_parameters">Template Parameters</a></h3>

    <p>Although <tt>iterator_adaptor</tt> takes seven template parameters,
    defaults have been carefully chosen to minimize the number of parameters
    you must supply in most cases, especially if <tt>BaseType</tt> is an
    iterator.

    <table border="1" summary="iterator_adaptor template parameters">
      <tr>
        <th>Parameter

        <th>Description

      <tr>
        <td><tt>BaseType</tt> 

        <td>The type being wrapped.

      <tr>
        <td><tt>Policies</tt> 

        <td>A <a href="../../more/generic_programming.html#policy">policy
        class</a> that supplies core functionality to the resulting iterator. A
        detailed description can be found <a href="#policies">below</a>.

      <tr>
        <td><tt>Value</tt> 

        <td>The <tt>value_type</tt> of the resulting iterator, unless const. If
        Value is <tt>const X</tt> the
        <tt>value_type</tt> will be (<i>non-</i><tt>const</tt>) <tt>X</tt><a href=
        "#1">[1]</a>. If the <tt>value_type</tt> you wish to use is an abstract
        base class see note <a href="#5">[5]</a>.<br>
         <b>Default:</b>
        <tt>std::iterator_traits&lt;BaseType&gt;::value_type</tt> <a href=
        "#2">[2]</a>

      <tr>
        <td><tt>Reference</tt> 

        <td>The <tt>reference</tt> type of the resulting iterator, and in
        particular, the result type of <tt>operator*()</tt>.<br>
         <b>Default:</b> If <tt>Value</tt> is supplied, <tt>Value&amp;</tt> is
        used. Otherwise
        <tt>std::iterator_traits&lt;BaseType&gt;::reference</tt> is used. <a href="#7">[7]</a>

      <tr>
        <td><tt>Pointer</tt> 

        <td>The <tt>pointer</tt> type of the resulting iterator, and in
        particular, the result type of <tt>operator-&gt;()</tt>.<br>
         <b>Default:</b> If <tt>Value</tt> was supplied, then <tt>Value*</tt>,
        otherwise <tt>std::iterator_traits&lt;BaseType&gt;::pointer</tt>. <a href="#7">[7]</a>

      <tr>
        <td><tt>Category</tt> 

        <td>The <tt>iterator_category</tt> type for the resulting iterator.<br>
         <b>Default:</b>
        <tt>std::iterator_traits&lt;BaseType&gt;::iterator_category</tt> 

      <tr>
        <td><tt>Distance</tt> 

        <td>The <tt>difference_type</tt> for the resulting iterator.<br>
         <b>Default:</b>
        <tt>std::iterator_traits&lt;BaseType&gt;::difference_type</tt> 

      <tr>
         <td><tt>NamedParam</tt>

         <td>A named template parameter (see below).
    </table>

    <h3><a name="named_template_parameters">Named Template Parameters</a></h3>
    
    With seven template parameters, providing arguments for
    <tt>iterator_adaptor</tt> in the correct order can be challenging.
    Also, often times one would like to specify the sixth or seventh
    template parameter, but use the defaults for the third through
    fifth. As a solution to these problems we provide a mechanism for
    naming the last five template parameters, and providing them in
    any order through a set of named template parameters. The following
    classes are provided for specifying the parameters. Any of these
    classes can be used for any of the last five template parameters
    of <tt>iterator_adaptor</tt>.
    <blockquote>
<pre>
template &lt;class Value&gt; struct value_type_is;
template &lt;class Reference&gt; struct reference_is;
template &lt;class Pointer&gt; struct pointer_is;
template &lt;class Distance&gt; struct difference_type_is;
template &lt;class Category&gt; struct iterator_category_is;
</pre>
    </blockquote>

    For example, the following adapts <tt>foo_iterator</tt> to create
    an <a href=
    "http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>
    with <tt>reference</tt> type <tt>foo</tt>, and whose other traits
    are determined according to the defaults described <a
    href="#template_parameters">above</a>.

    <blockquote>
<pre>
typedef iterator_adaptor&lt;foo_iterator, foo_policies,
  reference_is&lt;foo&gt;, iterator_category_is&lt;std::input_iterator_tag&gt;
  &gt; MyIterator;
</pre>
    </blockquote>

    
    <h3><a name="policies">The Policies Class</a></h3>

    <p>The main task in using <tt>iterator_adaptor</tt> is creating an
    appropriate <tt>Policies</tt> class. The <tt>Policies</tt> class will become
    the functional heart of the resulting iterator, supplying the core
    operations that determine its behavior. The <tt>iterator_adaptor</tt>
    template defines all of the operators required of a <a href=
    "http://www.sgi.com/tech/stl/RandomAccessIterator.html">Random Access
    Iterator</a> by dispatching to a <tt>Policies</tt> object. Your
    <tt>Policies</tt> class must implement a subset of the core iterator
    operations below corresponding to the iterator categories you want it to
    support.<br>
    <br>
    

    <table border="1" summary="iterator_adaptor Policies operations">
      <caption>
        <b>Policies Class Requirements</b><br>
        <tt><b>T</b></tt>: adapted iterator type; <tt><b>x, y</b></tt>: objects of type
        T; <tt><b>p</b></tt>: <tt>T::policies_type</tt>
         <tt><b>d</b></tt>:
        <tt>T::difference_type</tt>; <tt><b>i1</b></tt>, <tt><b>i2</b></tt>:
        <tt>T::base_type</tt>
      </caption>

      <tr>
        <th>Expression

        <th>Effects

        <th>Implements Operations

        <th>Required for Iterator Categories

      <tr>
        <td nowrap><tt>p.initialize(b)</tt>

        <td>optionally modify base iterator during iterator construction

        <td>constructors

        <td rowspan="4"><a href=
        "http://www.sgi.com/tech/stl/InputIterator.html">Input</a>/ <a href=
        "http://www.sgi.com/tech/stl/OutputIterator.html">Output</a>/ <a href=
        "http://www.sgi.com/tech/stl/ForwardIterator.html">Forward</a>/ <a
        href=
        "http://www.sgi.com/tech/stl/BidirectionalIterator.html">Bidirectional</a>/
        <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">Random&nbsp;Access</a> 

	  
      <tr>
        <td nowrap><tt>p.dereference(x)</tt>

        <td>returns an element of the iterator's <tt>reference</tt> type
        
        <td><tt>*x</tt>, <tt>x[d]</tt>


      <tr>
        <td nowrap><tt>p.equal(x, y)</tt> 

        <td>tests the iterator for equality

        <td><tt>i1&nbsp;==&nbsp;i2</tt>, <tt>i1&nbsp;!=&nbsp;i2</tt>

      <tr>
        <td nowrap><tt>p.increment(x)</tt> 

        <td>increments the iterator

        <td><tt>++p</tt>, <tt>p++</tt>

      <tr>
        <td nowrap><tt>p.decrement(x)</tt> 

        <td>decrements the iterator

        <td><tt>--x</tt>, <tt>x--</tt>

        <td><a href=
        "http://www.sgi.com/tech/stl/BidirectionalIterator.html">Bidirectional</a>/
        <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">Random&nbsp;Access</a> 

      <tr>
        <td nowrap><tt>p.distance(x, y)</tt> 

        <td>measures the distance between iterators

        <td><tt>y&nbsp;-&nbsp;x</tt>, <tt>x&nbsp;&lt;&nbsp;y</tt>

       <td rowspan="2"><a href=
         "http://www.sgi.com/tech/stl/RandomAccessIterator.html">Random
         Access</a> 

      <tr>
        <td nowrap><tt>p.advance(x, n)</tt> 

        <td>adds an integer offset to iterators

        <td>
<tt>x&nbsp;+&nbsp;d</tt>,
<tt>d&nbsp;+&nbsp;x</tt>,

<br>
<tt>x&nbsp;+=&nbsp;d</tt>,
<tt>x&nbsp;-&nbsp;d</tt>,<br>
<tt>x&nbsp;-=&nbsp;d</tt>
        
    </table>

    <p>The library also supplies a "trivial" policy class,
    <tt>default_iterator_policies</tt>, which implements all seven of the core
    operations in the usual way. If you wish to create an iterator adaptor that
    only changes a few of the base type's behaviors, then you can derive your
    new policy class from <tt>default_iterator_policies</tt> to avoid retyping
    the usual behaviors. You should also look at
    <tt>default_iterator_policies</tt> as the ``boilerplate'' for your own
    policy classes, defining functions with the same interface. This is the
    definition of <tt>default_iterator_policies</tt>:<br>
    <br>

    <blockquote>
<pre>
struct <a name="default_iterator_policies">default_iterator_policies</a>
{
    // Some of these members were defined static, but Borland got confused
    // and thought they were non-const. Also, Sun C++ does not like static
    // function templates.

    template &lt;class Base&gt;
    void initialize(Base&amp;)
        { }

    template &lt;class IteratorAdaptor&gt;
    typename IteratorAdaptor::reference dereference(const IteratorAdaptor&amp; x) const
        { return *x.base(); }

    template &lt;class IteratorAdaptor&gt;
    void increment(IteratorAdaptor&amp; x)
        { ++x.base(); }

    template &lt;class IteratorAdaptor&gt;
    void decrement(IteratorAdaptor&amp; x)
        { --x.base(); }

    template &lt;class IteratorAdaptor, class DifferenceType&gt;
    void advance(IteratorAdaptor&amp; x, DifferenceType n)
        { x.base() += n; }

    template &lt;class IteratorAdaptor1, class IteratorAdaptor2&gt;
    typename IteratorAdaptor1::difference_type
    distance(const IteratorAdaptor1&amp; x, const IteratorAdaptor2&amp; y) const
        { return y.base() - x.base(); }

    template &lt;class IteratorAdaptor1, class IteratorAdaptor2&gt;
    bool equal(const IteratorAdaptor1&amp; x, const IteratorAdaptor2&amp; y) const
        { return x.base() == y.base(); }
};
</pre></blockquote>

    <p>Template member functions are used throughout
    <tt>default_iterator_policies</tt> so that it can be employed with a wide
    range of iterators. If we had used concrete types above, we'd have tied the
    usefulness of <tt>default_iterator_policies</tt> to a particular range of
    adapted iterators. If you follow the same pattern with your
    <tt>Policies</tt> classes, you can use them to generate more specialized
    adaptors along the lines of <a href="#specialized_adaptors">those supplied by this library</a>.

    <h3><a name="additional_members">Additional Members</a></h3>
    In addition to all of the member functions required of a <a href=
    "http://www.sgi.com/tech/stl/RandomAccessIterator.html">Random Access
    Iterator</a>, the <tt>iterator_adaptor</tt> class template defines the
    following members. <br>
     <br>
     

    <table border="1" summary="additional iterator_adaptor members">
      <tr>
        <td><tt>explicit iterator_adaptor(const Base&amp;, const Policies&amp; =
        Policies())</tt>
         <br><br>
         Construct an adapted iterator from a base object and a policies
         object. As this constructor is <tt>explicit</tt>, it does not
         provide for implicit conversions from the <tt>Base</tt> type to
         the iterator adaptor.

      <tr>
        <td><tt>template &lt;class B, class V, class R, class P&gt;<br>
         iterator_adaptor(const
        iterator_adaptor&lt;B,Policies,V,R,P,Category,Distance&gt;&amp;)</tt>
        <br><br>
         This constructor allows for conversion from mutable to
        constant adapted iterators. See <a href=
        "#iterator_interactions">below</a> for more details.<br>
         Requires: <tt>B</tt> is convertible to <tt>Base</tt>.

      <tr>
        <td><tt>const base_type& base() const;</tt>
           <br><br>
         Return a const reference to the base object.

      <tr>        <td><tt>base_type& base();</tt>
         <br><br>
         Return a reference to the base object. This is to give the policies object
         access to the base object. See <a href="#policies">above</a> for policies
         iterator_adaptor interaction.<a href="#8">[8]</a>
    </table>

    <h3><a name="example">Example</a></h3>

    <p>It is often useful to automatically apply some function to the value
    returned by dereferencing an iterator. The <a href=
    "./transform_iterator.htm">transform iterator</a> makes it easy to create
    an iterator adaptor which does just that. Here we will show how easy it is
    to implement the transform iterator using the <tt>iterator_adaptor</tt>
    template.

    <p>We want to be able to adapt a range of iterators and functions, so the
    policies class will have a template parameter for the function type and it
    will have a data member of that type. We know that the function takes one
    argument and that we'll need to be able to deduce the <tt>result_type</tt>
    of the function so we can use it for the adapted iterator's
    <tt>value_type</tt>. <a href=
    "http://www.sgi.com/Technology/STL/AdaptableUnaryFunction.html">AdaptableUnaryFunction</a>
    is the <a href="../../more/generic_programming.html#concept">Concept</a>
    that fulfills those requirements.

    <p>To implement a transform iterator we will only change one of the base
    iterator's behaviors, so the <tt>transform_iterator_policies</tt> class can
    inherit the rest from <tt>default_iterator_policies</tt>. We will define the
    <tt>dereference()</tt> member function, which is used to implement
    <tt>operator*()</tt> of the adapted iterator. The implementation will
    dereference the base iterator and apply the function object. The complete
    code for <tt>transform_iterator_policies</tt> is:<br>
    <br>

<blockquote><pre>
template &lt;class AdaptableUnaryFunction&gt;
struct transform_iterator_policies : public default_iterator_policies
{
    transform_iterator_policies() { }

    transform_iterator_policies(const AdaptableUnaryFunction&amp; f)
        : m_f(f) { }
    
    template &lt;class IteratorAdaptor&gt;
    typename IteratorAdaptor::reference
    dereference(const IteratorAdaptor&amp; iter) const
        { return m_f(*iter.base()); }

    AdaptableUnaryFunction m_f;
};

</pre></blockquote>

    <p>The next step is to use the <tt>iterator_adaptor</tt> template to
    construct the transform iterator type. The nicest way to package the
    construction of the transform iterator is to create a <a href=
    "../../more/generic_programming.html#type_generator">type generator</a>.
    The first template parameter to the generator will be the type of the
    function object and the second will be the base iterator type. We use
    <tt>iterator_adaptor</tt> to define the transform iterator type as a nested
    <tt>typedef</tt> inside the <tt>transform_iterator_generator</tt> class.
    Because the function may return by-value, we must limit the
    <tt>iterator_category</tt> to <a href=
    "http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>, and
    the iterator's <tt>reference</tt> type cannot be a true reference (the
    standard allows this for input iterators), so in this case we can use few
    of <tt>iterator_adaptor</tt>'s default template arguments.<br>
    <br>


    <blockquote>
<pre>
template &lt;class AdaptableUnaryFunction, class Iterator&gt;
struct transform_iterator_generator
{
    typedef typename AdaptableUnaryFunction::result_type value_type;
public:
    typedef iterator_adaptor&lt;Iterator, 
        transform_iterator_policies&lt;AdaptableUnaryFunction&gt;,
        value_type, value_type, value_type*, std::input_iterator_tag&gt;
      type;
};
</pre>
    </blockquote>

    <p>As a finishing touch, we will create an <a href=
    "../../more/generic_programming.html#object_generator">object generator</a>
    for the transform iterator. Our object generator makes it more
    convenient to create a transform iterator.<br>
    <br>


    <blockquote>
<pre>
template &lt;class AdaptableUnaryFunction, class Iterator&gt;
typename transform_iterator_generator&lt;AdaptableUnaryFunction,Iterator&gt;::type
make_transform_iterator(Iterator base,
                        const AdaptableUnaryFunction&amp; f = AdaptableUnaryFunction())
{
    typedef typename transform_iterator_generator&lt;AdaptableUnaryFunction,
      Iterator&gt;::type result_t;
    return result_t(base, f);
}
</pre>
    </blockquote>

    <p>Here is an example that shows how to use a transform iterator to iterate
    through a range of numbers, multiplying each of them by 2 and printing the
    result to standard output.<br>
    <br>


    <blockquote>
<pre>
#include &lt;functional&gt;
#include &lt;algorithm&gt;
#include &lt;iostream&gt;
#include &lt;boost/iterator_adaptors.hpp&gt;

int main(int, char*[])
{
  int x[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
  const int N = sizeof(x)/sizeof(int);
  std::cout &lt;&lt; &quot;multiplying the array by 2:&quot; &lt;&lt; std::endl;
  std::copy(boost::make_transform_iterator(x, std::bind1st(std::multiplies&lt;int&gt;(), 2)),
      boost::make_transform_iterator(x + N, std::bind1st(std::multiplies&lt;int&gt;(), 2)),
      std::ostream_iterator&lt;int&gt;(std::cout, &quot; &quot;));
  std::cout &lt;&lt; std::endl;
  return 0;
}
</pre>
      This output is: 
<pre>
2 4 6 8 10 12 14 16
</pre>
    </blockquote>

    <h3><a name="iterator_interactions">Iterator Interactions</a></h3>

    <p>C++ allows <tt>const</tt> and non-<tt>const</tt> pointers to interact in
    the following intuitive ways:

    <ul>
      <li>a non-<tt>const</tt> pointer to <tt>T</tt> can be implicitly
      converted to a <tt>const</tt> pointer to <tt>T</tt>.

      <li><tt>const</tt> and non-<tt>const</tt> pointers to <tt>T</tt> can be
      freely mixed in comparison expressions.

      <li><tt>const</tt> and non-<tt>const</tt> pointers to <tt>T</tt> can be
      freely subtracted, in any order.
    </ul>

    Getting user-defined iterators to work together that way is nontrivial (see
    <a href="reverse_iterator.htm#interactions">here</a> for an example of where
    the C++ standard got it wrong), but <tt>iterator_adaptor</tt> can make it
    easy. The rules are as follows:

    <ul>
      <li><a name="interoperable">Adapted iterators that share the same <tt>Policies</tt>,
      <tt>Category</tt>, and <tt>Distance</tt> parameters are called
      <i>interoperable</i>.</a>

      <li>An adapted iterator can be implicitly converted to any other adapted
      iterator with which it is interoperable, so long as the <tt>Base</tt>
      type of the source iterator can be converted to the <tt>Base</tt> type of
      the target iterator.

      <li>Interoperable iterators can be freely mixed in comparison expressions
      so long as the <tt>Policies</tt> class has <tt>equal</tt> (and, for
      random access iterators, <tt>distance</tt>) members that can accept both
      <tt>Base</tt> types in either order.

      <li>Interoperable iterators can be freely mixed in subtraction
      expressions so long as the <tt>Policies</tt> class has a
      <tt>distance</tt> member that can accept both <tt>Base</tt> types in
      either order.
    </ul>

    <h4>Example</h4>
    
    <p>The <a href="projection_iterator.htm">Projection Iterator</a> adaptor is similar to the <a
href="./transform_iterator.htm">transform iterator adaptor</a> in that
its <tt>operator*()</tt> applies some function to the result of
dereferencing the base iterator and then returns the result. The
difference is that the function must return a reference to some
existing object (for example, a data member within the
<tt>value_type</tt> of the base iterator). 

    <p>
The <a
    href="projection_iterator.htm#projection_iterator_pair_generator">projection_iterator_pair_generator</a> template
    is a special two-<a href="../../more/generic_programming.html#type_generator">type generator</a> for mutable and constant versions of a
    projection iterator. It is defined as follows:
<blockquote>
<pre>
template &lt;class AdaptableUnaryFunction, class Iterator, class ConstIterator&gt;
struct projection_iterator_pair_generator {
    typedef typename AdaptableUnaryFunction::result_type value_type;
    typedef projection_iterator_policies&lt;AdaptableUnaryFunction&gt; policies;
public:
    typedef iterator_adaptor&lt;Iterator,policies,value_type&gt; iterator;
    typedef iterator_adaptor&lt;ConstIterator,policies,value_type,
        const value_type&amp;,const value_type*&gt; const_iterator;
};
</pre>
</blockquote>

<p>It is assumed that the <tt>Iterator</tt> and <tt>ConstIterator</tt> arguments are corresponding mutable
and constant iterators. <ul>
<li>
Clearly, then, the
<tt>projection_iterator_pair_generator</tt>'s <tt>iterator</tt> and
<tt>const_iterator</tt> are <a href="#interoperable">interoperable</a>, since
they share the same <tt>Policies</tt> and since <tt>Category</tt> and
<tt>Distance</tt> as supplied by <tt>std::iterator_traits</tt> through the
<a href="#template_parameters">default template parameters</a> to
<tt>iterator_adaptor</tt> should be the same.

<li>Since <tt>Iterator</tt> can presumably be converted to
<tt>ConstIterator</tt>, the projection <tt>iterator</tt> will be convertible to
the projection <tt>const_iterator</tt>.

<li> Since <tt>projection_iterator_policies</tt> implements only the
<tt>dereference</tt> operation, and inherits all other behaviors from
<tt><a
href="#default_iterator_policies">default_iterator_policies</a></tt>,
which has fully-templatized <tt>equal</tt> and <tt>distance</tt>
operations, the <tt>iterator</tt> and <tt>const_iterator</tt> can be
freely mixed in comparison and subtraction expressions.

</ul>

    <h3><a name="challenge">Challenge</a></h3>

    <p>There is an unlimited number of ways the <tt>iterator_adaptors</tt>
    class can be used to create iterators. One interesting exercise would be to
    re-implement the iterators of <tt>std::list</tt> and <tt>slist</tt>
    using <tt>iterator_adaptors</tt>, where the adapted <tt>Iterator</tt> types
    would be node pointers.

    <h3><a name="concept_model">Concept Model</a></h3>
    Depending on the <tt>Base</tt> and <tt>Policies</tt> template parameters,
    an <tt>iterator_adaptor</tt> can be a <a href=
    "http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>, <a
    href="http://www.sgi.com/tech/stl/ForwardIterator.html">Forward
    Iterator</a>, <a href=
    "http://www.sgi.com/tech/stl/BidirectionalIterator.html">Bidirectional
    Iterator</a>, or <a href=
    "http://www.sgi.com/tech/stl/RandomAccessIterator.html">Random Access
    Iterator</a>. 

    <h3><a name="declaration_synopsis">Declaration Synopsis</a></h3>
<pre>
template &lt;class Base, class Policies, 
    class Value = typename std::iterator_traits&lt;Base&gt;::value_type,
    class Reference = <i>...(see below)</i>,
    class Pointer = <i>...(see below)</i>,
    class Category = typename std::iterator_traits&lt;Base&gt;::iterator_category,
    class Distance = typename std::iterator_traits&lt;Base&gt;::difference_type
         &gt;
struct iterator_adaptor
{
    typedef Distance difference_type;
    typedef typename boost::remove_const&lt;Value&gt;::type value_type;
    typedef Pointer pointer;
    typedef Reference reference;
    typedef Category iterator_category;
    typedef Base base_type;
    typedef Policies policies_type;

    iterator_adaptor();
    explicit iterator_adaptor(const Base&amp;, const Policies&amp; = Policies());

    base_type&       base();
    const base_type& base() const;

    template &lt;class B, class V, class R, class P&gt;
    iterator_adaptor(
        const iterator_adaptor&lt;B,Policies,V,R,P,Category,Distance&gt;&amp;);

    reference operator*() const; <a href="#6">[6]</a>
    <i>operator_arrow_result_type</i> operator-&gt;() const; <a href=
"#3">[3]</a>
    <i>value_type</i> operator[](difference_type n) const; <a href="#3">[4]</a>, <a href="#6">[6]</a>

    iterator_adaptor&amp; operator++();
    iterator_adaptor&amp; operator++(int);
    iterator_adaptor&amp; operator--();
    iterator_adaptor&amp; operator--(int);

    iterator_adaptor&amp; operator+=(difference_type n);
    iterator_adaptor&amp; operator-=(difference_type n);

    iterator_adaptor&amp; operator-(Distance x) const;
};

template &lt;class B, class P, class V, class R, class Ptr, 
    class C, class D1, class D2&gt;
iterator_adaptor&lt;B,P,V,R,Ptr,C,D1&gt;
operator+(iterator_adaptor&lt;B,P,V,R,Ptr,C,D1&gt;, D2);

template &lt;class B, class P, class V, class R, class Ptr,
    class C, class D1, class D2&gt;
iterator_adaptor&lt;B,P,V,R,P,C,D1&gt;
operator+(D2, iterator_adaptor&lt;B,P,V,R,Ptr,C,D1&gt; p);

template &lt;class B1, class B2, class P, class V1, class V2,
    class R1, class R2, class P1, class P2, class C, class D&gt;
Distance operator-(const iterator_adaptor&lt;B1,P,V1,R1,P1,C,D&gt;&amp;, 
                   const iterator_adaptor&lt;B2,P,V2,R2,P2,C,D&gt;&amp;);

template &lt;class B1, class B2, class P, class V1, class V2,
    class R1, class R2, class P1, class P2, class C, class D&gt;
bool operator==(const iterator_adaptor&lt;B1,P,V1,R1,P1,C,D&gt;&amp;, 
                const iterator_adaptor&lt;B2,P,V2,R2,P2,C,D&gt;&amp;);

// and similarly for operators !=, &lt;, &lt;=, &gt;=, &gt;
</pre>

    <h3><a name="notes">Notes</a></h3>

    <p><a name="1">[1]</a> The standard specifies that the <tt>value_type</tt>
    of <tt>const</tt> iterators to <tt>T</tt> (e.g. <tt>const T*</tt>) is
    <tt><i>non-</i>const T</tt>, while the <tt>pointer</tt> and
    <tt>reference</tt> types for all <a href=
    "http://www.sgi.com/tech/stl/ForwardIterator.html">Forward Iterators</a> are
    <tt>const T*</tt> and <tt>const T&amp;</tt>, respectively. Stripping the
    <tt>const</tt>-ness of <tt>Value</tt> allows you to easily make a constant
    iterator by supplying a <tt>const</tt> type for <tt>Value</tt>, and allowing
    the defaults for the <tt>Pointer</tt> and <tt>Reference</tt> parameters to
    take effect. Although compilers that don't support partial specialization
    won't strip <tt>const</tt> for you, having a <tt>const value_type</tt> is
    often harmless in practice.

    <p><a name="2">[2]</a> If your compiler does not support partial
    specialization and the base iterator is a builtin pointer type, you
    will not be able to use the default for <tt>Value</tt> and will have to
    specify this type explicitly.

    <p><a name="3">[3]</a> The result type for the <tt>operator-&gt;()</tt>
    depends on the category and value type of the iterator and is somewhat
    complicated to describe. But be assured, it works in a stardard conforming
    fashion, providing access to members of the objects pointed to by the
    iterator.

    <p><a name="4">[4]</a> The result type of <tt>operator[]()</tt> is
    <tt>value_type</tt> instead of <tt>reference</tt> as might be expected.
    There are two reasons for this choice. First, the C++ standard only
    requires that the return type of an arbitrary <a href=
    "http://www.sgi.com/tech/stl/RandomAccessIterator.html">Random Access
    Iterator</a>'s <tt>operator[]</tt>be ``convertible to T'' (Table 76), so
    when adapting an arbitrary base iterator we may not have a reference to
    return. Second, and more importantly, for certain kinds of iterators,
    returning a reference could cause serious memory problems due to the
    reference being bound to a temporary object whose lifetime ends inside of
    the <tt>operator[]</tt>.

    <p><a name="5">[5]</a>
    The <tt>value_type</tt> of an iterator may not be
    an abstract base class, however many common uses of iterators
    never need the <tt>value_type</tt>, only the <tt>reference</tt> type.
    If you wish to create such an iterator adaptor, use a dummy
    type such as <tt>char</tt> for the <tt>Value</tt> parameter,
    and use a reference to your abstract base class for
    the <tt>Reference</tt> parameter. Note that such an iterator
    does not fulfill the C++ standards requirements for a
    <a href= "http://www.sgi.com/tech/stl/ForwardIterator.html">
    Forward Iterator</a>, so you will need to use a less restrictive
    iterator category such as <tt>std::input_iterator_tag</tt>.

    <p><a name="6">[6]</a>
    There is a common misconception that an iterator should have two
    versions of <tt>operator*</tt> and of <tt>operator[]</tt>, one
    version that is a <tt>const</tt> member function and one version
    that is non-<tt>const</tt>. Perhaps the source of this
    misconception is that containers typically have const and
    non-const versions of many of their member functions.  Iterators,
    however, are different. A particular iterator type can be either
    <i>mutable</i> or <i>constant</i> (but not both).  One can assign
    to and change the object pointed to by a mutable iterator whereas a
    constant iterator returns constant objects when dereferenced. Whether
    the iterator object itself is <tt>const</tt> has nothing to do with
    whether the iterator is mutable or constant.  This is analogous to
    the way built-in pointer types behave.  For example, one can
    modify objects pointed to by a <tt>const</tt> pointer
<pre>
    int* const x = new int;
    int i = 3;
    *x = i;
</pre>
    but one cannot modify objects pointed to by a pointer
    to <tt>const</tt>
<pre>
    int const* x = new int;
    int i = 3;
    *x = i;
</pre>

    <p><a name="7">[7]</a>
    If you are using a compiler that does not have a version of
    <tt>std::iterator_traits</tt> that works for pointers (i.e., if your
    compiler does not support partial specialization) then if the
    <tt>Base</tt> type is a const pointer, then the correct defaults
    for the <tt>reference</tt> and <tt>pointer</tt> types can not be
    deduced. You must specify these types explicitly.
    <p><a name="8">[8]</a>
    Exposing the base object might be considered as being dangerous.
    A possible fix would require compiler support for template friends. 
    As this is not widely available today, the base object remains exposed for now.

    <hr>

    <p>Revised 
    <!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %b %Y" startspan -->30 Nov 2001<!--webbot bot="Timestamp" endspan i-checksum="15239" -->


    <p>&copy; Copyright Dave Abrahams and Jeremy Siek 2001. Permission to copy,
    use, modify, sell and distribute this document is granted provided this
    copyright notice appears in all copies. This document is provided "as is"
    without express or implied warranty, and with no claim as to its
    suitability for any purpose. 

</body>

    <!--  LocalWords:  HTML html charset alt gif abrahams htm const iterator
        incrementable david abrahams
         -->
     
    <!--  LocalWords:  jeremy siek mishandled interoperable typename struct Iter iter src
         -->
     
    <!--  LocalWords:  int bool ForwardIterator BidirectionalIterator BaseIterator
         -->
     
    <!--  LocalWords:  RandomAccessIterator DifferenceType AdaptableUnaryFunction
         -->
     
    <!--  LocalWords:  iostream hpp sizeof InputIterator constness ConstIterator
         David Abrahams
         -->
<!--  LocalWords:  Iterators dereferenced
 -->
</html>