# Header boost/iterator_adaptors.hpp and boost/integer_range.hpp

The file `boost/iterator_adaptors.hpp` includes the main `iterator_adaptors` class and several other classes for constructing commonly used iterator adaptors.

- `iterator_adaptors`.
- `iterator_adaptor`.
- `transform_iterator`
- `Indirect Iterator Adaptors`
- `Projection Iterator Adaptors`
- `reverse_iterators`

The file `boost/integer_range.hpp` includes a class that uses iterator adaptors to create an iterator that increments over a range of integers. The file also includes a "container" type that creates a container-interface for the range of integers.

- `integer_range`

Dave Abrahams started the library, coming up with the idea to use policy classes and how to handle the const/non-const iterator interactions. He also contributed the `indirect_iterators` and `reverse_iterators` classes.
Jeremy Siek contributed `transform_iterator`, `integer_range`, and this documentation.
John Potter contributed `indirect_iterator` and `projection_iterator` and made some simplifications to `iterator_adaptor`.

### The Iterator Adaptors Class

Implementing standard conforming iterators is a non-trivial task. There are some fine-points such as iterator/const_iterator interactions and there are the myriad of operators that should be implemented but are easily forgotten such as `operator->()`. The purpose of the `iterator_adaptors` class is to make it easier to implement an iterator class, and even easier to extend and adapt existing iterator types. The `iterator_adaptors` class itself is not an adaptor class but a type generator. It generates a pair of adaptor classes, one class for the mutable iterator and one class for the const iterator. The definition of the `iterator_adaptors` class is as follows:

    template <class Iterator,
              class ConstIterator,
              class Traits = std::iterator_traits<Iterator>,
              class ConstTraits = std::iterator_traits<ConstIterator>,
              class Policies = default_iterator_policies>
    struct iterator_adaptors
    {
      typedef ... iterator;
      typedef ... const_iterator;
    };

The `Iterator` and `ConstIterator` template parameters are the iterator types that you want to adapt. The `Traits` and `ConstTraits` must be iterator traits classes. The traits parameters default to the specialization of the `std::iterator_traits` class for the adapted iterators. If you want the traits for your new iterator adaptor (`value_type`, `iterator_category`, etc.) to be the same as the adapted iterator then use the default, otherwise create your own traits classes and pass them in [1].

The `Policies` class that you pass in will become the heart of the iterator adaptor, supplying the core iterator operations that will determine how your new adaptor class will behave. The core iterator operations are:

- `dereference` - returns an element of the iterator's `reference` type
- `equal` - tests the iterator for equality
- `increment` - increments the iterator
- `decrement` - decrements bidirectional and random-access iterators
- `less` - imposes a strict weak ordering relation on random-access iterators
- `distance` - measures the distance between random-access iterators
- `advance` - adds an integer offset to random-access iterators

The `Policies` class must implement three, four, or seven of the core iterator operations depending on whether you wish the new iterator adaptor class to be a ForwardIterator, BidirectionalIterator, or RandomAccessIterator. The `iterator_category` type of the traits class you pass in must match the category of iterator that you want to create. The default policy class, `default_iterator_policies`, implements all 7 of the core operations in the usual way. If you wish to create an iterator adaptor that only changes a few of the iterator's behaviors, then you can have your new policy class inherit from `default_iterator_policies` to avoid retyping the usual behaviours. You should also look at `default_iterator_policies` as the "boiler-plate" for your own policy classes. The following is definition of the `default_iterator_policies` class:

    struct default_iterator_policies
    {
      // required for a ForwardIterator
      template <class Reference, class Iterator>
      Reference dereference(type<Reference>, const Iterator& x) const
        { return *x; }

      template <class Iterator>
      static void increment(Iterator& x)
        { ++x; }

      template <class Iterator1, class Iterator2>
      bool equal(Iterator1& x, Iterator2& y) const
        { return x == y; }

      // required for a BidirectionalIterator
      template <class Iterator>
      static void decrement(Iterator& x)
        { --x; }

      // required for a RandomAccessIterator
      template <class Iterator, class DifferenceType>
      static void advance(Iterator& x, DifferenceType n)
        { x += n; }

      template <class Difference, class Iterator1, class Iterator2>
      Difference distance(type<Difference>, Iterator1& x, Iterator2& y) const
        { return y - x; }

      template <class Iterator1, class Iterator2>
      bool less(Iterator1& x, Iterator2& y) const
        { return x < y; }
    };

