1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
|
<?xml version="1.0" encoding="utf-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="generator" content="Docutils 0.5: http://docutils.sourceforge.net/" />
<title>Iterator Adaptor</title>
<meta name="author" content="David Abrahams, Jeremy Siek, Thomas Witt" />
<meta name="organization" content="Boost Consulting, Indiana University Open Systems Lab, University of Hanover Institute for Transport Railway Operation and Construction" />
<meta name="date" content="2006-09-11" />
<meta name="copyright" content="Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003." />
<link rel="stylesheet" href="../../../rst.css" type="text/css" />
</head>
<body>
<div class="document" id="iterator-adaptor">
<h1 class="title">Iterator Adaptor</h1>
<table class="docinfo" frame="void" rules="none">
<col class="docinfo-name" />
<col class="docinfo-content" />
<tbody valign="top">
<tr><th class="docinfo-name">Author:</th>
<td>David Abrahams, Jeremy Siek, Thomas Witt</td></tr>
<tr><th class="docinfo-name">Contact:</th>
<td><a class="first reference external" href="mailto:dave@boost-consulting.com">dave@boost-consulting.com</a>, <a class="reference external" href="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</a>, <a class="last reference external" href="mailto:witt@ive.uni-hannover.de">witt@ive.uni-hannover.de</a></td></tr>
<tr><th class="docinfo-name">Organization:</th>
<td><a class="first reference external" href="http://www.boost-consulting.com">Boost Consulting</a>, Indiana University <a class="reference external" href="http://www.osl.iu.edu">Open Systems
Lab</a>, University of Hanover <a class="last reference external" href="http://www.ive.uni-hannover.de">Institute for Transport
Railway Operation and Construction</a></td></tr>
<tr><th class="docinfo-name">Date:</th>
<td>2006-09-11</td></tr>
<tr><th class="docinfo-name">Copyright:</th>
<td>Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003.</td></tr>
</tbody>
</table>
<!-- Distributed under 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) -->
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field"><th class="field-name">abstract:</th><td class="field-body"></td>
</tr>
</tbody>
</table>
<!-- Distributed under 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) -->
<!-- Version 1.1 of this ReStructuredText document corresponds to
n1530_, the paper accepted by the LWG. -->
<!-- Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003. -->
<p>Each specialization of the <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> class template is derived from
a specialization of <tt class="docutils literal"><span class="pre">iterator_facade</span></tt>. The core interface functions
expected by <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> are implemented in terms of the
<tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>'s <tt class="docutils literal"><span class="pre">Base</span></tt> template parameter. A class derived
from <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> typically redefines some of the core
interface functions to adapt the behavior of the <tt class="docutils literal"><span class="pre">Base</span></tt> type.
Whether the derived class models any of the standard iterator concepts
depends on the operations supported by the <tt class="docutils literal"><span class="pre">Base</span></tt> type and which
core interface functions of <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> are redefined in the
<tt class="docutils literal"><span class="pre">Derived</span></tt> class.</p>
<div class="contents topic" id="table-of-contents">
<p class="topic-title first">Table of Contents</p>
<ul class="simple">
<li><a class="reference internal" href="#overview" id="id6">Overview</a></li>
<li><a class="reference internal" href="#reference" id="id7">Reference</a><ul>
<li><a class="reference internal" href="#iterator-adaptor-requirements" id="id8"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> requirements</a></li>
<li><a class="reference internal" href="#iterator-adaptor-base-class-parameters" id="id9"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> base class parameters</a></li>
<li><a class="reference internal" href="#iterator-adaptor-public-operations" id="id10"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> public operations</a></li>
<li><a class="reference internal" href="#iterator-adaptor-protected-member-functions" id="id11"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> protected member functions</a></li>
<li><a class="reference internal" href="#iterator-adaptor-private-member-functions" id="id12"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> private member functions</a></li>
</ul>
</li>
<li><a class="reference internal" href="#tutorial-example" id="id13">Tutorial Example</a></li>
</ul>
</div>
<div class="section" id="overview">
<h1><a class="toc-backref" href="#id6">Overview</a></h1>
<!-- Distributed under 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) -->
<!-- Version 1.2 of this ReStructuredText document corresponds to
n1530_, the paper accepted by the LWG for TR1. -->
<!-- Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003. -->
<p>The <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> class template adapts some <tt class="docutils literal"><span class="pre">Base</span></tt><a class="footnote-reference" href="#base" id="id1"><sup>1</sup></a>
type to create a new iterator. Instantiations of <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>
are derived from a corresponding instantiation of <tt class="docutils literal"><span class="pre">iterator_facade</span></tt>
and implement the core behaviors in terms of the <tt class="docutils literal"><span class="pre">Base</span></tt> type. In
essence, <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> merely forwards all operations to an
instance of the <tt class="docutils literal"><span class="pre">Base</span></tt> type, which it stores as a member.</p>
<table class="docutils footnote" frame="void" id="base" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label">[1]</td><td><em>(<a class="fn-backref" href="#id1">1</a>, <a class="fn-backref" href="#id3">2</a>)</em> The term "Base" here does not refer to a base class and is
not meant to imply the use of derivation. We have followed the lead
of the standard library, which provides a base() function to access
the underlying iterator object of a <tt class="docutils literal"><span class="pre">reverse_iterator</span></tt> adaptor.</td></tr>
</tbody>
</table>
<p>The user of <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> creates a class derived from an
instantiation of <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> and then selectively
redefines some of the core member functions described in the
<tt class="docutils literal"><span class="pre">iterator_facade</span></tt> core requirements table. The <tt class="docutils literal"><span class="pre">Base</span></tt> type need
not meet the full requirements for an iterator; it need only
support the operations used by the core interface functions of
<tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> that have not been redefined in the user's
derived class.</p>
<p>Several of the template parameters of <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> default
to <tt class="docutils literal"><span class="pre">use_default</span></tt>. This allows the
user to make use of a default parameter even when she wants to
specify a parameter later in the parameter list. Also, the
defaults for the corresponding associated types are somewhat
complicated, so metaprogramming is required to compute them, and
<tt class="docutils literal"><span class="pre">use_default</span></tt> can help to simplify the implementation. Finally,
the identity of the <tt class="docutils literal"><span class="pre">use_default</span></tt> type is not left unspecified
because specification helps to highlight that the <tt class="docutils literal"><span class="pre">Reference</span></tt>
template parameter may not always be identical to the iterator's
<tt class="docutils literal"><span class="pre">reference</span></tt> type, and will keep users from making mistakes based on
that assumption.</p>
</div>
<div class="section" id="reference">
<h1><a class="toc-backref" href="#id7">Reference</a></h1>
<!-- Distributed under 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) -->
<!-- Version 1.4 of this ReStructuredText document corresponds to
n1530_, the paper accepted by the LWG for TR1. -->
<!-- Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003. -->
<pre class="literal-block">
template <
class Derived
, class Base
, class Value = use_default
, class CategoryOrTraversal = use_default
, class Reference = use_default
, class Difference = use_default
>
class iterator_adaptor
: public iterator_facade<Derived, <em>V'</em>, <em>C'</em>, <em>R'</em>, <em>D'</em>> // see <a class="reference internal" href="#base-parameters">details</a>
{
friend class iterator_core_access;
public:
iterator_adaptor();
explicit iterator_adaptor(Base const& iter);
typedef Base base_type;
Base const& base() const;
protected:
typedef iterator_adaptor iterator_adaptor_;
Base const& base_reference() const;
Base& base_reference();
private: // Core iterator interface for iterator_facade.
typename iterator_adaptor::reference dereference() const;
template <
class OtherDerived, class OtherIterator, class V, class C, class R, class D
>
bool equal(iterator_adaptor<OtherDerived, OtherIterator, V, C, R, D> const& x) const;
void advance(typename iterator_adaptor::difference_type n);
void increment();
void decrement();
template <
class OtherDerived, class OtherIterator, class V, class C, class R, class D
>
typename iterator_adaptor::difference_type distance_to(
iterator_adaptor<OtherDerived, OtherIterator, V, C, R, D> const& y) const;
private:
Base m_iterator; // exposition only
};
</pre>
<div class="section" id="iterator-adaptor-requirements">
<span id="requirements"></span><h2><a class="toc-backref" href="#id8"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> requirements</a></h2>
<p><tt class="docutils literal"><span class="pre">static_cast<Derived*>(iterator_adaptor*)</span></tt> shall be well-formed.
The <tt class="docutils literal"><span class="pre">Base</span></tt> argument shall be Assignable and Copy Constructible.</p>
</div>
<div class="section" id="iterator-adaptor-base-class-parameters">
<span id="base-parameters"></span><h2><a class="toc-backref" href="#id9"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> base class parameters</a></h2>
<p>The <em>V'</em>, <em>C'</em>, <em>R'</em>, and <em>D'</em> parameters of the <tt class="docutils literal"><span class="pre">iterator_facade</span></tt>
used as a base class in the summary of <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>
above are defined as follows:</p>
<pre class="literal-block">
<em>V'</em> = if (Value is use_default)
return iterator_traits<Base>::value_type
else
return Value
<em>C'</em> = if (CategoryOrTraversal is use_default)
return iterator_traversal<Base>::type
else
return CategoryOrTraversal
<em>R'</em> = if (Reference is use_default)
if (Value is use_default)
return iterator_traits<Base>::reference
else
return Value&
else
return Reference
<em>D'</em> = if (Difference is use_default)
return iterator_traits<Base>::difference_type
else
return Difference
</pre>
<!-- ``iterator_adaptor`` models
- - - - - - - - - - - - - - - - - - - - - - - - - - -
In order for ``Derived`` to model the iterator concepts corresponding
to ``iterator_traits<Derived>::iterator_category``, the expressions
involving ``m_iterator`` in the specifications of those private member
functions of ``iterator_adaptor`` that may be called by
``iterator_facade<Derived, V, C, R, D>`` in evaluating any valid
expression involving ``Derived`` in those concepts' requirements. -->
<!-- The above is confusing and needs a rewrite. -JGS -->
<!-- That's why it's removed. We're embracing inheritance, remember? -->
</div>
<div class="section" id="iterator-adaptor-public-operations">
<h2><a class="toc-backref" href="#id10"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> public operations</a></h2>
<p><tt class="docutils literal"><span class="pre">iterator_adaptor();</span></tt></p>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field"><th class="field-name">Requires:</th><td class="field-body">The <tt class="docutils literal"><span class="pre">Base</span></tt> type must be Default Constructible.</td>
</tr>
<tr class="field"><th class="field-name">Returns:</th><td class="field-body">An instance of <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> with
<tt class="docutils literal"><span class="pre">m_iterator</span></tt> default constructed.</td>
</tr>
</tbody>
</table>
<p><tt class="docutils literal"><span class="pre">explicit</span> <span class="pre">iterator_adaptor(Base</span> <span class="pre">const&</span> <span class="pre">iter);</span></tt></p>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field"><th class="field-name">Returns:</th><td class="field-body">An instance of <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> with
<tt class="docutils literal"><span class="pre">m_iterator</span></tt> copy constructed from <tt class="docutils literal"><span class="pre">iter</span></tt>.</td>
</tr>
</tbody>
</table>
<p><tt class="docutils literal"><span class="pre">Base</span> <span class="pre">const&</span> <span class="pre">base()</span> <span class="pre">const;</span></tt></p>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_iterator</span></tt></td>
</tr>
</tbody>
</table>
</div>
<div class="section" id="iterator-adaptor-protected-member-functions">
<h2><a class="toc-backref" href="#id11"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> protected member functions</a></h2>
<p><tt class="docutils literal"><span class="pre">Base</span> <span class="pre">const&</span> <span class="pre">base_reference()</span> <span class="pre">const;</span></tt></p>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field"><th class="field-name">Returns:</th><td class="field-body">A const reference to <tt class="docutils literal"><span class="pre">m_iterator</span></tt>.</td>
</tr>
</tbody>
</table>
<p><tt class="docutils literal"><span class="pre">Base&</span> <span class="pre">base_reference();</span></tt></p>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field"><th class="field-name">Returns:</th><td class="field-body">A non-const reference to <tt class="docutils literal"><span class="pre">m_iterator</span></tt>.</td>
</tr>
</tbody>
</table>
</div>
<div class="section" id="iterator-adaptor-private-member-functions">
<h2><a class="toc-backref" href="#id12"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> private member functions</a></h2>
<p><tt class="docutils literal"><span class="pre">typename</span> <span class="pre">iterator_adaptor::reference</span> <span class="pre">dereference()</span> <span class="pre">const;</span></tt></p>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*m_iterator</span></tt></td>
</tr>
</tbody>
</table>
<pre class="literal-block">
template <
class OtherDerived, class OtherIterator, class V, class C, class R, class D
>
bool equal(iterator_adaptor<OtherDerived, OtherIterator, V, C, R, D> const& x) const;
</pre>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_iterator</span> <span class="pre">==</span> <span class="pre">x.base()</span></tt></td>
</tr>
</tbody>
</table>
<p><tt class="docutils literal"><span class="pre">void</span> <span class="pre">advance(typename</span> <span class="pre">iterator_adaptor::difference_type</span> <span class="pre">n);</span></tt></p>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_iterator</span> <span class="pre">+=</span> <span class="pre">n;</span></tt></td>
</tr>
</tbody>
</table>
<p><tt class="docutils literal"><span class="pre">void</span> <span class="pre">increment();</span></tt></p>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><tt class="docutils literal"><span class="pre">++m_iterator;</span></tt></td>
</tr>
</tbody>
</table>
<p><tt class="docutils literal"><span class="pre">void</span> <span class="pre">decrement();</span></tt></p>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field"><th class="field-name">Effects:</th><td class="field-body"><tt class="docutils literal"><span class="pre">--m_iterator;</span></tt></td>
</tr>
</tbody>
</table>
<pre class="literal-block">
template <
class OtherDerived, class OtherIterator, class V, class C, class R, class D
>
typename iterator_adaptor::difference_type distance_to(
iterator_adaptor<OtherDerived, OtherIterator, V, C, R, D> const& y) const;
</pre>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">y.base()</span> <span class="pre">-</span> <span class="pre">m_iterator</span></tt></td>
</tr>
</tbody>
</table>
</div>
</div>
<div class="section" id="tutorial-example">
<h1><a class="toc-backref" href="#id13">Tutorial Example</a></h1>
<!-- 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) -->
<p>In this section we'll further refine the <tt class="docutils literal"><span class="pre">node_iter</span></tt> class
template we developed in the <a class="reference external" href="iterator_facade.html#tutorial-example"><tt class="docutils literal"><span class="pre">iterator_facade</span></tt> tutorial</a>. If you haven't already
read that material, you should go back now and check it out because
we're going to pick up right where it left off.</p>
<div class="sidebar">
<p class="first sidebar-title"><tt class="docutils literal"><span class="pre">node_base*</span></tt> really <em>is</em> an iterator</p>
<p class="last">It's not really a very interesting iterator, since <tt class="docutils literal"><span class="pre">node_base</span></tt>
is an abstract class: a pointer to a <tt class="docutils literal"><span class="pre">node_base</span></tt> just points
at some base subobject of an instance of some other class, and
incrementing a <tt class="docutils literal"><span class="pre">node_base*</span></tt> moves it past this base subobject
to who-knows-where? The most we can do with that incremented
position is to compare another <tt class="docutils literal"><span class="pre">node_base*</span></tt> to it. In other
words, the original iterator traverses a one-element array.</p>
</div>
<p>You probably didn't think of it this way, but the <tt class="docutils literal"><span class="pre">node_base*</span></tt>
object that underlies <tt class="docutils literal"><span class="pre">node_iterator</span></tt> is itself an iterator,
just like all other pointers. If we examine that pointer closely
from an iterator perspective, we can see that it has much in common
with the <tt class="docutils literal"><span class="pre">node_iterator</span></tt> we're building. First, they share most
of the same associated types (<tt class="docutils literal"><span class="pre">value_type</span></tt>, <tt class="docutils literal"><span class="pre">reference</span></tt>,
<tt class="docutils literal"><span class="pre">pointer</span></tt>, and <tt class="docutils literal"><span class="pre">difference_type</span></tt>). Second, even some of the
core functionality is the same: <tt class="docutils literal"><span class="pre">operator*</span></tt> and <tt class="docutils literal"><span class="pre">operator==</span></tt> on
the <tt class="docutils literal"><span class="pre">node_iterator</span></tt> return the result of invoking the same
operations on the underlying pointer, via the <tt class="docutils literal"><span class="pre">node_iterator</span></tt>'s
<a class="reference external" href="iterator_facade.html#implementing-the-core-operations"><tt class="docutils literal"><span class="pre">dereference</span></tt> and <tt class="docutils literal"><span class="pre">equal</span></tt> member functions</a>). The only real behavioral difference
between <tt class="docutils literal"><span class="pre">node_base*</span></tt> and <tt class="docutils literal"><span class="pre">node_iterator</span></tt> can be observed when
they are incremented: <tt class="docutils literal"><span class="pre">node_iterator</span></tt> follows the
<tt class="docutils literal"><span class="pre">m_next</span></tt> pointer, while <tt class="docutils literal"><span class="pre">node_base*</span></tt> just applies an address offset.</p>
<p>It turns out that the pattern of building an iterator on another
iterator-like type (the <tt class="docutils literal"><span class="pre">Base</span></tt><a class="footnote-reference" href="#base" id="id3"><sup>1</sup></a> type) while modifying
just a few aspects of the underlying type's behavior is an
extremely common one, and it's the pattern addressed by
<tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>. Using <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> is very much like
using <tt class="docutils literal"><span class="pre">iterator_facade</span></tt>, but because iterator_adaptor tries to
mimic as much of the <tt class="docutils literal"><span class="pre">Base</span></tt> type's behavior as possible, we
neither have to supply a <tt class="docutils literal"><span class="pre">Value</span></tt> argument, nor implement any core
behaviors other than <tt class="docutils literal"><span class="pre">increment</span></tt>. The implementation of
<tt class="docutils literal"><span class="pre">node_iter</span></tt> is thus reduced to:</p>
<pre class="literal-block">
template <class Value>
class node_iter
: public boost::iterator_adaptor<
node_iter<Value> // Derived
, Value* // Base
, boost::use_default // Value
, boost::forward_traversal_tag // CategoryOrTraversal
>
{
private:
struct enabler {}; // a private type avoids misuse
public:
node_iter()
: node_iter::iterator_adaptor_(0) {}
explicit node_iter(Value* p)
: node_iter::iterator_adaptor_(p) {}
template <class OtherValue>
node_iter(
node_iter<OtherValue> const& other
, typename boost::enable_if<
boost::is_convertible<OtherValue*,Value*>
, enabler
>::type = enabler()
)
: node_iter::iterator_adaptor_(other.base()) {}
private:
friend class boost::iterator_core_access;
void increment() { this->base_reference() = this->base()->next(); }
};
</pre>
<p>Note the use of <tt class="docutils literal"><span class="pre">node_iter::iterator_adaptor_</span></tt> here: because
<tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> defines a nested <tt class="docutils literal"><span class="pre">iterator_adaptor_</span></tt> type
that refers to itself, that gives us a convenient way to refer to
the complicated base class type of <tt class="docutils literal"><span class="pre">node_iter<Value></span></tt>. [Note:
this technique is known not to work with Borland C++ 5.6.4 and
Metrowerks CodeWarrior versions prior to 9.0]</p>
<p>You can see an example program that exercises this version of the
node iterators <a class="reference external" href="../example/node_iterator3.cpp">here</a>.</p>
<p>In the case of <tt class="docutils literal"><span class="pre">node_iter</span></tt>, it's not very compelling to pass
<tt class="docutils literal"><span class="pre">boost::use_default</span></tt> as <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>'s <tt class="docutils literal"><span class="pre">Value</span></tt>
argument; we could have just passed <tt class="docutils literal"><span class="pre">node_iter</span></tt>'s <tt class="docutils literal"><span class="pre">Value</span></tt>
along to <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>, and that'd even be shorter! Most
iterator class templates built with <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> are
parameterized on another iterator type, rather than on its
<tt class="docutils literal"><span class="pre">value_type</span></tt>. For example, <tt class="docutils literal"><span class="pre">boost::reverse_iterator</span></tt> takes an
iterator type argument and reverses its direction of traversal,
since the original iterator and the reversed one have all the same
associated types, <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>'s delegation of default
types to its <tt class="docutils literal"><span class="pre">Base</span></tt> saves the implementor of
<tt class="docutils literal"><span class="pre">boost::reverse_iterator</span></tt> from writing:</p>
<pre class="literal-block">
std::iterator_traits<Iterator>::<em>some-associated-type</em>
</pre>
<p>at least four times.</p>
<p>We urge you to review the documentation and implementations of
<a class="reference external" href="reverse_iterator.html"><tt class="docutils literal"><span class="pre">reverse_iterator</span></tt></a> and the other Boost <a class="reference external" href="index.html#specialized-adaptors">specialized iterator
adaptors</a> to get an idea of the sorts of things you can do with
<tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>. In particular, have a look at
<a class="reference external" href="transform_iterator.html"><tt class="docutils literal"><span class="pre">transform_iterator</span></tt></a>, which is perhaps the most straightforward
adaptor, and also <a class="reference external" href="counting_iterator.html"><tt class="docutils literal"><span class="pre">counting_iterator</span></tt></a>, which demonstrates that
<tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt>'s <tt class="docutils literal"><span class="pre">Base</span></tt> type needn't be an iterator.</p>
</div>
</div>
<div class="footer">
<hr class="footer" />
<a class="reference external" href="iterator_adaptor.rst">View document source</a>.
Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source.
</div>
</body>
</html>
|
