ceph/src/boost/libs/iterator/doc/iterator_adaptor_tutorial.rst

   1 .. Copyright David Abrahams 2004. Use, modification and distribution is
   2 .. subject to the Boost Software License, Version 1.0. (See accompanying
   3 .. file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   4
   5 In this section we'll further refine the ``node_iter`` class
   6 template we developed in the |fac_tut|_.  If you haven't already
   7 read that material, you should go back now and check it out because
   8 we're going to pick up right where it left off.
   9
  10 .. |fac_tut| replace:: ``iterator_facade`` tutorial
  11 .. _fac_tut: iterator_facade.html#tutorial-example
  12
  13 .. sidebar:: ``node_base*`` really *is* an iterator
  14
  15    It's not really a very interesting iterator, since ``node_base``
  16    is an abstract class: a pointer to a ``node_base`` just points
  17    at some base subobject of an instance of some other class, and
  18    incrementing a ``node_base*`` moves it past this base subobject
  19    to who-knows-where?  The most we can do with that incremented
  20    position is to compare another ``node_base*`` to it.  In other
  21    words, the original iterator traverses a one-element array.
  22
  23 You probably didn't think of it this way, but the ``node_base*``
  24 object that underlies ``node_iterator`` is itself an iterator,
  25 just like all other pointers.  If we examine that pointer closely
  26 from an iterator perspective, we can see that it has much in common
  27 with the ``node_iterator`` we're building.  First, they share most
  28 of the same associated types (``value_type``, ``reference``,
  29 ``pointer``, and ``difference_type``).  Second, even some of the
  30 core functionality is the same: ``operator*`` and ``operator==`` on
  31 the ``node_iterator`` return the result of invoking the same
  32 operations on the underlying pointer, via the ``node_iterator``\ 's
  33 |dereference_and_equal|_).  The only real behavioral difference
  34 between ``node_base*`` and ``node_iterator`` can be observed when
  35 they are incremented: ``node_iterator`` follows the
  36 ``m_next`` pointer, while ``node_base*`` just applies an address offset.
  37
  38 .. |dereference_and_equal| replace:: ``dereference`` and ``equal`` member functions
  39 .. _dereference_and_equal: iterator_facade.html#implementing-the-core-operations
  40
  41 It turns out that the pattern of building an iterator on another
  42 iterator-like type (the ``Base`` [#base]_ type) while modifying
  43 just a few aspects of the underlying type's behavior is an
  44 extremely common one, and it's the pattern addressed by
  45 ``iterator_adaptor``.  Using ``iterator_adaptor`` is very much like
  46 using ``iterator_facade``, but because iterator_adaptor tries to
  47 mimic as much of the ``Base`` type's behavior as possible, we
  48 neither have to supply a ``Value`` argument, nor implement any core
  49 behaviors other than ``increment``.  The implementation of
  50 ``node_iter`` is thus reduced to::
  51
  52   template <class Value>
  53   class node_iter
  54     : public boost::iterator_adaptor<
  55           node_iter<Value>                // Derived
  56         , Value*                          // Base
  57         , boost::use_default              // Value
  58         , boost::forward_traversal_tag    // CategoryOrTraversal
  59       >
  60   {
  61    private:
  62       struct enabler {};  // a private type avoids misuse
  63
  64    public:
  65       node_iter()
  66         : node_iter::iterator_adaptor_(0) {}
  67
  68       explicit node_iter(Value* p)
  69         : node_iter::iterator_adaptor_(p) {}
  70
  71       template <class OtherValue>
  72       node_iter(
  73           node_iter<OtherValue> const& other
  74         , typename boost::enable_if<
  75               boost::is_convertible<OtherValue*,Value*>
  76             , enabler
  77           >::type = enabler()
  78       )
  79         : node_iter::iterator_adaptor_(other.base()) {}
  80
  81    private:
  82       friend class boost::iterator_core_access;
  83       void increment() { this->base_reference() = this->base()->next(); }
  84   };
  85
  86 Note the use of ``node_iter::iterator_adaptor_`` here: because
  87 ``iterator_adaptor`` defines a nested ``iterator_adaptor_`` type
  88 that refers to itself, that gives us a convenient way to refer to
  89 the complicated base class type of ``node_iter<Value>``. [Note:
  90 this technique is known not to work with Borland C++ 5.6.4 and
  91 Metrowerks CodeWarrior versions prior to 9.0]
  92
  93 You can see an example program that exercises this version of the
  94 node iterators `here`__.
  95
  96 __ ../example/node_iterator3.cpp
  97
  98 In the case of ``node_iter``, it's not very compelling to pass
  99 ``boost::use_default`` as ``iterator_adaptor``\ 's ``Value``
 100 argument; we could have just passed ``node_iter``\ 's ``Value``
 101 along to ``iterator_adaptor``, and that'd even be shorter!  Most
 102 iterator class templates built with ``iterator_adaptor`` are
 103 parameterized on another iterator type, rather than on its
 104 ``value_type``.  For example, ``boost::reverse_iterator`` takes an
 105 iterator type argument and reverses its direction of traversal,
 106 since the original iterator and the reversed one have all the same
 107 associated types, ``iterator_adaptor``\ 's delegation of default
 108 types to its ``Base`` saves the implementor of
 109 ``boost::reverse_iterator`` from writing:
 110
 111 .. parsed-literal::
 112
 113    std::iterator_traits<Iterator>::*some-associated-type*
 114
 115 at least four times.
 116
 117 We urge you to review the documentation and implementations of
 118 |reverse_iterator|_ and the other Boost `specialized iterator
 119 adaptors`__ to get an idea of the sorts of things you can do with
 120 ``iterator_adaptor``.  In particular, have a look at
 121 |transform_iterator|_, which is perhaps the most straightforward
 122 adaptor, and also |counting_iterator|_, which demonstrates that
 123 ``iterator_adaptor``\ 's ``Base`` type needn't be an iterator.
 124
 125 .. |reverse_iterator| replace:: ``reverse_iterator``
 126 .. _reverse_iterator: reverse_iterator.html
 127
 128 .. |counting_iterator| replace:: ``counting_iterator``
 129 .. _counting_iterator: counting_iterator.html
 130
 131 .. |transform_iterator| replace:: ``transform_iterator``
 132 .. _transform_iterator: transform_iterator.html
 133
 134 __ index.html#specialized-adaptors
 135