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