2 [section:facade_tutorial Tutorial]
4 In this section we'll walk through the implementation of a few
5 iterators using `iterator_facade`, based around the simple
6 example of a linked list of polymorphic objects. This example was
8 [@http://thread.gmane.org/gmane.comp.lib.boost.user/5100 `posting`]
9 by Keith Macdonald on the
10 [@http://www.boost.org/more/mailing_lists.htm#users `Boost-Users`]
17 Say we've written a polymorphic linked list node base class:
23 node_base() : m_next(0) {}
25 // Each node manages all of its tail nodes
26 virtual ~node_base() { delete m_next; }
28 // Access the rest of the list
29 node_base* next() const { return m_next; }
31 // print to the stream
32 virtual void print(std::ostream& s) const = 0;
35 virtual void double_me() = 0;
37 void append(node_base* p)
49 Lists can hold objects of different types by linking together
50 specializations of the following template:
53 struct node : node_base
59 void print(std::ostream& s) const { s << this->m_value; }
60 void double_me() { m_value += m_value; }
66 And we can print any node using the following streaming operator:
68 inline std::ostream& operator<<(std::ostream& s, node_base const& n)
74 Our first challenge is to build an appropriate iterator over these
77 [h2 A Basic Iterator Using `iterator_facade`]
79 We will construct a `node_iterator` class using inheritance from
80 `iterator_facade` to implement most of the iterator's operations.
84 # include <boost/iterator/iterator_facade.hpp>
87 : public boost::iterator_facade<...>
94 [h2 Template Arguments for `iterator_facade`]
96 `iterator_facade` has several template parameters, so we must decide
97 what types to use for the arguments. The parameters are `Derived`,
98 `Value`, `CategoryOrTraversal`, `Reference`, and `Difference`.
103 Because `iterator_facade` is meant to be used with the CRTP
104 [Cop95]_ the first parameter is the iterator class name itself,
109 The `Value` parameter determines the `node_iterator`\ 's
110 `value_type`. In this case, we are iterating over `node_base`
111 objects, so `Value` will be `node_base`.
114 [h3 `CategoryOrTraversal`]
116 Now we have to determine which `iterator traversal concept`_ our
117 `node_iterator` is going to model. Singly-linked lists only have
118 forward links, so our iterator can't can't be a `bidirectional
119 traversal iterator`_. Our iterator should be able to make multiple
120 passes over the same linked list (unlike, say, an
121 `istream_iterator` which consumes the stream it traverses), so it
122 must be a `forward traversal iterator`_. Therefore, we'll pass
123 `boost::forward_traversal_tag` in this position [#category]_.
125 .. [#category] `iterator_facade` also supports old-style category
126 tags, so we could have passed `std::forward_iterator_tag` here;
127 either way, the resulting iterator's `iterator_category` will
128 end up being `std::forward_iterator_tag`.
132 The `Reference` argument becomes the type returned by
133 `node_iterator`\ 's dereference operation, and will also be the
134 same as `std::iterator_traits<node_iterator>::reference`. The
135 library's default for this parameter is `Value&`; since
136 `node_base&` is a good choice for the iterator's `reference`
137 type, we can omit this argument, or pass `use_default`.
141 The `Difference` argument determines how the distance between
142 two `node_iterator`\ s will be measured and will also be the
143 same as `std::iterator_traits<node_iterator>::difference_type`.
144 The library's default for `Difference` is `std::ptrdiff_t`, an
145 appropriate type for measuring the distance between any two
146 addresses in memory, and one that works for almost any iterator,
147 so we can omit this argument, too.
149 The declaration of `node_iterator` will therefore look something
153 # include <boost/iterator/iterator_facade.hpp>
156 : public boost::iterator_facade<
159 , boost::forward_traversal_tag
166 [h2 Constructors and Data Members]
168 Next we need to decide how to represent the iterator's position.
169 This representation will take the form of data members, so we'll
170 also need to write constructors to initialize them. The
171 `node_iterator`\ 's position is quite naturally represented using
172 a pointer to a `node_base`. We'll need a constructor to build an
173 iterator from a `node_base*`, and a default constructor to
174 satisfy the `forward traversal iterator`_ requirements [#default]_.
175 Our `node_iterator` then becomes:
178 # include <boost/iterator/iterator_facade.hpp>
181 : public boost::iterator_facade<
184 , boost::forward_traversal_tag
192 explicit node_iterator(node_base* p)
201 .. [#default] Technically, the C++ standard places almost no
202 requirements on a default-constructed iterator, so if we were
203 really concerned with efficiency, we could've written the
204 default constructor to leave `m_node` uninitialized.
206 [h2 Implementing the Core Operations]
208 The last step is to implement the `core operations`_ required by
209 the concepts we want our iterator to model. Referring to the
210 table__, we can see that the first three rows are applicable
211 because `node_iterator` needs to satisfy the requirements for
212 `readable iterator`_, `single pass iterator`_, and `incrementable
215 __ `core operations`_
217 We therefore need to supply `dereference`,
218 `equal`, and `increment` members. We don't want these members
219 to become part of `node_iterator`\ 's public interface, so we can
220 make them private and grant friendship to
221 `boost::iterator_core_access`, a "back-door" that
222 `iterator_facade` uses to get access to the core operations:
225 # include <boost/iterator/iterator_facade.hpp>
228 : public boost::iterator_facade<
231 , boost::forward_traversal_tag
238 explicit node_iterator(node_base* p)
242 friend class boost::iterator_core_access;
244 void increment() { m_node = m_node->next(); }
246 bool equal(node_iterator const& other) const
248 return this->m_node == other.m_node;
251 node_base& dereference() const { return *m_node; }
256 Voila; a complete and conforming readable, forward-traversal
257 iterator! For a working example of its use, see
258 [@../example/node_iterator1.cpp `this program`].
260 __ ../example/node_iterator1.cpp
262 [h2 A constant `node_iterator`]
264 [blurb *Constant and Mutable iterators*[br][br]
265 The term **mutable iterator** means an iterator through which
266 the object it references (its "referent") can be modified. A
267 **constant iterator** is one which doesn't allow modification of
268 its referent.[br][br]
269 The words *constant* and *mutable* don't refer to the ability to
270 modify the iterator itself. For example, an `int const*` is a
271 non-\ `const` *constant iterator*, which can be incremented
272 but doesn't allow modification of its referent, and `int*
273 const` is a `const` *mutable iterator*, which cannot be
274 modified but which allows modification of its referent.[br][br]
275 Confusing? We agree, but those are the standard terms. It
276 probably doesn't help much that a container's constant iterator
277 is called `const_iterator`.
280 Now, our `node_iterator` gives clients access to both `node`\
281 's `print(std::ostream&) const` member function, but also its
282 mutating `double_me()` member. If we wanted to build a
283 *constant* `node_iterator`, we'd only have to make three
286 class const_node_iterator
287 : public boost::iterator_facade<
289 , node_base **const**
290 , boost::forward_traversal_tag
294 const_node_iterator()
297 explicit const_node_iterator(node_base* p)
301 friend class boost::iterator_core_access;
303 void increment() { m_node = m_node->next(); }
305 bool equal(const_node_iterator const& other) const
307 return this->m_node == other.m_node;
310 node_base **const**\ & dereference() const { return \*m_node; }
312 node_base **const**\ * m_node;
315 [blurb `const` and an iterator's `value_type`[br][br]
316 The C++ standard requires an iterator's `value_type` *not* be
317 `const`\ -qualified, so `iterator_facade` strips the
318 `const` from its `Value` parameter in order to produce the
319 iterator's `value_type`. Making the `Value` argument
320 `const` provides a useful hint to `iterator_facade` that the
321 iterator is a *constant iterator*, and the default `Reference`
322 argument will be correct for all lvalue iterators.
325 As a matter of fact, `node_iterator` and `const_node_iterator`
326 are so similar that it makes sense to factor the common code out
327 into a template as follows:
329 template <class Value>
331 : public boost::iterator_facade<
334 , boost::forward_traversal_tag
341 explicit node_iter(Value* p)
345 friend class boost::iterator_core_access;
347 bool equal(node_iter<Value> const& other) const
349 return this->m_node == other.m_node;
353 { m_node = m_node->next(); }
355 Value& dereference() const
360 typedef node_iter<node_base> node_iterator;
361 typedef node_iter<node_base const> node_const_iterator;
364 [h2 Interoperability]
366 Our `const_node_iterator` works perfectly well on its own, but
367 taken together with `node_iterator` it doesn't quite meet
368 expectations. For example, we'd like to be able to pass a
369 `node_iterator` where a `node_const_iterator` was expected,
370 just as you can with `std::list<int>`\ 's `iterator` and
371 `const_iterator`. Furthermore, given a `node_iterator` and a
372 `node_const_iterator` into the same list, we should be able to
373 compare them for equality.
375 This expected ability to use two different iterator types together
376 is known as |interoperability|_. Achieving interoperability in
377 our case is as simple as templatizing the `equal` function and
378 adding a templatized converting constructor [#broken]_ [#random]_:
380 template <class Value>
382 : public boost::iterator_facade<
385 , boost::forward_traversal_tag
392 explicit node_iter(Value* p)
395 template <class OtherValue>
396 node_iter(node_iter<OtherValue> const& other)
397 : m_node(other.m_node) {}
400 friend class boost::iterator_core_access;
401 template <class> friend class node_iter;
403 template <class OtherValue>
404 bool equal(node_iter<OtherValue> const& other) const
406 return this->m_node == other.m_node;
410 { m_node = m_node->next(); }
412 Value& dereference() const
417 typedef impl::node_iterator<node_base> node_iterator;
418 typedef impl::node_iterator<node_base const> node_const_iterator;
420 .. |interoperability| replace:: **interoperability**
421 .. _interoperability: new-iter-concepts.html#interoperable-iterators-lib-interoperable-iterators
423 .. [#broken] If you're using an older compiler and it can't handle
424 this example, see the `example code`__ for workarounds.
426 .. [#random] If `node_iterator` had been a `random access
427 traversal iterator`_, we'd have had to templatize its
428 `distance_to` function as well.
431 __ ../example/node_iterator2.hpp
433 You can see an example program which exercises our interoperable
435 [@../example/node_iterator2.cpp `here`].
438 [h2 Telling the Truth]
440 Now `node_iterator` and `node_const_iterator` behave exactly as
441 you'd expect... almost. We can compare them and we can convert in
442 one direction: from `node_iterator` to `node_const_iterator`.
443 If we try to convert from `node_const_iterator` to
444 `node_iterator`, we'll get an error when the converting
445 constructor tries to initialize `node_iterator`\ 's `m_node`, a
446 `node*` with a `node const*`. So what's the problem?
449 `boost::`\ |is_convertible|_\ `<node_const_iterator,node_iterator>::value`
450 will be `true`, but it should be `false`. |is_convertible|_
451 lies because it can only see as far as the *declaration* of
452 `node_iter`\ 's converting constructor, but can't look inside at
453 the *definition* to make sure it will compile. A perfect solution
454 would make `node_iter`\ 's converting constructor disappear when
455 the `m_node` conversion would fail.
457 .. |is_convertible| replace:: `is_convertible`
458 .. _is_convertible: ../../type_traits/index.html#relationships
460 In fact, that sort of magic is possible using
461 |enable_if|__. By rewriting the converting constructor as
462 follows, we can remove it from the overload set when it's not
465 #include <boost/type_traits/is_convertible.hpp>
466 #include <boost/utility/enable_if.hpp>
474 template <class OtherValue>
476 node_iter<OtherValue> const& other
477 , typename boost::enable_if<
478 boost::is_convertible<OtherValue*,Value*>
482 : m_node(other.m_node) {}
484 .. |enable_if| replace:: `boost::enable_if`
485 __ ../../utility/enable_if.html
490 This concludes our `iterator_facade` tutorial, but before you
491 stop reading we urge you to take a look at |iterator_adaptor|__.
492 There's another way to approach writing these iterators which might
495 .. |iterator_adaptor| replace:: `iterator_adaptor`
496 __ iterator_adaptor.html
498 .. _`iterator traversal concept`: new-iter-concepts.html#iterator-traversal-concepts-lib-iterator-traversal
499 .. _`readable iterator`: new-iter-concepts.html#readable-iterators-lib-readable-iterators
500 .. _`lvalue iterator`: new-iter-concepts.html#lvalue-iterators-lib-lvalue-iterators
501 .. _`single pass iterator`: new-iter-concepts.html#single-pass-iterators-lib-single-pass-iterators
502 .. _`incrementable iterator`: new-iter-concepts.html#incrementable-iterators-lib-incrementable-iterators
503 .. _`forward traversal iterator`: new-iter-concepts.html#forward-traversal-iterators-lib-forward-traversal-iterators
504 .. _`bidirectional traversal iterator`: new-iter-concepts.html#bidirectional-traversal-iterators-lib-bidirectional-traversal-iterators
505 .. _`random access traversal iterator`: new-iter-concepts.html#random-access-traversal-iterators-lib-random-access-traversal-iterators