bump version to 12.2.2-pve1

[ceph.git] / ceph / src / boost / libs / iterator / doc / iterator_facade_tutorial.rst

.. Copyright David Abrahams 2004. Use, modification and distribution is
.. subject to the Boost Software License, Version 1.0. (See accompanying
.. file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

In this section we'll walk through the implementation of a few
iterators using ``iterator_facade``, based around the simple
example of a linked list of polymorphic objects.  This example was
inspired by a `posting`__ by Keith Macdonald on the `Boost-Users`_
mailing list.

.. _`Boost-Users`: http://www.boost.org/more/mailing_lists.htm#users

__ http://thread.gmane.org/gmane.comp.lib.boost.user/5100

The Problem
-----------

Say we've written a polymorphic linked list node base class::

  # include <iostream>

  struct node_base
  {
      node_base() : m_next(0) {}

      // Each node manages all of its tail nodes
      virtual ~node_base() { delete m_next; }

      // Access the rest of the list
      node_base* next() const { return m_next; }

      // print to the stream
      virtual void print(std::ostream& s) const = 0;
      
      // double the value
      virtual void double_me() = 0;

      void append(node_base* p)
      {
          if (m_next) 
              m_next->append(p); 
          else
              m_next = p; 
      }

   private:
      node_base* m_next;
  };

Lists can hold objects of different types by linking together
specializations of the following template::

  template <class T>
  struct node : node_base
  {
      node(T x)
        : m_value(x)
      {}

      void print(std::ostream& s) const { s << this->m_value; }
      void double_me() { m_value += m_value; }

   private:
      T m_value;
  };

And we can print any node using the following streaming operator::

  inline std::ostream& operator<<(std::ostream& s, node_base const& n)
  {
      n.print(s);
      return s;
  }

Our first challenge is to build an appropriate iterator over these
lists.

A Basic Iterator Using ``iterator_facade``
------------------------------------------

We will construct a ``node_iterator`` class using inheritance from
``iterator_facade`` to implement most of the iterator's operations.

::

  # include "node.hpp"
  # include <boost/iterator/iterator_facade.hpp>

  class node_iterator
    : public boost::iterator_facade<...>
  {
     ...
  };



Template Arguments for ``iterator_facade``
..........................................

``iterator_facade`` has several template parameters, so we must decide
what types to use for the arguments. The parameters are ``Derived``,
``Value``, ``CategoryOrTraversal``, ``Reference``, and ``Difference``.


``Derived``
'''''''''''

Because ``iterator_facade`` is meant to be used with the CRTP
[Cop95]_ the first parameter is the iterator class name itself,
``node_iterator``.

``Value``
'''''''''

The ``Value`` parameter determines the ``node_iterator``\ 's
``value_type``.  In this case, we are iterating over ``node_base``
objects, so ``Value`` will be ``node_base``.


``CategoryOrTraversal``
'''''''''''''''''''''''

Now we have to determine which `iterator traversal concept`_ our
``node_iterator`` is going to model.  Singly-linked lists only have
forward links, so our iterator can't can't be a `bidirectional
traversal iterator`_.  Our iterator should be able to make multiple
passes over the same linked list (unlike, say, an
``istream_iterator`` which consumes the stream it traverses), so it
must be a `forward traversal iterator`_.  Therefore, we'll pass
``boost::forward_traversal_tag`` in this position [#category]_.

.. [#category] ``iterator_facade`` also supports old-style category
   tags, so we could have passed ``std::forward_iterator_tag`` here;
   either way, the resulting iterator's ``iterator_category`` will
   end up being ``std::forward_iterator_tag``.

``Reference``
'''''''''''''

The ``Reference`` argument becomes the type returned by
``node_iterator``\ 's dereference operation, and will also be the
same as ``std::iterator_traits<node_iterator>::reference``.  The
library's default for this parameter is ``Value&``; since
``node_base&`` is a good choice for the iterator's ``reference``
type, we can omit this argument, or pass ``use_default``.

``Difference``
''''''''''''''

The ``Difference`` argument determines how the distance between
two ``node_iterator``\ s will be measured and will also be the
same as ``std::iterator_traits<node_iterator>::difference_type``.
The library's default for ``Difference`` is ``std::ptrdiff_t``, an
appropriate type for measuring the distance between any two
addresses in memory, and one that works for almost any iterator,
so we can omit this argument, too.

The declaration of ``node_iterator`` will therefore look something
like::

  # include "node.hpp"
  # include <boost/iterator/iterator_facade.hpp>

  class node_iterator
    : public boost::iterator_facade<
          node_iterator
        , node_base
        , boost::forward_traversal_tag
      >
  {
     ...
  };

Constructors and Data Members
.............................

Next we need to decide how to represent the iterator's position.
This representation will take the form of data members, so we'll
also need to write constructors to initialize them.  The
``node_iterator``\ 's position is quite naturally represented using
a pointer to a ``node_base``.  We'll need a constructor to build an
iterator from a ``node_base*``, and a default constructor to
satisfy the `forward traversal iterator`_ requirements [#default]_.
Our ``node_iterator`` then becomes::

  # include "node.hpp"
  # include <boost/iterator/iterator_facade.hpp>

  class node_iterator
    : public boost::iterator_facade<
          node_iterator
        , node_base
        , boost::forward_traversal_tag
      >
  {
   public:
      node_iterator()
        : m_node(0)
      {}

      explicit node_iterator(node_base* p)
        : m_node(p)
      {}

   private:
      ...
      node_base* m_node;
  };

.. [#default] Technically, the C++ standard places almost no
   requirements on a default-constructed iterator, so if we were
   really concerned with efficiency, we could've written the
   default constructor to leave ``m_node`` uninitialized.

Implementing the Core Operations
................................

The last step is to implement the `core operations`_ required by
the concepts we want our iterator to model.  Referring to the
table__, we can see that the first three rows are applicable
because ``node_iterator`` needs to satisfy the requirements for
`readable iterator`_, `single pass iterator`_, and `incrementable
iterator`_.  

__ `core operations`_

We therefore need to supply ``dereference``,
``equal``, and ``increment`` members.  We don't want these members
to become part of ``node_iterator``\ 's public interface, so we can
make them private and grant friendship to
``boost::iterator_core_access``, a "back-door" that
``iterator_facade`` uses to get access to the core operations::

  # include "node.hpp"
  # include <boost/iterator/iterator_facade.hpp>

  class node_iterator
    : public boost::iterator_facade<
          node_iterator
        , node_base
        , boost::forward_traversal_tag
      >
  {
   public:
      node_iterator()
        : m_node(0) {}

      explicit node_iterator(node_base* p)
        : m_node(p) {}

   private:
      friend class boost::iterator_core_access;

      void increment() { m_node = m_node->next(); }

      bool equal(node_iterator const& other) const
      {
          return this->m_node == other.m_node;
      }

      node_base& dereference() const { return *m_node; }

      node_base* m_node;
  };