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)
5 In this section we'll walk through the implementation of a few
6 iterators using ``iterator_facade``, based around the simple
7 example of a linked list of polymorphic objects. This example was
8 inspired by a `posting`__ by Keith Macdonald on the `Boost-Users`_
11 .. _`Boost-Users`: http://www.boost.org/more/mailing_lists.htm#users
13 __ http://thread.gmane.org/gmane.comp.lib.boost.user/5100
18 Say we've written a polymorphic linked list node base class::
24 node_base() : m_next(0) {}
26 // Each node manages all of its tail nodes
27 virtual ~node_base() { delete m_next; }
29 // Access the rest of the list
30 node_base* next() const { return m_next; }
32 // print to the stream
33 virtual void print(std::ostream& s) const = 0;
36 virtual void double_me() = 0;
38 void append(node_base* p)
50 Lists can hold objects of different types by linking together
51 specializations of the following template::
54 struct node : node_base
60 void print(std::ostream& s) const { s << this->m_value; }
61 void double_me() { m_value += m_value; }
67 And we can print any node using the following streaming operator::
69 inline std::ostream& operator<<(std::ostream& s, node_base const& n)
75 Our first challenge is to build an appropriate iterator over these
78 A Basic Iterator Using ``iterator_facade``
79 ------------------------------------------
81 We will construct a ``node_iterator`` class using inheritance from
82 ``iterator_facade`` to implement most of the iterator's operations.
87 # include <boost/iterator/iterator_facade.hpp>
90 : public boost::iterator_facade<...>
97 Template Arguments for ``iterator_facade``
98 ..........................................
100 ``iterator_facade`` has several template parameters, so we must decide
101 what types to use for the arguments. The parameters are ``Derived``,
102 ``Value``, ``CategoryOrTraversal``, ``Reference``, and ``Difference``.
108 Because ``iterator_facade`` is meant to be used with the CRTP
109 [Cop95]_ the first parameter is the iterator class name itself,
115 The ``Value`` parameter determines the ``node_iterator``\ 's
116 ``value_type``. In this case, we are iterating over ``node_base``
117 objects, so ``Value`` will be ``node_base``.
120 ``CategoryOrTraversal``
121 '''''''''''''''''''''''
123 Now we have to determine which `iterator traversal concept`_ our
124 ``node_iterator`` is going to model. Singly-linked lists only have
125 forward links, so our iterator can't can't be a `bidirectional
126 traversal iterator`_. Our iterator should be able to make multiple
127 passes over the same linked list (unlike, say, an
128 ``istream_iterator`` which consumes the stream it traverses), so it
129 must be a `forward traversal iterator`_. Therefore, we'll pass
130 ``boost::forward_traversal_tag`` in this position [#category]_.
132 .. [#category] ``iterator_facade`` also supports old-style category
133 tags, so we could have passed ``std::forward_iterator_tag`` here;
134 either way, the resulting iterator's ``iterator_category`` will
135 end up being ``std::forward_iterator_tag``.
140 The ``Reference`` argument becomes the type returned by
141 ``node_iterator``\ 's dereference operation, and will also be the
142 same as ``std::iterator_traits<node_iterator>::reference``. The
143 library's default for this parameter is ``Value&``; since
144 ``node_base&`` is a good choice for the iterator's ``reference``
145 type, we can omit this argument, or pass ``use_default``.
150 The ``Difference`` argument determines how the distance between
151 two ``node_iterator``\ s will be measured and will also be the
152 same as ``std::iterator_traits<node_iterator>::difference_type``.
153 The library's default for ``Difference`` is ``std::ptrdiff_t``, an
154 appropriate type for measuring the distance between any two
155 addresses in memory, and one that works for almost any iterator,
156 so we can omit this argument, too.
158 The declaration of ``node_iterator`` will therefore look something
162 # include <boost/iterator/iterator_facade.hpp>
165 : public boost::iterator_facade<
168 , boost::forward_traversal_tag
174 Constructors and Data Members
175 .............................
177 Next we need to decide how to represent the iterator's position.
178 This representation will take the form of data members, so we'll
179 also need to write constructors to initialize them. The
180 ``node_iterator``\ 's position is quite naturally represented using
181 a pointer to a ``node_base``. We'll need a constructor to build an
182 iterator from a ``node_base*``, and a default constructor to
183 satisfy the `forward traversal iterator`_ requirements [#default]_.
184 Our ``node_iterator`` then becomes::
187 # include <boost/iterator/iterator_facade.hpp>
190 : public boost::iterator_facade<
193 , boost::forward_traversal_tag
201 explicit node_iterator(node_base* p)
210 .. [#default] Technically, the C++ standard places almost no
211 requirements on a default-constructed iterator, so if we were
212 really concerned with efficiency, we could've written the
213 default constructor to leave ``m_node`` uninitialized.
215 Implementing the Core Operations
216 ................................
218 The last step is to implement the `core operations`_ required by
219 the concepts we want our iterator to model. Referring to the
220 table__, we can see that the first three rows are applicable
221 because ``node_iterator`` needs to satisfy the requirements for
222 `readable iterator`_, `single pass iterator`_, and `incrementable
225 __ `core operations`_
227 We therefore need to supply ``dereference``,
228 ``equal``, and ``increment`` members. We don't want these members
229 to become part of ``node_iterator``\ 's public interface, so we can
230 make them private and grant friendship to
231 ``boost::iterator_core_access``, a "back-door" that
232 ``iterator_facade`` uses to get access to the core operations::
235 # include <boost/iterator/iterator_facade.hpp>
238 : public boost::iterator_facade<
241 , boost::forward_traversal_tag
248 explicit node_iterator(node_base* p)
252 friend class boost::iterator_core_access;
254 void increment() { m_node = m_node->next(); }
256 bool equal(node_iterator const& other) const
258 return this->m_node == other.m_node;
261 node_base& dereference() const { return *m_node; }
266 VoilĂ ; a complete and conforming readable, forward-traversal
267 iterator! For a working example of its use, see `this program`__.
269 __ ../example/node_iterator1.cpp
271 A constant ``node_iterator``
272 ----------------------------
274 .. Sidebar:: Constant and Mutable iterators
276 The term **mutable iterator** means an iterator through which
277 the object it references (its "referent") can be modified. A
278 **constant iterator** is one which doesn't allow modification of
281 The words *constant* and *mutable* don't refer to the ability to
282 modify the iterator itself. For example, an ``int const*`` is a
283 non-\ ``const`` *constant iterator*, which can be incremented
284 but doesn't allow modification of its referent, and ``int*
285 const`` is a ``const`` *mutable iterator*, which cannot be
286 modified but which allows modification of its referent.
288 Confusing? We agree, but those are the standard terms. It
289 probably doesn't help much that a container's constant iterator
290 is called ``const_iterator``.
292 Now, our ``node_iterator`` gives clients access to both ``node``\
293 's ``print(std::ostream&) const`` member function, but also its
294 mutating ``double_me()`` member. If we wanted to build a
295 *constant* ``node_iterator``, we'd only have to make three
300 class const_node_iterator
301 : public boost::iterator_facade<
303 , node_base **const**
304 , boost::forward_traversal_tag
308 const_node_iterator()
311 explicit const_node_iterator(node_base* p)
315 friend class boost::iterator_core_access;
317 void increment() { m_node = m_node->next(); }
319 bool equal(const_node_iterator const& other) const
321 return this->m_node == other.m_node;
324 node_base **const**\ & dereference() const { return \*m_node; }
326 node_base **const**\ * m_node;
329 .. Sidebar:: ``const`` and an iterator's ``value_type``
331 The C++ standard requires an iterator's ``value_type`` *not* be
332 ``const``\ -qualified, so ``iterator_facade`` strips the
333 ``const`` from its ``Value`` parameter in order to produce the
334 iterator's ``value_type``. Making the ``Value`` argument
335 ``const`` provides a useful hint to ``iterator_facade`` that the
336 iterator is a *constant iterator*, and the default ``Reference``
337 argument will be correct for all lvalue iterators.
339 As a matter of fact, ``node_iterator`` and ``const_node_iterator``
340 are so similar that it makes sense to factor the common code out
341 into a template as follows::
343 template <class Value>
345 : public boost::iterator_facade<
348 , boost::forward_traversal_tag
355 explicit node_iter(Value* p)
359 friend class boost::iterator_core_access;
361 bool equal(node_iter<Value> const& other) const
363 return this->m_node == other.m_node;
367 { m_node = m_node->next(); }
369 Value& dereference() const
374 typedef node_iter<node_base> node_iterator;
375 typedef node_iter<node_base const> node_const_iterator;
381 Our ``const_node_iterator`` works perfectly well on its own, but
382 taken together with ``node_iterator`` it doesn't quite meet
383 expectations. For example, we'd like to be able to pass a
384 ``node_iterator`` where a ``node_const_iterator`` was expected,
385 just as you can with ``std::list<int>``\ 's ``iterator`` and
386 ``const_iterator``. Furthermore, given a ``node_iterator`` and a
387 ``node_const_iterator`` into the same list, we should be able to
388 compare them for equality.
390 This expected ability to use two different iterator types together
391 is known as |interoperability|_. Achieving interoperability in
392 our case is as simple as templatizing the ``equal`` function and
393 adding a templatized converting constructor [#broken]_ [#random]_::
395 template <class Value>
397 : public boost::iterator_facade<
400 , boost::forward_traversal_tag
407 explicit node_iter(Value* p)
410 template <class OtherValue>
411 node_iter(node_iter<OtherValue> const& other)
412 : m_node(other.m_node) {}
415 friend class boost::iterator_core_access;
416 template <class> friend class node_iter;
418 template <class OtherValue>
419 bool equal(node_iter<OtherValue> const& other) const
421 return this->m_node == other.m_node;
425 { m_node = m_node->next(); }
427 Value& dereference() const
432 typedef impl::node_iterator<node_base> node_iterator;
433 typedef impl::node_iterator<node_base const> node_const_iterator;
435 .. |interoperability| replace:: **interoperability**
436 .. _interoperability: new-iter-concepts.html#interoperable-iterators-lib-interoperable-iterators
438 .. [#broken] If you're using an older compiler and it can't handle
439 this example, see the `example code`__ for workarounds.
441 .. [#random] If ``node_iterator`` had been a `random access
442 traversal iterator`_, we'd have had to templatize its
443 ``distance_to`` function as well.
446 __ ../example/node_iterator2.hpp
448 You can see an example program which exercises our interoperable
451 __ ../example/node_iterator2.cpp
456 Now ``node_iterator`` and ``node_const_iterator`` behave exactly as
457 you'd expect... almost. We can compare them and we can convert in
458 one direction: from ``node_iterator`` to ``node_const_iterator``.
459 If we try to convert from ``node_const_iterator`` to
460 ``node_iterator``, we'll get an error when the converting
461 constructor tries to initialize ``node_iterator``\ 's ``m_node``, a
462 ``node*`` with a ``node const*``. So what's the problem?
465 ``boost::``\ |is_convertible|_\ ``<node_const_iterator,node_iterator>::value``
466 will be ``true``, but it should be ``false``. |is_convertible|_
467 lies because it can only see as far as the *declaration* of
468 ``node_iter``\ 's converting constructor, but can't look inside at
469 the *definition* to make sure it will compile. A perfect solution
470 would make ``node_iter``\ 's converting constructor disappear when
471 the ``m_node`` conversion would fail.
473 .. |is_convertible| replace:: ``is_convertible``
474 .. _is_convertible: ../../type_traits/index.html#relationships
476 In fact, that sort of magic is possible using
477 |enable_if|__. By rewriting the converting constructor as
478 follows, we can remove it from the overload set when it's not
481 #include <boost/type_traits/is_convertible.hpp>
482 #include <boost/utility/enable_if.hpp>
490 template <class OtherValue>
492 node_iter<OtherValue> const& other
493 , typename boost::enable_if<
494 boost::is_convertible<OtherValue*,Value*>
498 : m_node(other.m_node) {}
500 .. |enable_if| replace:: ``boost::enable_if``
501 __ ../../utility/enable_if.html
507 This concludes our ``iterator_facade`` tutorial, but before you
508 stop reading we urge you to take a look at |iterator_adaptor|__.
509 There's another way to approach writing these iterators which might
512 .. |iterator_adaptor| replace:: ``iterator_adaptor``
513 __ iterator_adaptor.html
515 .. _`iterator traversal concept`: new-iter-concepts.html#iterator-traversal-concepts-lib-iterator-traversal
516 .. _`readable iterator`: new-iter-concepts.html#readable-iterators-lib-readable-iterators
517 .. _`lvalue iterator`: new-iter-concepts.html#lvalue-iterators-lib-lvalue-iterators
518 .. _`single pass iterator`: new-iter-concepts.html#single-pass-iterators-lib-single-pass-iterators
519 .. _`incrementable iterator`: new-iter-concepts.html#incrementable-iterators-lib-incrementable-iterators
520 .. _`forward traversal iterator`: new-iter-concepts.html#forward-traversal-iterators-lib-forward-traversal-iterators
521 .. _`bidirectional traversal iterator`: new-iter-concepts.html#bidirectional-traversal-iterators-lib-bidirectional-traversal-iterators
522 .. _`random access traversal iterator`: new-iter-concepts.html#random-access-traversal-iterators-lib-random-access-traversal-iterators