]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | |
2 | [section:facade_tutorial Tutorial] | |
3 | ||
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 | |
7 | inspired by a | |
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`] | |
11 | mailing list. | |
12 | ||
13 | ||
14 | [h2 The Problem] | |
15 | ||
16 | ||
17 | Say we've written a polymorphic linked list node base class: | |
18 | ||
19 | # include <iostream> | |
20 | ||
21 | struct node_base | |
22 | { | |
23 | node_base() : m_next(0) {} | |
24 | ||
25 | // Each node manages all of its tail nodes | |
26 | virtual ~node_base() { delete m_next; } | |
27 | ||
28 | // Access the rest of the list | |
29 | node_base* next() const { return m_next; } | |
30 | ||
31 | // print to the stream | |
32 | virtual void print(std::ostream& s) const = 0; | |
33 | ||
34 | // double the value | |
35 | virtual void double_me() = 0; | |
36 | ||
37 | void append(node_base* p) | |
38 | { | |
39 | if (m_next) | |
40 | m_next->append(p); | |
41 | else | |
42 | m_next = p; | |
43 | } | |
44 | ||
45 | private: | |
46 | node_base* m_next; | |
47 | }; | |
48 | ||
49 | Lists can hold objects of different types by linking together | |
50 | specializations of the following template: | |
51 | ||
52 | template <class T> | |
53 | struct node : node_base | |
54 | { | |
55 | node(T x) | |
56 | : m_value(x) | |
57 | {} | |
58 | ||
59 | void print(std::ostream& s) const { s << this->m_value; } | |
60 | void double_me() { m_value += m_value; } | |
61 | ||
62 | private: | |
63 | T m_value; | |
64 | }; | |
65 | ||
66 | And we can print any node using the following streaming operator: | |
67 | ||
68 | inline std::ostream& operator<<(std::ostream& s, node_base const& n) | |
69 | { | |
70 | n.print(s); | |
71 | return s; | |
72 | } | |
73 | ||
74 | Our first challenge is to build an appropriate iterator over these | |
75 | lists. | |
76 | ||
77 | [h2 A Basic Iterator Using `iterator_facade`] | |
78 | ||
79 | We will construct a `node_iterator` class using inheritance from | |
80 | `iterator_facade` to implement most of the iterator's operations. | |
81 | ||
82 | ||
83 | # include "node.hpp" | |
84 | # include <boost/iterator/iterator_facade.hpp> | |
85 | ||
86 | class node_iterator | |
87 | : public boost::iterator_facade<...> | |
88 | { | |
89 | ... | |
90 | }; | |
91 | ||
92 | ||
93 | ||
94 | [h2 Template Arguments for `iterator_facade`] | |
95 | ||
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`. | |
99 | ||
100 | ||
101 | [h3 `Derived`] | |
102 | ||
103 | Because `iterator_facade` is meant to be used with the CRTP | |
104 | [Cop95]_ the first parameter is the iterator class name itself, | |
105 | `node_iterator`. | |
106 | ||
107 | [h3 `Value`] | |
108 | ||
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`. | |
112 | ||
113 | ||
114 | [h3 `CategoryOrTraversal`] | |
115 | ||
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]_. | |
124 | ||
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`. | |
129 | ||
130 | [h3 `Reference`] | |
131 | ||
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`. | |
138 | ||
139 | [h3 `Difference`] | |
140 | ||
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. | |
148 | ||
149 | The declaration of `node_iterator` will therefore look something | |
150 | like: | |
151 | ||
152 | # include "node.hpp" | |
153 | # include <boost/iterator/iterator_facade.hpp> | |
154 | ||
155 | class node_iterator | |
156 | : public boost::iterator_facade< | |
157 | node_iterator | |
158 | , node_base | |
159 | , boost::forward_traversal_tag | |
160 | > | |
161 | { | |
162 | ... | |
163 | }; | |
164 | ||
165 | ||
166 | [h2 Constructors and Data Members] | |
167 | ||
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: | |
176 | ||
177 | # include "node.hpp" | |
178 | # include <boost/iterator/iterator_facade.hpp> | |
179 | ||
180 | class node_iterator | |
181 | : public boost::iterator_facade< | |
182 | node_iterator | |
183 | , node_base | |
184 | , boost::forward_traversal_tag | |
185 | > | |
186 | { | |
187 | public: | |
188 | node_iterator() | |
189 | : m_node(0) | |
190 | {} | |
191 | ||
192 | explicit node_iterator(node_base* p) | |
193 | : m_node(p) | |
194 | {} | |
195 | ||
196 | private: | |
197 | ... | |
198 | node_base* m_node; | |
199 | }; | |
200 | ||
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. | |
205 | ||
206 | [h2 Implementing the Core Operations] | |
207 | ||
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 | |
213 | iterator`_. | |
214 | ||
215 | __ `core operations`_ | |
216 | ||
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: | |
223 | ||
224 | # include "node.hpp" | |
225 | # include <boost/iterator/iterator_facade.hpp> | |
226 | ||
227 | class node_iterator | |
228 | : public boost::iterator_facade< | |
229 | node_iterator | |
230 | , node_base | |
231 | , boost::forward_traversal_tag | |
232 | > | |
233 | { | |
234 | public: | |
235 | node_iterator() | |
236 | : m_node(0) {} | |
237 | ||
238 | explicit node_iterator(node_base* p) | |
239 | : m_node(p) {} | |
240 | ||
241 | private: | |
242 | friend class boost::iterator_core_access; | |
243 | ||
244 | void increment() { m_node = m_node->next(); } | |
245 | ||
246 | bool equal(node_iterator const& other) const | |
247 | { | |
248 | return this->m_node == other.m_node; | |
249 | } | |
250 | ||
251 | node_base& dereference() const { return *m_node; } | |
252 | ||
253 | node_base* m_node; | |
254 | }; | |
255 | ||
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`]. | |
259 | ||
260 | __ ../example/node_iterator1.cpp | |
261 | ||
262 | [h2 A constant `node_iterator`] | |
263 | ||
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`. | |
278 | ] | |
279 | ||
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 | |
284 | changes: | |
285 | ||
286 | class const_node_iterator | |
287 | : public boost::iterator_facade< | |
288 | node_iterator | |
289 | , node_base **const** | |
290 | , boost::forward_traversal_tag | |
291 | > | |
292 | { | |
293 | public: | |
294 | const_node_iterator() | |
295 | : m_node(0) {} | |
296 | ||
297 | explicit const_node_iterator(node_base* p) | |
298 | : m_node(p) {} | |
299 | ||
300 | private: | |
301 | friend class boost::iterator_core_access; | |
302 | ||
303 | void increment() { m_node = m_node->next(); } | |
304 | ||
305 | bool equal(const_node_iterator const& other) const | |
306 | { | |
307 | return this->m_node == other.m_node; | |
308 | } | |
309 | ||
310 | node_base **const**\ & dereference() const { return \*m_node; } | |
311 | ||
312 | node_base **const**\ * m_node; | |
313 | }; | |
314 | ||
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. | |
323 | ] | |
324 | ||
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: | |
328 | ||
329 | template <class Value> | |
330 | class node_iter | |
331 | : public boost::iterator_facade< | |
332 | node_iter<Value> | |
333 | , Value | |
334 | , boost::forward_traversal_tag | |
335 | > | |
336 | { | |
337 | public: | |
338 | node_iter() | |
339 | : m_node(0) {} | |
340 | ||
341 | explicit node_iter(Value* p) | |
342 | : m_node(p) {} | |
343 | ||
344 | private: | |
345 | friend class boost::iterator_core_access; | |
346 | ||
347 | bool equal(node_iter<Value> const& other) const | |
348 | { | |
349 | return this->m_node == other.m_node; | |
350 | } | |
351 | ||
352 | void increment() | |
353 | { m_node = m_node->next(); } | |
354 | ||
355 | Value& dereference() const | |
356 | { return *m_node; } | |
357 | ||
358 | Value* m_node; | |
359 | }; | |
360 | typedef node_iter<node_base> node_iterator; | |
361 | typedef node_iter<node_base const> node_const_iterator; | |
362 | ||
363 | ||
364 | [h2 Interoperability] | |
365 | ||
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. | |
374 | ||
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]_: | |
379 | ||
380 | template <class Value> | |
381 | class node_iter | |
382 | : public boost::iterator_facade< | |
383 | node_iter<Value> | |
384 | , Value | |
385 | , boost::forward_traversal_tag | |
386 | > | |
387 | { | |
388 | public: | |
389 | node_iter() | |
390 | : m_node(0) {} | |
391 | ||
392 | explicit node_iter(Value* p) | |
393 | : m_node(p) {} | |
394 | ||
395 | template <class OtherValue> | |
396 | node_iter(node_iter<OtherValue> const& other) | |
397 | : m_node(other.m_node) {} | |
398 | ||
399 | private: | |
400 | friend class boost::iterator_core_access; | |
401 | template <class> friend class node_iter; | |
402 | ||
403 | template <class OtherValue> | |
404 | bool equal(node_iter<OtherValue> const& other) const | |
405 | { | |
406 | return this->m_node == other.m_node; | |
407 | } | |
408 | ||
409 | void increment() | |
410 | { m_node = m_node->next(); } | |
411 | ||
412 | Value& dereference() const | |
413 | { return *m_node; } | |
414 | ||
415 | Value* m_node; | |
416 | }; | |
417 | typedef impl::node_iterator<node_base> node_iterator; | |
418 | typedef impl::node_iterator<node_base const> node_const_iterator; | |
419 | ||
420 | .. |interoperability| replace:: **interoperability** | |
421 | .. _interoperability: new-iter-concepts.html#interoperable-iterators-lib-interoperable-iterators | |
422 | ||
423 | .. [#broken] If you're using an older compiler and it can't handle | |
424 | this example, see the `example code`__ for workarounds. | |
425 | ||
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. | |
429 | ||
430 | ||
431 | __ ../example/node_iterator2.hpp | |
432 | ||
433 | You can see an example program which exercises our interoperable | |
434 | iterators | |
435 | [@../example/node_iterator2.cpp `here`]. | |
436 | ||
437 | ||
438 | [h2 Telling the Truth] | |
439 | ||
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? | |
447 | ||
448 | The problem is that | |
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. | |
456 | ||
457 | .. |is_convertible| replace:: `is_convertible` | |
458 | .. _is_convertible: ../../type_traits/index.html#relationships | |
459 | ||
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 | |
463 | appropriate: | |
464 | ||
465 | #include <boost/type_traits/is_convertible.hpp> | |
466 | #include <boost/utility/enable_if.hpp> | |
467 | ||
468 | ... | |
469 | ||
470 | private: | |
471 | struct enabler {}; | |
472 | ||
473 | public: | |
474 | template <class OtherValue> | |
475 | node_iter( | |
476 | node_iter<OtherValue> const& other | |
477 | , typename boost::enable_if< | |
478 | boost::is_convertible<OtherValue*,Value*> | |
479 | , enabler | |
480 | >::type = enabler() | |
481 | ) | |
482 | : m_node(other.m_node) {} | |
483 | ||
484 | .. |enable_if| replace:: `boost::enable_if` | |
485 | __ ../../utility/enable_if.html | |
486 | ||
487 | ||
488 | [h2 Wrap Up] | |
489 | ||
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 | |
493 | even be superior. | |
494 | ||
495 | .. |iterator_adaptor| replace:: `iterator_adaptor` | |
496 | __ iterator_adaptor.html | |
497 | ||
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 | |
506 | ||
507 | [endsect] |