123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523 |
- .. 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;
- };
- Voilà; a complete and conforming readable, forward-traversal
- iterator! For a working example of its use, see `this program`__.
- __ ../example/node_iterator1.cpp
- A constant ``node_iterator``
- ----------------------------
- .. Sidebar:: Constant and Mutable iterators
- The term **mutable iterator** means an iterator through which
- the object it references (its "referent") can be modified. A
- **constant iterator** is one which doesn't allow modification of
- its referent.
- The words *constant* and *mutable* don't refer to the ability to
- modify the iterator itself. For example, an ``int const*`` is a
- non-\ ``const`` *constant iterator*, which can be incremented
- but doesn't allow modification of its referent, and ``int*
- const`` is a ``const`` *mutable iterator*, which cannot be
- modified but which allows modification of its referent.
- Confusing? We agree, but those are the standard terms. It
- probably doesn't help much that a container's constant iterator
- is called ``const_iterator``.
- Now, our ``node_iterator`` gives clients access to both ``node``\
- 's ``print(std::ostream&) const`` member function, but also its
- mutating ``double_me()`` member. If we wanted to build a
- *constant* ``node_iterator``, we'd only have to make three
- changes:
- .. parsed-literal::
- class const_node_iterator
- : public boost::iterator_facade<
- const_node_iterator
- , node_base **const**
- , boost::forward_traversal_tag
- >
- {
- public:
- const_node_iterator()
- : m_node(0) {}
- explicit const_node_iterator(node_base* p)
- : m_node(p) {}
- private:
- friend class boost::iterator_core_access;
- void increment() { m_node = m_node->next(); }
- bool equal(const_node_iterator const& other) const
- {
- return this->m_node == other.m_node;
- }
- node_base **const**\ & dereference() const { return \*m_node; }
- node_base **const**\ * m_node;
- };
- .. Sidebar:: ``const`` and an iterator's ``value_type``
- The C++ standard requires an iterator's ``value_type`` *not* be
- ``const``\ -qualified, so ``iterator_facade`` strips the
- ``const`` from its ``Value`` parameter in order to produce the
- iterator's ``value_type``. Making the ``Value`` argument
- ``const`` provides a useful hint to ``iterator_facade`` that the
- iterator is a *constant iterator*, and the default ``Reference``
- argument will be correct for all lvalue iterators.
- As a matter of fact, ``node_iterator`` and ``const_node_iterator``
- are so similar that it makes sense to factor the common code out
- into a template as follows::
- template <class Value>
- class node_iter
- : public boost::iterator_facade<
- node_iter<Value>
- , Value
- , boost::forward_traversal_tag
- >
- {
- public:
- node_iter()
- : m_node(0) {}
- explicit node_iter(Value* p)
- : m_node(p) {}
- private:
- friend class boost::iterator_core_access;
- bool equal(node_iter<Value> const& other) const
- {
- return this->m_node == other.m_node;
- }
- void increment()
- { m_node = m_node->next(); }
- Value& dereference() const
- { return *m_node; }
- Value* m_node;
- };
- typedef node_iter<node_base> node_iterator;
- typedef node_iter<node_base const> node_const_iterator;
- Interoperability
- ----------------
- Our ``const_node_iterator`` works perfectly well on its own, but
- taken together with ``node_iterator`` it doesn't quite meet
- expectations. For example, we'd like to be able to pass a
- ``node_iterator`` where a ``node_const_iterator`` was expected,
- just as you can with ``std::list<int>``\ 's ``iterator`` and
- ``const_iterator``. Furthermore, given a ``node_iterator`` and a
- ``node_const_iterator`` into the same list, we should be able to
- compare them for equality.
- This expected ability to use two different iterator types together
- is known as |interoperability|_. Achieving interoperability in
- our case is as simple as templatizing the ``equal`` function and
- adding a templatized converting constructor [#broken]_ [#random]_::
- template <class Value>
- class node_iter
- : public boost::iterator_facade<
- node_iter<Value>
- , Value
- , boost::forward_traversal_tag
- >
- {
- public:
- node_iter()
- : m_node(0) {}
- explicit node_iter(Value* p)
- : m_node(p) {}
- template <class OtherValue>
- node_iter(node_iter<OtherValue> const& other)
- : m_node(other.m_node) {}
- private:
- friend class boost::iterator_core_access;
- template <class> friend class node_iter;
- template <class OtherValue>
- bool equal(node_iter<OtherValue> const& other) const
- {
- return this->m_node == other.m_node;
- }
- void increment()
- { m_node = m_node->next(); }
- Value& dereference() const
- { return *m_node; }
- Value* m_node;
- };
- typedef impl::node_iterator<node_base> node_iterator;
- typedef impl::node_iterator<node_base const> node_const_iterator;
- .. |interoperability| replace:: **interoperability**
- .. _interoperability: new-iter-concepts.html#interoperable-iterators-lib-interoperable-iterators
- .. [#broken] If you're using an older compiler and it can't handle
- this example, see the `example code`__ for workarounds.
- .. [#random] If ``node_iterator`` had been a `random access
- traversal iterator`_, we'd have had to templatize its
- ``distance_to`` function as well.
- __ ../example/node_iterator2.hpp
- You can see an example program which exercises our interoperable
- iterators `here`__.
- __ ../example/node_iterator2.cpp
- Telling the Truth
- -----------------
- Now ``node_iterator`` and ``node_const_iterator`` behave exactly as
- you'd expect... almost. We can compare them and we can convert in
- one direction: from ``node_iterator`` to ``node_const_iterator``.
- If we try to convert from ``node_const_iterator`` to
- ``node_iterator``, we'll get an error when the converting
- constructor tries to initialize ``node_iterator``\ 's ``m_node``, a
- ``node*`` with a ``node const*``. So what's the problem?
- The problem is that
- ``boost::``\ |is_convertible|_\ ``<node_const_iterator,node_iterator>::value``
- will be ``true``, but it should be ``false``. |is_convertible|_
- lies because it can only see as far as the *declaration* of
- ``node_iter``\ 's converting constructor, but can't look inside at
- the *definition* to make sure it will compile. A perfect solution
- would make ``node_iter``\ 's converting constructor disappear when
- the ``m_node`` conversion would fail.
- .. |is_convertible| replace:: ``is_convertible``
- .. _is_convertible: ../../type_traits/index.html#relationships
- In fact, that sort of magic is possible using
- |enable_if|__. By rewriting the converting constructor as
- follows, we can remove it from the overload set when it's not
- appropriate::
- #include <boost/type_traits/is_convertible.hpp>
- #include <boost/utility/enable_if.hpp>
- ...
- private:
- struct enabler {};
- public:
- template <class OtherValue>
- node_iter(
- node_iter<OtherValue> const& other
- , typename boost::enable_if<
- boost::is_convertible<OtherValue*,Value*>
- , enabler
- >::type = enabler()
- )
- : m_node(other.m_node) {}
- .. |enable_if| replace:: ``boost::enable_if``
- __ ../../utility/enable_if.html
- Wrap Up
- -------
- This concludes our ``iterator_facade`` tutorial, but before you
- stop reading we urge you to take a look at |iterator_adaptor|__.
- There's another way to approach writing these iterators which might
- even be superior.
- .. |iterator_adaptor| replace:: ``iterator_adaptor``
- __ iterator_adaptor.html
- .. _`iterator traversal concept`: new-iter-concepts.html#iterator-traversal-concepts-lib-iterator-traversal
- .. _`readable iterator`: new-iter-concepts.html#readable-iterators-lib-readable-iterators
- .. _`lvalue iterator`: new-iter-concepts.html#lvalue-iterators-lib-lvalue-iterators
- .. _`single pass iterator`: new-iter-concepts.html#single-pass-iterators-lib-single-pass-iterators
- .. _`incrementable iterator`: new-iter-concepts.html#incrementable-iterators-lib-incrementable-iterators
- .. _`forward traversal iterator`: new-iter-concepts.html#forward-traversal-iterators-lib-forward-traversal-iterators
- .. _`bidirectional traversal iterator`: new-iter-concepts.html#bidirectional-traversal-iterators-lib-bidirectional-traversal-iterators
- .. _`random access traversal iterator`: new-iter-concepts.html#random-access-traversal-iterators-lib-random-access-traversal-iterators
|