The generated iterator adaptor types will have the following constructors.

    iterator(const Iterator& i, const Policies& p = Policies())

    const_iterator(const ConstIterator& i, const Policies& p = Policies())

### The Iterator Adaptor Class

This is the class used inside of the `iterator_adaptors` type generator. Use this class directly (instead of using `iterator_adaptors`) when you are interested in creating only one of the iterator types (either const or non-const) or when there is no difference between the const and non-const versions of the iterator type (often this is because there is only a const (read-only) version of the iterator, as is the case for `std::set`'s iterators).

    template <class Iterator,
              class Policies = default_iterator_policies,
              class Traits = std::iterator_traits<Iterator> >
    struct iterator_adaptor;

Next we will look at some iterator adaptors that are examples of how to use the iterator adaptors class, and that are useful iterator adaptors in their own right.

### The Transform Iterator Class

It is often useful to automatically apply some function to the value returned by dereferencing (`operator*()`) an iterator. The `transform_iterators` class makes it easy to create an iterator adaptor that does just that. First let us consider what the `Policies` class for the transform iterator should look like. We are only changing one of the iterator behaviours, so we will inherit from `default_iterator_policies`. In addition, we will need a function object to apply, so we will have a template parameter and a data member for the function object. The function will take one argument (the dereferenced value) and we will need to know the `result_type` of the function, so AdaptableUnaryFunction is the corrent concept to choose for the function object type. Now for the heart of our iterator adaptor, we implement the `dereference` method, applying the function object to `*i`. The `type<Reference>` class is there to tell you what the reference type of the iterator is, which is handy when writing generic iterator adaptors such as this one [2].

      template <class AdaptableUnaryFunction>
      struct transform_iterator_policies : public default_iterator_policies
      {
        transform_iterator_policies() { }
        transform_iterator_policies(const AdaptableUnaryFunction& f) : m_f(f) { }

        template <class Reference, class Iterator>
        Reference dereference(type<Reference>, const Iterator& i) const
          { return m_f(*i); }

        AdaptableUnaryFunction m_f;
      };

Next we need to create the traits class for our new iterator. In some situations you may need to create a separate traits class for the const and non-const iterator types, but here a single traits class will do. The `value_type` and `reference` type of our transform iterator will be the `result_type` of the function object. The `difference_type` and `iterator_category` will be the same as the adapted iterator.

      template <class AdaptableUnaryFunction, class IteratorTraits>
      struct transform_iterator_traits {
        typedef typename AdaptableUnaryFunction::result_type value_type;
        typedef value_type reference;
        typedef value_type* pointer;
        typedef typename IteratorTraits::difference_type difference_type;
        typedef typename IteratorTraits::iterator_category iterator_category;
      };

The final step is to use the `iterator_adaptor` class to construct our transform iterator. We will use the single iterator adaptor version because we will not need to create both a mutable and const version of the transform iterator. The transform iterator is inherently a read-only iterator. The nicest way to package up our new transform iterator is to create a type generator similar to `iterator_adaptor`. The first template parameter will be the type of the function object. The second parameter will be the adapted iterator type. The third parameter is the trait class for the adapted iterator. Inside the `transform_iterators` class we use the `transform_iterator_traits` class defined above to create the traits class for the new transform iterator. We then use the `iterator_adaptor` class to extract the generated iterator adaptor type.

    template <class AdaptableUnaryFunction,
              class Iterator,
              class Traits = std::iterator_traits<Iterator>
             >
    struct transform_iterator
    {
      typedef transform_iterator_traits<AdaptableUnaryFunction,Traits>
        TransTraits;
      typedef iterator_adaptor<Iterator, TransTraits,
        transform_iterator_policies<AdaptableUnaryFunction> >::type type;
    };

The following is a simple example of how to use the `transform_iterators` class to iterate through a range of numbers, multiplying each of them by 2 when they are dereferenced.

    #include <functional>
    #include <iostream>
    #include <boost/iterator_adaptors.hpp>

    int
    main(int, char*[])
    {
      int x[] = { 1, 2, 3, 4, 5, 6, 7, 8 };

      typedef std::binder1st< std::multiplies<int> > Function;
      typedef boost::transform_iterator<Function, int*,
        boost::iterator<std::random_access_iterator_tag, int>
      >::type doubling_iterator;

      doubling_iterator i(x, std::bind1st(std::multiplies<int>(), 2)),
        i_end(x + sizeof(x)/sizeof(int), std::bind1st(std::multiplies<int>(), 2));

      std::cout << "multiplying the array by 2:" << std::endl;
      while (i != i_end)
        std::cout << *i++ << " ";
      std::cout << std::endl;

      return 0;
    }

### The Indirect Iterator Adaptors

It is not all that uncommon to create data structures that consist of pointers to pointers. For such a structure it might be nice to have an iterator that applies a double-dereference inside the `operator*()`. The implementation of this is similar to the `transform_iterators`[3]. When talking about a data structure of pointers to pointers (or more generally, iterators to iterators), we call the first level iterators the outer iterators and the second level iterators the inner iterators. For example, if the outer iterator type is `T**` then the inner iterator type is `T*`. To implement the indirect adaptors, we first create a policies class which does a double-dereference in the `dereference()` method.

    struct indirect_iterator_policies : public default_iterator_policies
    {
        template <class Reference, class Iterator>
        Reference dereference(type<Reference>, const Iterator& x) const
            { return **x; }
    };

We then create a traits class, including a template parameter for both the inner and outer iterators and traits classes. The `difference_type` and `iterator_category` come from the outer iterator, while the `value_type`, `pointer`, and `reference` types come from the inner iterator.

    template <class OuterIterator, class InnerIterator,
              class OuterTraits = std::iterator_traits<OuterIterator>,
              class InnerTraits = std::iterator_traits<InnerIterator>
             >
    struct indirect_traits
    {
        typedef typename OuterTraits::difference_type difference_type;
        typedef typename InnerTraits::value_type value_type;
        typedef typename InnerTraits::pointer pointer;
        typedef typename InnerTraits::reference reference;
        typedef typename OuterTraits::iterator_category iterator_category;
    };

Lastly we wrap this up in two type generators: `indirect_iterator` for creating a single indirect iterator type, and `indirect_iterators` for creating an const/non-const pair of indirect iterator types. We use the `iterator_adaptor` and `iterator_adaptors` classes here to do most of the work.

    template <class OuterIterator, class InnerIterator,
              class OuterTraits = std::iterator_traits<OuterIterator>,
              class InnerTraits = std::iterator_traits<InnerIterator>
             >
    struct indirect_iterator
    {
        typedef iterator_adaptor<OuterIterator,
            indirect_iterator_policies,
            indirect_traits<OuterIterator, InnerIterator,
                            OuterTraits, InnerTraits>
        > type;
    };

    template <class OuterIterator,      // Mutable or Immutable, does not matter
              class InnerIterator,      // Mutable
              class ConstInnerIterator, // Immutable
              class OuterTraits = std::iterator_traits<OuterIterator>,
              class InnerTraits = std::iterator_traits<InnerIterator>,
              class ConstInnerTraits = std::iterator_traits<ConstInnerIterator>
             >
    struct indirect_iterators
    {
        typedef iterator_adaptors<OuterIterator, OuterIterator,
            indirect_traits<OuterIterator, InnerIterator,
                            OuterTraits, InnerTraits>,
            indirect_traits<OuterIterator, ConstInnerIterator,
                            OuterTraits, ConstInnerTraits>,
            indirect_iterator_policies
            > Adaptors;
        typedef typename Adaptors::iterator iterator;
        typedef typename Adaptors::const_iterator const_iterator;
    };

### The Projection Iterator Adaptors

The projection iterator adaptor is very similar to the transform iterator, except for a subtle difference in the return type: the tranform iterator returns the result of the unary function by value, whereas the projection iterator returns the result by reference. Therefore, these two adaptors cater to different kinds of unary functions. Transform iterator caters to functions that create new objects, whereas projection iterator caters to a function that somehow obtains a reference to an object that already exists. An example of a unary function that is suitable for use with the projection adaptor is `select1st_`:

    template <class Pair>
    struct select1st_
      : public std::unary_function<Pair, typename Pair::first_type>
    {
      const typename Pair::first_type& operator()(const Pair& x) const {
        return x.first;
      }
      typename Pair::first_type& operator()(Pair& x) const {
        return x.first;
      }
    };

The implementation of projection iterator is as follows. First, the policies class is the same as the transform iterator's policies class.

    template <class AdaptableUnaryFunction>
    struct projection_iterator_policies : public default_iterator_policies
    {
        projection_iterator_policies() { }
        projection_iterator_policies(const AdaptableUnaryFunction& f) : m_f(f) { }

        template <class Reference, class Iterator>
        Reference dereference (type<Reference>, Iterator const& iter) const {
            return m_f(*iter);
        }

        AdaptableUnaryFunction m_f;
    };

Next we have two traits classes. We use `value_type&` for the reference type of the mutable projection iterator, and `const value_type&` for the immutable projection iterator.

    template <class AdaptableUnaryFunction, class Traits>
    struct projection_iterator_traits {
        typedef typename AdaptableUnaryFunction::result_type value_type;
        typedef value_type& reference;
        typedef value_type* pointer;
        typedef typename Traits::difference_type difference_type;
        typedef typename Traits::iterator_category iterator_category;
    };

    template <class AdaptableUnaryFunction, class Traits>
    struct const_projection_iterator_traits {
        typedef typename AdaptableUnaryFunction::result_type value_type;
        typedef value_type const& reference;
        typedef value_type const* pointer;
        typedef typename Traits::difference_type difference_type;
        typedef typename Traits::iterator_category iterator_category;
    };

And to finish up, we create three generator classes that use `iterator_adaptor` to create the projection iterator types. The class `projection_iterator` creates a mutable projection iterator type. The class `const_projection_iterator` creates an immutable projection iterator type, and `projection_iterators` creates both mutable and immutable projection iterator types.

    template <class AdaptableUnaryFunction, class Iterator,
              class Traits = std::iterator_traits<Iterator>
             >
    struct projection_iterator {
        typedef projection_iterator_traits<AdaptableUnaryFunction, Traits>
                Projection_Traits;
        typedef iterator_adaptor<Iterator,
                projection_iterator_policies<AdaptableUnaryFunction>,
                Projection_Traits> type;
    };

    template <class AdaptableUnaryFunction, class Iterator,
              class Traits = std::iterator_traits<Iterator>
             >
    struct const_projection_iterator {
        typedef const_projection_iterator_traits<AdaptableUnaryFunction,
                Traits> Projection_Traits;
        typedef iterator_adaptor<Iterator,
                projection_iterator_policies<AdaptableUnaryFunction>,
                Projection_Traits> type;
    };

    template <class AdaptableUnaryFunction, class Iterator, class ConstIterator,
              class Traits = std::iterator_traits<Iterator>,
              class ConstTraits = std::iterator_traits<ConstIterator>
             >
    struct projection_iterators {
        typedef projection_iterator_traits<AdaptableUnaryFunction, Traits>
                Projection_Traits;
        typedef const_projection_iterator_traits<AdaptableUnaryFunction,
                ConstTraits> Const_Projection_Traits;
        typedef iterator_adaptors<Iterator, ConstIterator,
                Projection_Traits, Const_Projection_Traits,
                projection_iterator_policies<AdaptableUnaryFunction> > Adaptors;
        typedef typename Adaptors::iterator iterator;
        typedef typename Adaptors::const_iterator const_iterator;
    };

### The Reverse Iterators Class

Yes, there is already a `reverse_iterator` adaptor class defined in the C++ Standard, but using the `iterator_adaptors` class we can re-implement this classic adaptor in a more succinct and elegant fashion. Also, this makes for a good example of using `iterator_adaptors` that is in familiar territory.

The first step is to create the `Policies` class. As in the `std::reverse_iterator` class, we need to flip all the operations of the iterator. Increment will become decrement, advancing by `n` will become retreating by `n`, etc.

    struct reverse_iterator_policies
    {
      template <class Reference, class Iterator>
      Reference dereference(type<Reference>, const Iterator& x) const
        { return *boost::prior(x); }
        // this is equivalent to { Iterator tmp = x; return *--tmp; }

      template <class Iterator>
      void increment(Iterator& x) const
        { --x; }

      template <class Iterator>
      void decrement(Iterator& x) const
        { ++x; }

      template <class Iterator, class DifferenceType>
      void advance(Iterator& x, DifferenceType n) const
        { x -= n; }

      template <class Difference, class Iterator1, class Iterator2>
      Difference distance(type<Difference>, Iterator1& x, Iterator2& y) const
        { return x - y; }

      template <class Iterator1, class Iterator2>
      bool equal(Iterator1& x, Iterator2& y) const
        { return x == y; }

      template <class Iterator1, class Iterator2>
      bool less(Iterator1& x, Iterator2& y) const
        { return y < x; }
    };

Since the traits of the reverse iterator adaptor will be the same as the adapted iterator's traits, we do not need to create new traits classes as was the case for `transform_iterator`. We can skip to the final stage of creating a type generator class for our reverse iterators using the `iterator_adaptor` class.

    template <class Iterator, class ConstIterator,
              class Traits = std::iterator_traits<Iterator>,
              class ConstTraits = std::iterator_traits<ConstIterator>
             >
    struct reverse_iterators
    {
      typedef iterator_adaptors<Iterator,ConstIterator,Traits,ConstTraits,
        reverse_iterator_policies> Adaptor;
      typedef typename Adaptor::iterator iterator;
      typedef typename Adaptor::const_iterator const_iterator;
    };

A typical use of the `reverse_iterators` class is in user-defined container types. You can use the `reverse_iterators` class to generate the reverse iterators for your container.

    class my_container {
      ...
      typedef ... iterator;
      typedef ... const_iterator;

      typedef reverse_iterators<iterator, const_iterator> RevIters;
      typedef typename RevIters::iterator reverse_iterator;
      typedef typename RevIters::const_iterator const_reverse_iterator;
      ...
    };

### The Integer Range Class

The `iterator_adaptors` class can not only be used for adapting iterators, but it can also be used to take a non-iterator type and use it to build an iterator. An especially simple example of this is turning an integer type into an iterator, a counting iterator. The builtin integer types of C++ are almost iterators. They have `operator++()`, `operator--()`, etc. The one operator they are lacking is the `operator*()`, which we will want to simply return the current value of the integer. The following few lines of code implement the policy and traits class for the counting iterator.

    template <class IntegerType>
    struct counting_iterator_policies : public default_iterator_policies
    {
      IntegerType dereference(type<IntegerType>, const IntegerType& i) const
        { return i; }
    };
    template <class IntegerType>
    struct counting_iterator_traits {
      typedef IntegerType value_type;
      typedef IntegerType reference;
      typedef value_type* pointer;
      typedef std::ptrdiff_t difference_type;
      typedef std::random_access_iterator_tag iterator_category;
    };

Typically we will want to count the integers in some range, so a nice interface would be to have a fake container that represents the range of integers. The following is the definition of such a class called `integer_range`.

    template <class IntegerType>
    struct integer_range {
      typedef typename iterator_adaptor<IntegerType,
                               counting_iterator_traits<IntegerType>,
                               counting_iterator_policies >::type iterator;
      typedef iterator const_iterator;
      typedef IntegerType value_type;
      typedef std::ptrdiff_t difference_type;
      typedef IntegerType reference;
      typedef IntegerType* pointer;
      typedef IntegerType size_type;

      integer_range(IntegerType start, IntegerType finish)
        : m_start(start), m_finish(finish) { }

      iterator begin() const { return iterator(m_start); }
      iterator end() const { return iterator(m_finish); }
      size_type size() const { return m_finish - m_start; }
      bool empty() const { return m_finish == m_start; }
      void swap(integer_range& x) {
        std::swap(m_start, x.m_start);
        std::swap(m_finish, x.m_finish);
      }
    protected:
      IntegerType m_start, m_finish;
    };

The following is an example of how to use the `integer_range` class to count from 0 to 4.

    boost::integer_range<int> r(0,5);

    cout << "counting to from 0 to 4:" << endl;
    std::copy(r.begin(), r.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

### Challenge

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

### Notes

[1] If your compiler does not support partial specialization and hence does not have a working `std::iterator_traits` class, you will not be able to use the defaults and will need to supply your own `Traits` and `ConstTraits` classes.

[2] The reference type could also be obtained from `std::iterator_traits`, but that is not portable on compilers that do not support partial specialization.

[3] It would have been more elegant to implement `indirect_iterators` using `transform_iterators`, but for subtle reasons that would require the use of `boost::remove_cv` which is not portable.

### Implementation Notes

The code is somewhat complicated because there are three iterator adaptor class: `forward_iterator_adaptor`, `bidirectional_iterator_adaptor`, and `random_access_iterator_adaptor`. The alternative would be to just have one iterator adaptor equivalent to the `random_access_iterator_adaptor`. The reason for going with the three adaptors is that according to 14.5.3p5 in the C++ Standard, friend functions defined inside a template class body are instantiated when the template class is instantiated. This means that if we only used the one iterator adaptor, then if the adapted iterator did not meet all of the requirements for a RandomAccessIterator then a compiler error should occur. Many current compilers in fact do not instantiate the friend functions unless used, so we could get away with the one iterator adaptor in most cases. However, out of respect for the standard this implementation uses the three adaptors.

Revised 10 Feb 2001

© Copyright Jeremy Siek 2000. 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.