]>
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 Facade</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-facade"> | |
16 | <h1 class="title">Iterator Facade</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"><!-- Copyright David Abrahams 2006. Distributed under the Boost --> | |
43 | <!-- Software License, Version 1.0. (See accompanying --> | |
44 | <!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) --> | |
45 | <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> is a base class template that implements the | |
46 | interface of standard iterators in terms of a few core functions | |
47 | and associated types, to be supplied by a derived iterator class.</td> | |
48 | </tr> | |
49 | </tbody> | |
50 | </table> | |
51 | <div class="contents topic" id="table-of-contents"> | |
52 | <p class="topic-title first">Table of Contents</p> | |
53 | <ul class="simple"> | |
54 | <li><a class="reference internal" href="#overview" id="id23">Overview</a><ul> | |
55 | <li><a class="reference internal" href="#usage" id="id24">Usage</a></li> | |
56 | <li><a class="reference internal" href="#iterator-core-access" id="id25">Iterator Core Access</a></li> | |
57 | <li><a class="reference internal" href="#operator" id="id26"><tt class="docutils literal"><span class="pre">operator[]</span></tt></a></li> | |
58 | <li><a class="reference internal" href="#id2" id="id27"><tt class="docutils literal"><span class="pre">operator-></span></tt></a></li> | |
59 | </ul> | |
60 | </li> | |
61 | <li><a class="reference internal" href="#reference" id="id28">Reference</a><ul> | |
62 | <li><a class="reference internal" href="#iterator-facade-requirements" id="id29"><tt class="docutils literal"><span class="pre">iterator_facade</span></tt> Requirements</a></li> | |
63 | <li><a class="reference internal" href="#iterator-facade-operations" id="id30"><tt class="docutils literal"><span class="pre">iterator_facade</span></tt> operations</a></li> | |
64 | </ul> | |
65 | </li> | |
66 | <li><a class="reference internal" href="#tutorial-example" id="id31">Tutorial Example</a><ul> | |
67 | <li><a class="reference internal" href="#the-problem" id="id32">The Problem</a></li> | |
68 | <li><a class="reference internal" href="#a-basic-iterator-using-iterator-facade" id="id33">A Basic Iterator Using <tt class="docutils literal"><span class="pre">iterator_facade</span></tt></a><ul> | |
69 | <li><a class="reference internal" href="#template-arguments-for-iterator-facade" id="id34">Template Arguments for <tt class="docutils literal"><span class="pre">iterator_facade</span></tt></a><ul> | |
70 | <li><a class="reference internal" href="#derived" id="id35"><tt class="docutils literal"><span class="pre">Derived</span></tt></a></li> | |
71 | <li><a class="reference internal" href="#value" id="id36"><tt class="docutils literal"><span class="pre">Value</span></tt></a></li> | |
72 | <li><a class="reference internal" href="#categoryortraversal" id="id37"><tt class="docutils literal"><span class="pre">CategoryOrTraversal</span></tt></a></li> | |
73 | <li><a class="reference internal" href="#id12" id="id38"><tt class="docutils literal"><span class="pre">Reference</span></tt></a></li> | |
74 | <li><a class="reference internal" href="#difference" id="id39"><tt class="docutils literal"><span class="pre">Difference</span></tt></a></li> | |
75 | </ul> | |
76 | </li> | |
77 | <li><a class="reference internal" href="#constructors-and-data-members" id="id40">Constructors and Data Members</a></li> | |
78 | <li><a class="reference internal" href="#implementing-the-core-operations" id="id41">Implementing the Core Operations</a></li> | |
79 | </ul> | |
80 | </li> | |
81 | <li><a class="reference internal" href="#a-constant-node-iterator" id="id42">A constant <tt class="docutils literal"><span class="pre">node_iterator</span></tt></a></li> | |
82 | <li><a class="reference internal" href="#interoperability" id="id43">Interoperability</a></li> | |
83 | <li><a class="reference internal" href="#telling-the-truth" id="id44">Telling the Truth</a></li> | |
84 | <li><a class="reference internal" href="#wrap-up" id="id45">Wrap Up</a></li> | |
85 | </ul> | |
86 | </li> | |
87 | </ul> | |
88 | </div> | |
89 | <div class="section" id="overview"> | |
90 | <h1><a class="toc-backref" href="#id23">Overview</a></h1> | |
91 | <!-- Distributed under the Boost --> | |
92 | <!-- Software License, Version 1.0. (See accompanying --> | |
93 | <!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) --> | |
94 | <!-- Version 1.1 of this ReStructuredText document corresponds to | |
95 | n1530_, the paper accepted by the LWG for TR1. --> | |
96 | <!-- Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003. --> | |
97 | <p>While the iterator interface is rich, there is a core subset of the | |
98 | interface that is necessary for all the functionality. We have | |
99 | identified the following core behaviors for iterators:</p> | |
100 | <ul class="simple"> | |
101 | <li>dereferencing</li> | |
102 | <li>incrementing</li> | |
103 | <li>decrementing</li> | |
104 | <li>equality comparison</li> | |
105 | <li>random-access motion</li> | |
106 | <li>distance measurement</li> | |
107 | </ul> | |
108 | <p>In addition to the behaviors listed above, the core interface elements | |
109 | include the associated types exposed through iterator traits: | |
110 | <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">difference_type</span></tt>, and | |
111 | <tt class="docutils literal"><span class="pre">iterator_category</span></tt>.</p> | |
112 | <p>Iterator facade uses the Curiously Recurring Template | |
113 | Pattern (CRTP) <a class="citation-reference" href="#cop95" id="id1">[Cop95]</a> so that the user can specify the behavior | |
114 | of <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> in a derived class. Former designs used | |
115 | policy objects to specify the behavior, but that approach was | |
116 | discarded for several reasons:</p> | |
117 | <blockquote> | |
118 | <ol class="arabic simple"> | |
119 | <li>the creation and eventual copying of the policy object may create | |
120 | overhead that can be avoided with the current approach.</li> | |
121 | <li>The policy object approach does not allow for custom constructors | |
122 | on the created iterator types, an essential feature if | |
123 | <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> should be used in other library | |
124 | implementations.</li> | |
125 | <li>Without the use of CRTP, the standard requirement that an | |
126 | iterator's <tt class="docutils literal"><span class="pre">operator++</span></tt> returns the iterator type itself | |
127 | would mean that all iterators built with the library would | |
128 | have to be specializations of <tt class="docutils literal"><span class="pre">iterator_facade<...></span></tt>, rather | |
129 | than something more descriptive like | |
130 | <tt class="docutils literal"><span class="pre">indirect_iterator<T*></span></tt>. Cumbersome type generator | |
131 | metafunctions would be needed to build new parameterized | |
132 | iterators, and a separate <tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt> layer would be | |
133 | impossible.</li> | |
134 | </ol> | |
135 | </blockquote> | |
136 | <div class="section" id="usage"> | |
137 | <h2><a class="toc-backref" href="#id24">Usage</a></h2> | |
138 | <p>The user of <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> derives his iterator class from a | |
139 | specialization of <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> and passes the derived | |
140 | iterator class as <tt class="docutils literal"><span class="pre">iterator_facade</span></tt>'s first template parameter. | |
141 | The order of the other template parameters have been carefully | |
142 | chosen to take advantage of useful defaults. For example, when | |
143 | defining a constant lvalue iterator, the user can pass a | |
144 | const-qualified version of the iterator's <tt class="docutils literal"><span class="pre">value_type</span></tt> as | |
145 | <tt class="docutils literal"><span class="pre">iterator_facade</span></tt>'s <tt class="docutils literal"><span class="pre">Value</span></tt> parameter and omit the | |
146 | <tt class="docutils literal"><span class="pre">Reference</span></tt> parameter which follows.</p> | |
147 | <p>The derived iterator class must define member functions implementing | |
148 | the iterator's core behaviors. The following table describes | |
149 | expressions which are required to be valid depending on the category | |
150 | of the derived iterator type. These member functions are described | |
151 | briefly below and in more detail in the iterator facade | |
152 | requirements.</p> | |
153 | <blockquote> | |
154 | <table border="1" class="docutils"> | |
155 | <colgroup> | |
156 | <col width="44%" /> | |
157 | <col width="56%" /> | |
158 | </colgroup> | |
159 | <thead valign="bottom"> | |
160 | <tr><th class="head">Expression</th> | |
161 | <th class="head">Effects</th> | |
162 | </tr> | |
163 | </thead> | |
164 | <tbody valign="top"> | |
165 | <tr><td><tt class="docutils literal"><span class="pre">i.dereference()</span></tt></td> | |
166 | <td>Access the value referred to</td> | |
167 | </tr> | |
168 | <tr><td><tt class="docutils literal"><span class="pre">i.equal(j)</span></tt></td> | |
169 | <td>Compare for equality with <tt class="docutils literal"><span class="pre">j</span></tt></td> | |
170 | </tr> | |
171 | <tr><td><tt class="docutils literal"><span class="pre">i.increment()</span></tt></td> | |
172 | <td>Advance by one position</td> | |
173 | </tr> | |
174 | <tr><td><tt class="docutils literal"><span class="pre">i.decrement()</span></tt></td> | |
175 | <td>Retreat by one position</td> | |
176 | </tr> | |
177 | <tr><td><tt class="docutils literal"><span class="pre">i.advance(n)</span></tt></td> | |
178 | <td>Advance by <tt class="docutils literal"><span class="pre">n</span></tt> positions</td> | |
179 | </tr> | |
180 | <tr><td><tt class="docutils literal"><span class="pre">i.distance_to(j)</span></tt></td> | |
181 | <td>Measure the distance to <tt class="docutils literal"><span class="pre">j</span></tt></td> | |
182 | </tr> | |
183 | </tbody> | |
184 | </table> | |
185 | </blockquote> | |
186 | <!-- Should we add a comment that a zero overhead implementation of iterator_facade | |
187 | is possible with proper inlining? --> | |
188 | <p>In addition to implementing the core interface functions, an iterator | |
189 | derived from <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> typically defines several | |
190 | constructors. To model any of the standard iterator concepts, the | |
191 | iterator must at least have a copy constructor. Also, if the iterator | |
192 | type <tt class="docutils literal"><span class="pre">X</span></tt> is meant to be automatically interoperate with another | |
193 | iterator type <tt class="docutils literal"><span class="pre">Y</span></tt> (as with constant and mutable iterators) then | |
194 | there must be an implicit conversion from <tt class="docutils literal"><span class="pre">X</span></tt> to <tt class="docutils literal"><span class="pre">Y</span></tt> or from <tt class="docutils literal"><span class="pre">Y</span></tt> | |
195 | to <tt class="docutils literal"><span class="pre">X</span></tt> (but not both), typically implemented as a conversion | |
196 | constructor. Finally, if the iterator is to model Forward Traversal | |
197 | Iterator or a more-refined iterator concept, a default constructor is | |
198 | required.</p> | |
199 | </div> | |
200 | <div class="section" id="iterator-core-access"> | |
201 | <h2><a class="toc-backref" href="#id25">Iterator Core Access</a></h2> | |
202 | <p><tt class="docutils literal"><span class="pre">iterator_facade</span></tt> and the operator implementations need to be able | |
203 | to access the core member functions in the derived class. Making the | |
204 | core member functions public would expose an implementation detail to | |
205 | the user. The design used here ensures that implementation details do | |
206 | not appear in the public interface of the derived iterator type.</p> | |
207 | <p>Preventing direct access to the core member functions has two | |
208 | advantages. First, there is no possibility for the user to accidently | |
209 | use a member function of the iterator when a member of the value_type | |
210 | was intended. This has been an issue with smart pointer | |
211 | implementations in the past. The second and main advantage is that | |
212 | library implementers can freely exchange a hand-rolled iterator | |
213 | implementation for one based on <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> without fear of | |
214 | breaking code that was accessing the public core member functions | |
215 | directly.</p> | |
216 | <p>In a naive implementation, keeping the derived class' core member | |
217 | functions private would require it to grant friendship to | |
218 | <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> and each of the seven operators. In order to | |
219 | reduce the burden of limiting access, <tt class="docutils literal"><span class="pre">iterator_core_access</span></tt> is | |
220 | provided, a class that acts as a gateway to the core member functions | |
221 | in the derived iterator class. The author of the derived class only | |
222 | needs to grant friendship to <tt class="docutils literal"><span class="pre">iterator_core_access</span></tt> to make his core | |
223 | member functions available to the library.</p> | |
224 | <!-- This is no long uptodate -thw --> | |
225 | <!-- Yes it is; I made sure of it! -DWA --> | |
226 | <p><tt class="docutils literal"><span class="pre">iterator_core_access</span></tt> will be typically implemented as an empty | |
227 | class containing only private static member functions which invoke the | |
228 | iterator core member functions. There is, however, no need to | |
229 | standardize the gateway protocol. Note that even if | |
230 | <tt class="docutils literal"><span class="pre">iterator_core_access</span></tt> used public member functions it would not | |
231 | open a safety loophole, as every core member function preserves the | |
232 | invariants of the iterator.</p> | |
233 | </div> | |
234 | <div class="section" id="operator"> | |
235 | <h2><a class="toc-backref" href="#id26"><tt class="docutils literal"><span class="pre">operator[]</span></tt></a></h2> | |
236 | <p>The indexing operator for a generalized iterator presents special | |
237 | challenges. A random access iterator's <tt class="docutils literal"><span class="pre">operator[]</span></tt> is only | |
238 | required to return something convertible to its <tt class="docutils literal"><span class="pre">value_type</span></tt>. | |
239 | Requiring that it return an lvalue would rule out currently-legal | |
240 | random-access iterators which hold the referenced value in a data | |
241 | member (e.g. <a class="reference external" href="counting_iterator.html"><tt class="docutils literal"><span class="pre">counting_iterator</span></tt></a>), because <tt class="docutils literal"><span class="pre">*(p+n)</span></tt> is a reference | |
242 | into the temporary iterator <tt class="docutils literal"><span class="pre">p+n</span></tt>, which is destroyed when | |
243 | <tt class="docutils literal"><span class="pre">operator[]</span></tt> returns.</p> | |
244 | <p>Writable iterators built with <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> implement the | |
245 | semantics required by the preferred resolution to <a class="reference external" href="http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#299">issue 299</a> and | |
246 | adopted by proposal <a class="reference external" href="http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2003/n1550.htm">n1550</a>: the result of <tt class="docutils literal"><span class="pre">p[n]</span></tt> is an object | |
247 | convertible to the iterator's <tt class="docutils literal"><span class="pre">value_type</span></tt>, and <tt class="docutils literal"><span class="pre">p[n]</span> <span class="pre">=</span> <span class="pre">x</span></tt> is | |
248 | equivalent to <tt class="docutils literal"><span class="pre">*(p</span> <span class="pre">+</span> <span class="pre">n)</span> <span class="pre">=</span> <span class="pre">x</span></tt> (Note: This result object may be | |
249 | implemented as a proxy containing a copy of <tt class="docutils literal"><span class="pre">p+n</span></tt>). This approach | |
250 | will work properly for any random-access iterator regardless of the | |
251 | other details of its implementation. A user who knows more about | |
252 | the implementation of her iterator is free to implement an | |
253 | <tt class="docutils literal"><span class="pre">operator[]</span></tt> that returns an lvalue in the derived iterator | |
254 | class; it will hide the one supplied by <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> from | |
255 | clients of her iterator.</p> | |
256 | </div> | |
257 | <div class="section" id="id2"> | |
258 | <span id="operator-arrow"></span><h2><a class="toc-backref" href="#id27"><tt class="docutils literal"><span class="pre">operator-></span></tt></a></h2> | |
259 | <p>The <tt class="docutils literal"><span class="pre">reference</span></tt> type of a readable iterator (and today's input | |
260 | iterator) need not in fact be a reference, so long as it is | |
261 | convertible to the iterator's <tt class="docutils literal"><span class="pre">value_type</span></tt>. When the <tt class="docutils literal"><span class="pre">value_type</span></tt> | |
262 | is a class, however, it must still be possible to access members | |
263 | through <tt class="docutils literal"><span class="pre">operator-></span></tt>. Therefore, an iterator whose <tt class="docutils literal"><span class="pre">reference</span></tt> | |
264 | type is not in fact a reference must return a proxy containing a copy | |
265 | of the referenced value from its <tt class="docutils literal"><span class="pre">operator-></span></tt>.</p> | |
266 | <p>The return types for <tt class="docutils literal"><span class="pre">iterator_facade</span></tt>'s <tt class="docutils literal"><span class="pre">operator-></span></tt> and | |
267 | <tt class="docutils literal"><span class="pre">operator[]</span></tt> are not explicitly specified. Instead, those types | |
268 | are described in terms of a set of requirements, which must be | |
269 | satisfied by the <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> implementation.</p> | |
270 | <table class="docutils citation" frame="void" id="cop95" rules="none"> | |
271 | <colgroup><col class="label" /><col /></colgroup> | |
272 | <tbody valign="top"> | |
273 | <tr><td class="label">[Cop95]</td><td><em>(<a class="fn-backref" href="#id1">1</a>, <a class="fn-backref" href="#id10">2</a>)</em> [Coplien, 1995] Coplien, J., Curiously Recurring Template | |
274 | Patterns, C++ Report, February 1995, pp. 24-27.</td></tr> | |
275 | </tbody> | |
276 | </table> | |
277 | </div> | |
278 | </div> | |
279 | <div class="section" id="reference"> | |
280 | <h1><a class="toc-backref" href="#id28">Reference</a></h1> | |
281 | <!-- Distributed under the Boost --> | |
282 | <!-- Software License, Version 1.0. (See accompanying --> | |
283 | <!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) --> | |
284 | <!-- Version 1.3 of this ReStructuredText document corresponds to | |
285 | n1530_, the paper accepted by the LWG for TR1. --> | |
286 | <!-- Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003. --> | |
287 | <pre class="literal-block"> | |
288 | template < | |
289 | class Derived | |
290 | , class Value | |
291 | , class CategoryOrTraversal | |
292 | , class Reference = Value& | |
293 | , class Difference = ptrdiff_t | |
294 | > | |
295 | class iterator_facade { | |
296 | public: | |
297 | typedef remove_const<Value>::type value_type; | |
298 | typedef Reference reference; | |
299 | typedef Value* pointer; | |
300 | typedef Difference difference_type; | |
301 | typedef /* see <a class="reference internal" href="#iterator-category">below</a> */ iterator_category; | |
302 | ||
303 | reference operator*() const; | |
304 | /* see <a class="reference internal" href="#operator-arrow">below</a> */ operator->() const; | |
305 | /* see <a class="reference internal" href="#brackets">below</a> */ operator[](difference_type n) const; | |
306 | Derived& operator++(); | |
307 | Derived operator++(int); | |
308 | Derived& operator--(); | |
309 | Derived operator--(int); | |
310 | Derived& operator+=(difference_type n); | |
311 | Derived& operator-=(difference_type n); | |
312 | Derived operator-(difference_type n) const; | |
313 | protected: | |
314 | typedef iterator_facade iterator_facade_; | |
315 | }; | |
316 | ||
317 | // Comparison operators | |
318 | template <class Dr1, class V1, class TC1, class R1, class D1, | |
319 | class Dr2, class V2, class TC2, class R2, class D2> | |
320 | typename enable_if_interoperable<Dr1,Dr2,bool>::type // exposition | |
321 | operator ==(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, | |
322 | iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); | |
323 | ||
324 | template <class Dr1, class V1, class TC1, class R1, class D1, | |
325 | class Dr2, class V2, class TC2, class R2, class D2> | |
326 | typename enable_if_interoperable<Dr1,Dr2,bool>::type | |
327 | operator !=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, | |
328 | iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); | |
329 | ||
330 | template <class Dr1, class V1, class TC1, class R1, class D1, | |
331 | class Dr2, class V2, class TC2, class R2, class D2> | |
332 | typename enable_if_interoperable<Dr1,Dr2,bool>::type | |
333 | operator <(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, | |
334 | iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); | |
335 | ||
336 | template <class Dr1, class V1, class TC1, class R1, class D1, | |
337 | class Dr2, class V2, class TC2, class R2, class D2> | |
338 | typename enable_if_interoperable<Dr1,Dr2,bool>::type | |
339 | operator <=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, | |
340 | iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); | |
341 | ||
342 | template <class Dr1, class V1, class TC1, class R1, class D1, | |
343 | class Dr2, class V2, class TC2, class R2, class D2> | |
344 | typename enable_if_interoperable<Dr1,Dr2,bool>::type | |
345 | operator >(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, | |
346 | iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); | |
347 | ||
348 | template <class Dr1, class V1, class TC1, class R1, class D1, | |
349 | class Dr2, class V2, class TC2, class R2, class D2> | |
350 | typename enable_if_interoperable<Dr1,Dr2,bool>::type | |
351 | operator >=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, | |
352 | iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); | |
353 | ||
354 | // Iterator difference | |
355 | template <class Dr1, class V1, class TC1, class R1, class D1, | |
356 | class Dr2, class V2, class TC2, class R2, class D2> | |
357 | /* see <a class="reference internal" href="#minus">below</a> */ | |
358 | operator-(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, | |
359 | iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); | |
360 | ||
361 | // Iterator addition | |
362 | template <class Dr, class V, class TC, class R, class D> | |
363 | Derived operator+ (iterator_facade<Dr,V,TC,R,D> const&, | |
364 | typename Derived::difference_type n); | |
365 | ||
366 | template <class Dr, class V, class TC, class R, class D> | |
367 | Derived operator+ (typename Derived::difference_type n, | |
368 | iterator_facade<Dr,V,TC,R,D> const&); | |
369 | </pre> | |
370 | <p id="iterator-category">The <tt class="docutils literal"><span class="pre">iterator_category</span></tt> member of <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> is</p> | |
371 | <pre class="literal-block"> | |
372 | <em>iterator-category</em>(CategoryOrTraversal, value_type, reference) | |
373 | </pre> | |
374 | <p>where <em>iterator-category</em> is defined as follows:</p> | |
375 | <pre class="literal-block" id="id7"> | |
376 | <em>iterator-category</em>(C,R,V) := | |
377 | if (C is convertible to std::input_iterator_tag | |
378 | || C is convertible to std::output_iterator_tag | |
379 | ) | |
380 | return C | |
381 | ||
382 | else if (C is not convertible to incrementable_traversal_tag) | |
383 | <em>the program is ill-formed</em> | |
384 | ||
385 | else return a type X satisfying the following two constraints: | |
386 | ||
387 | 1. X is convertible to X1, and not to any more-derived | |
388 | type, where X1 is defined by: | |
389 | ||
390 | if (R is a reference type | |
391 | && C is convertible to forward_traversal_tag) | |
392 | { | |
393 | if (C is convertible to random_access_traversal_tag) | |
394 | X1 = random_access_iterator_tag | |
395 | else if (C is convertible to bidirectional_traversal_tag) | |
396 | X1 = bidirectional_iterator_tag | |
397 | else | |
398 | X1 = forward_iterator_tag | |
399 | } | |
400 | else | |
401 | { | |
402 | if (C is convertible to single_pass_traversal_tag | |
403 | && R is convertible to V) | |
404 | X1 = input_iterator_tag | |
405 | else | |
406 | X1 = C | |
407 | } | |
408 | ||
409 | 2. <a class="reference external" href="new-iter-concepts.html#category-to-traversal"><em>category-to-traversal</em></a>(X) is convertible to the most | |
410 | derived traversal tag type to which X is also | |
411 | convertible, and not to any more-derived traversal tag | |
412 | type. | |
413 | </pre> | |
414 | <p>[Note: the intention is to allow <tt class="docutils literal"><span class="pre">iterator_category</span></tt> to be one of | |
415 | the five original category tags when convertibility to one of the | |
416 | traversal tags would add no information]</p> | |
417 | <!-- Copyright David Abrahams 2004. Use, modification and distribution is --> | |
418 | <!-- subject to the Boost Software License, Version 1.0. (See accompanying --> | |
419 | <!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) --> | |
420 | <p>The <tt class="docutils literal"><span class="pre">enable_if_interoperable</span></tt> template used above is for exposition | |
421 | purposes. The member operators should only be in an overload set | |
422 | provided the derived types <tt class="docutils literal"><span class="pre">Dr1</span></tt> and <tt class="docutils literal"><span class="pre">Dr2</span></tt> are interoperable, | |
423 | meaning that at least one of the types is convertible to the other. The | |
424 | <tt class="docutils literal"><span class="pre">enable_if_interoperable</span></tt> approach uses SFINAE to take the operators | |
425 | out of the overload set when the types are not interoperable. | |
426 | The operators should behave <em>as-if</em> <tt class="docutils literal"><span class="pre">enable_if_interoperable</span></tt> | |
427 | were defined to be:</p> | |
428 | <pre class="literal-block"> | |
429 | template <bool, typename> enable_if_interoperable_impl | |
430 | {}; | |
431 | ||
432 | template <typename T> enable_if_interoperable_impl<true,T> | |
433 | { typedef T type; }; | |
434 | ||
435 | template<typename Dr1, typename Dr2, typename T> | |
436 | struct enable_if_interoperable | |
437 | : enable_if_interoperable_impl< | |
438 | is_convertible<Dr1,Dr2>::value || is_convertible<Dr2,Dr1>::value | |
439 | , T | |
440 | > | |
441 | {}; | |
442 | </pre> | |
443 | <div class="section" id="iterator-facade-requirements"> | |
444 | <h2><a class="toc-backref" href="#id29"><tt class="docutils literal"><span class="pre">iterator_facade</span></tt> Requirements</a></h2> | |
445 | <p>The following table describes the typical valid expressions on | |
446 | <tt class="docutils literal"><span class="pre">iterator_facade</span></tt>'s <tt class="docutils literal"><span class="pre">Derived</span></tt> parameter, depending on the | |
447 | iterator concept(s) it will model. The operations in the first | |
448 | column must be made accessible to member functions of class | |
449 | <tt class="docutils literal"><span class="pre">iterator_core_access</span></tt>. In addition, | |
450 | <tt class="docutils literal"><span class="pre">static_cast<Derived*>(iterator_facade*)</span></tt> shall be well-formed.</p> | |
451 | <p>In the table below, <tt class="docutils literal"><span class="pre">F</span></tt> is <tt class="docutils literal"><span class="pre">iterator_facade<X,V,C,R,D></span></tt>, <tt class="docutils literal"><span class="pre">a</span></tt> is an | |
452 | object of type <tt class="docutils literal"><span class="pre">X</span></tt>, <tt class="docutils literal"><span class="pre">b</span></tt> and <tt class="docutils literal"><span class="pre">c</span></tt> are objects of type <tt class="docutils literal"><span class="pre">const</span> <span class="pre">X</span></tt>, | |
453 | <tt class="docutils literal"><span class="pre">n</span></tt> is an object of <tt class="docutils literal"><span class="pre">F::difference_type</span></tt>, <tt class="docutils literal"><span class="pre">y</span></tt> is a constant | |
454 | object of a single pass iterator type interoperable with <tt class="docutils literal"><span class="pre">X</span></tt>, and <tt class="docutils literal"><span class="pre">z</span></tt> | |
455 | is a constant object of a random access traversal iterator type | |
456 | interoperable with <tt class="docutils literal"><span class="pre">X</span></tt>.</p> | |
457 | <div class="topic" id="core-operations"> | |
458 | <p class="topic-title first"><tt class="docutils literal"><span class="pre">iterator_facade</span></tt> Core Operations</p> | |
459 | <table border="1" class="docutils"> | |
460 | <colgroup> | |
461 | <col width="21%" /> | |
462 | <col width="23%" /> | |
463 | <col width="27%" /> | |
464 | <col width="29%" /> | |
465 | </colgroup> | |
466 | <thead valign="bottom"> | |
467 | <tr><th class="head">Expression</th> | |
468 | <th class="head">Return Type</th> | |
469 | <th class="head">Assertion/Note</th> | |
470 | <th class="head">Used to implement Iterator | |
471 | Concept(s)</th> | |
472 | </tr> | |
473 | </thead> | |
474 | <tbody valign="top"> | |
475 | <tr><td><tt class="docutils literal"><span class="pre">c.dereference()</span></tt></td> | |
476 | <td><tt class="docutils literal"><span class="pre">F::reference</span></tt></td> | |
477 | <td> </td> | |
478 | <td>Readable Iterator, Writable | |
479 | Iterator</td> | |
480 | </tr> | |
481 | <tr><td><tt class="docutils literal"><span class="pre">c.equal(y)</span></tt></td> | |
482 | <td>convertible to bool</td> | |
483 | <td>true iff <tt class="docutils literal"><span class="pre">c</span></tt> and <tt class="docutils literal"><span class="pre">y</span></tt> | |
484 | refer to the same | |
485 | position.</td> | |
486 | <td>Single Pass Iterator</td> | |
487 | </tr> | |
488 | <tr><td><tt class="docutils literal"><span class="pre">a.increment()</span></tt></td> | |
489 | <td>unused</td> | |
490 | <td> </td> | |
491 | <td>Incrementable Iterator</td> | |
492 | </tr> | |
493 | <tr><td><tt class="docutils literal"><span class="pre">a.decrement()</span></tt></td> | |
494 | <td>unused</td> | |
495 | <td> </td> | |
496 | <td>Bidirectional Traversal | |
497 | Iterator</td> | |
498 | </tr> | |
499 | <tr><td><tt class="docutils literal"><span class="pre">a.advance(n)</span></tt></td> | |
500 | <td>unused</td> | |
501 | <td> </td> | |
502 | <td>Random Access Traversal | |
503 | Iterator</td> | |
504 | </tr> | |
505 | <tr><td><tt class="docutils literal"><span class="pre">c.distance_to(z)</span></tt></td> | |
506 | <td>convertible to | |
507 | <tt class="docutils literal"><span class="pre">F::difference_type</span></tt></td> | |
508 | <td>equivalent to | |
509 | <tt class="docutils literal"><span class="pre">distance(c,</span> <span class="pre">X(z))</span></tt>.</td> | |
510 | <td>Random Access Traversal | |
511 | Iterator</td> | |
512 | </tr> | |
513 | </tbody> | |
514 | </table> | |
515 | </div> | |
516 | </div> | |
517 | <div class="section" id="iterator-facade-operations"> | |
518 | <h2><a class="toc-backref" href="#id30"><tt class="docutils literal"><span class="pre">iterator_facade</span></tt> operations</a></h2> | |
519 | <p>The operations in this section are described in terms of operations on | |
520 | the core interface of <tt class="docutils literal"><span class="pre">Derived</span></tt> which may be inaccessible | |
521 | (i.e. private). The implementation should access these operations | |
522 | through member functions of class <tt class="docutils literal"><span class="pre">iterator_core_access</span></tt>.</p> | |
523 | <p><tt class="docutils literal"><span class="pre">reference</span> <span class="pre">operator*()</span> <span class="pre">const;</span></tt></p> | |
524 | <table class="docutils field-list" frame="void" rules="none"> | |
525 | <col class="field-name" /> | |
526 | <col class="field-body" /> | |
527 | <tbody valign="top"> | |
528 | <tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">static_cast<Derived</span> <span class="pre">const*>(this)->dereference()</span></tt></td> | |
529 | </tr> | |
530 | </tbody> | |
531 | </table> | |
532 | <p><tt class="docutils literal"><span class="pre">operator->()</span> <span class="pre">const;</span></tt> (see <a class="reference internal" href="#operator-arrow">below</a>)</p> | |
533 | <table class="docutils field-list" frame="void" rules="none"> | |
534 | <col class="field-name" /> | |
535 | <col class="field-body" /> | |
536 | <tbody valign="top"> | |
537 | <tr class="field"><th class="field-name">Returns:</th><td class="field-body"><p class="first">If <tt class="docutils literal"><span class="pre">reference</span></tt> is a reference type, an object | |
538 | of type <tt class="docutils literal"><span class="pre">pointer</span></tt> equal to:</p> | |
539 | <pre class="literal-block"> | |
540 | &static_cast<Derived const*>(this)->dereference() | |
541 | </pre> | |
542 | <p class="last">Otherwise returns an object of unspecified type such that, | |
543 | <tt class="docutils literal"><span class="pre">(*static_cast<Derived</span> <span class="pre">const*>(this))->m</span></tt> is equivalent to <tt class="docutils literal"><span class="pre">(w</span> <span class="pre">=</span> <span class="pre">**static_cast<Derived</span> <span class="pre">const*>(this),</span> | |
544 | <span class="pre">w.m)</span></tt> for some temporary object <tt class="docutils literal"><span class="pre">w</span></tt> of type <tt class="docutils literal"><span class="pre">value_type</span></tt>.</p> | |
545 | </td> | |
546 | </tr> | |
547 | </tbody> | |
548 | </table> | |
549 | <p id="brackets"><em>unspecified</em> <tt class="docutils literal"><span class="pre">operator[](difference_type</span> <span class="pre">n)</span> <span class="pre">const;</span></tt></p> | |
550 | <table class="docutils field-list" frame="void" rules="none"> | |
551 | <col class="field-name" /> | |
552 | <col class="field-body" /> | |
553 | <tbody valign="top"> | |
554 | <tr class="field"><th class="field-name">Returns:</th><td class="field-body">an object convertible to <tt class="docutils literal"><span class="pre">value_type</span></tt>. For constant | |
555 | objects <tt class="docutils literal"><span class="pre">v</span></tt> of type <tt class="docutils literal"><span class="pre">value_type</span></tt>, and <tt class="docutils literal"><span class="pre">n</span></tt> of type | |
556 | <tt class="docutils literal"><span class="pre">difference_type</span></tt>, <tt class="docutils literal"><span class="pre">(*this)[n]</span> <span class="pre">=</span> <span class="pre">v</span></tt> is equivalent to | |
557 | <tt class="docutils literal"><span class="pre">*(*this</span> <span class="pre">+</span> <span class="pre">n)</span> <span class="pre">=</span> <span class="pre">v</span></tt>, and <tt class="docutils literal"><span class="pre">static_cast<value_type</span> | |
558 | <span class="pre">const&>((*this)[n])</span></tt> is equivalent to | |
559 | <tt class="docutils literal"><span class="pre">static_cast<value_type</span> <span class="pre">const&>(*(*this</span> <span class="pre">+</span> <span class="pre">n))</span></tt></td> | |
560 | </tr> | |
561 | </tbody> | |
562 | </table> | |
563 | <p><tt class="docutils literal"><span class="pre">Derived&</span> <span class="pre">operator++();</span></tt></p> | |
564 | <table class="docutils field-list" frame="void" rules="none"> | |
565 | <col class="field-name" /> | |
566 | <col class="field-body" /> | |
567 | <tbody valign="top"> | |
568 | <tr class="field"><th class="field-name">Effects:</th><td class="field-body"><pre class="first last literal-block"> | |
569 | static_cast<Derived*>(this)->increment(); | |
570 | return *static_cast<Derived*>(this); | |
571 | </pre> | |
572 | </td> | |
573 | </tr> | |
574 | </tbody> | |
575 | </table> | |
576 | <p><tt class="docutils literal"><span class="pre">Derived</span> <span class="pre">operator++(int);</span></tt></p> | |
577 | <table class="docutils field-list" frame="void" rules="none"> | |
578 | <col class="field-name" /> | |
579 | <col class="field-body" /> | |
580 | <tbody valign="top"> | |
581 | <tr class="field"><th class="field-name">Effects:</th><td class="field-body"><pre class="first last literal-block"> | |
582 | Derived tmp(static_cast<Derived const*>(this)); | |
583 | ++*this; | |
584 | return tmp; | |
585 | </pre> | |
586 | </td> | |
587 | </tr> | |
588 | </tbody> | |
589 | </table> | |
590 | <p><tt class="docutils literal"><span class="pre">Derived&</span> <span class="pre">operator--();</span></tt></p> | |
591 | <table class="docutils field-list" frame="void" rules="none"> | |
592 | <col class="field-name" /> | |
593 | <col class="field-body" /> | |
594 | <tbody valign="top"> | |
595 | <tr class="field"><th class="field-name">Effects:</th><td class="field-body"><pre class="first last literal-block"> | |
596 | static_cast<Derived*>(this)->decrement(); | |
597 | return *static_cast<Derived*>(this); | |
598 | </pre> | |
599 | </td> | |
600 | </tr> | |
601 | </tbody> | |
602 | </table> | |
603 | <p><tt class="docutils literal"><span class="pre">Derived</span> <span class="pre">operator--(int);</span></tt></p> | |
604 | <table class="docutils field-list" frame="void" rules="none"> | |
605 | <col class="field-name" /> | |
606 | <col class="field-body" /> | |
607 | <tbody valign="top"> | |
608 | <tr class="field"><th class="field-name">Effects:</th><td class="field-body"><pre class="first last literal-block"> | |
609 | Derived tmp(static_cast<Derived const*>(this)); | |
610 | --*this; | |
611 | return tmp; | |
612 | </pre> | |
613 | </td> | |
614 | </tr> | |
615 | </tbody> | |
616 | </table> | |
617 | <p><tt class="docutils literal"><span class="pre">Derived&</span> <span class="pre">operator+=(difference_type</span> <span class="pre">n);</span></tt></p> | |
618 | <table class="docutils field-list" frame="void" rules="none"> | |
619 | <col class="field-name" /> | |
620 | <col class="field-body" /> | |
621 | <tbody valign="top"> | |
622 | <tr class="field"><th class="field-name">Effects:</th><td class="field-body"><pre class="first last literal-block"> | |
623 | static_cast<Derived*>(this)->advance(n); | |
624 | return *static_cast<Derived*>(this); | |
625 | </pre> | |
626 | </td> | |
627 | </tr> | |
628 | </tbody> | |
629 | </table> | |
630 | <p><tt class="docutils literal"><span class="pre">Derived&</span> <span class="pre">operator-=(difference_type</span> <span class="pre">n);</span></tt></p> | |
631 | <table class="docutils field-list" frame="void" rules="none"> | |
632 | <col class="field-name" /> | |
633 | <col class="field-body" /> | |
634 | <tbody valign="top"> | |
635 | <tr class="field"><th class="field-name">Effects:</th><td class="field-body"><pre class="first last literal-block"> | |
636 | static_cast<Derived*>(this)->advance(-n); | |
637 | return *static_cast<Derived*>(this); | |
638 | </pre> | |
639 | </td> | |
640 | </tr> | |
641 | </tbody> | |
642 | </table> | |
643 | <p><tt class="docutils literal"><span class="pre">Derived</span> <span class="pre">operator-(difference_type</span> <span class="pre">n)</span> <span class="pre">const;</span></tt></p> | |
644 | <table class="docutils field-list" frame="void" rules="none"> | |
645 | <col class="field-name" /> | |
646 | <col class="field-body" /> | |
647 | <tbody valign="top"> | |
648 | <tr class="field"><th class="field-name">Effects:</th><td class="field-body"><pre class="first last literal-block"> | |
649 | Derived tmp(static_cast<Derived const*>(this)); | |
650 | return tmp -= n; | |
651 | </pre> | |
652 | </td> | |
653 | </tr> | |
654 | </tbody> | |
655 | </table> | |
656 | <pre class="literal-block"> | |
657 | template <class Dr, class V, class TC, class R, class D> | |
658 | Derived operator+ (iterator_facade<Dr,V,TC,R,D> const&, | |
659 | typename Derived::difference_type n); | |
660 | ||
661 | template <class Dr, class V, class TC, class R, class D> | |
662 | Derived operator+ (typename Derived::difference_type n, | |
663 | iterator_facade<Dr,V,TC,R,D> const&); | |
664 | </pre> | |
665 | <table class="docutils field-list" frame="void" rules="none"> | |
666 | <col class="field-name" /> | |
667 | <col class="field-body" /> | |
668 | <tbody valign="top"> | |
669 | <tr class="field"><th class="field-name">Effects:</th><td class="field-body"><pre class="first last literal-block"> | |
670 | Derived tmp(static_cast<Derived const*>(this)); | |
671 | return tmp += n; | |
672 | </pre> | |
673 | </td> | |
674 | </tr> | |
675 | </tbody> | |
676 | </table> | |
677 | <pre class="literal-block"> | |
678 | template <class Dr1, class V1, class TC1, class R1, class D1, | |
679 | class Dr2, class V2, class TC2, class R2, class D2> | |
680 | typename enable_if_interoperable<Dr1,Dr2,bool>::type | |
681 | operator ==(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, | |
682 | iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); | |
683 | </pre> | |
684 | <table class="docutils field-list" frame="void" rules="none"> | |
685 | <col class="field-name" /> | |
686 | <col class="field-body" /> | |
687 | <tbody valign="top"> | |
688 | <tr class="field"><th class="field-name">Returns:</th><td class="field-body"><p class="first">if <tt class="docutils literal"><span class="pre">is_convertible<Dr2,Dr1>::value</span></tt></p> | |
689 | <dl class="last docutils"> | |
690 | <dt>then</dt> | |
691 | <dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr1</span> <span class="pre">const&)lhs).equal((Dr2</span> <span class="pre">const&)rhs)</span></tt>.</p> | |
692 | </dd> | |
693 | <dt>Otherwise,</dt> | |
694 | <dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr2</span> <span class="pre">const&)rhs).equal((Dr1</span> <span class="pre">const&)lhs)</span></tt>.</p> | |
695 | </dd> | |
696 | </dl> | |
697 | </td> | |
698 | </tr> | |
699 | </tbody> | |
700 | </table> | |
701 | <pre class="literal-block"> | |
702 | template <class Dr1, class V1, class TC1, class R1, class D1, | |
703 | class Dr2, class V2, class TC2, class R2, class D2> | |
704 | typename enable_if_interoperable<Dr1,Dr2,bool>::type | |
705 | operator !=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, | |
706 | iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); | |
707 | </pre> | |
708 | <table class="docutils field-list" frame="void" rules="none"> | |
709 | <col class="field-name" /> | |
710 | <col class="field-body" /> | |
711 | <tbody valign="top"> | |
712 | <tr class="field"><th class="field-name">Returns:</th><td class="field-body"><p class="first">if <tt class="docutils literal"><span class="pre">is_convertible<Dr2,Dr1>::value</span></tt></p> | |
713 | <dl class="last docutils"> | |
714 | <dt>then</dt> | |
715 | <dd><p class="first last"><tt class="docutils literal"><span class="pre">!((Dr1</span> <span class="pre">const&)lhs).equal((Dr2</span> <span class="pre">const&)rhs)</span></tt>.</p> | |
716 | </dd> | |
717 | <dt>Otherwise,</dt> | |
718 | <dd><p class="first last"><tt class="docutils literal"><span class="pre">!((Dr2</span> <span class="pre">const&)rhs).equal((Dr1</span> <span class="pre">const&)lhs)</span></tt>.</p> | |
719 | </dd> | |
720 | </dl> | |
721 | </td> | |
722 | </tr> | |
723 | </tbody> | |
724 | </table> | |
725 | <pre class="literal-block"> | |
726 | template <class Dr1, class V1, class TC1, class R1, class D1, | |
727 | class Dr2, class V2, class TC2, class R2, class D2> | |
728 | typename enable_if_interoperable<Dr1,Dr2,bool>::type | |
729 | operator <(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, | |
730 | iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); | |
731 | </pre> | |
732 | <table class="docutils field-list" frame="void" rules="none"> | |
733 | <col class="field-name" /> | |
734 | <col class="field-body" /> | |
735 | <tbody valign="top"> | |
736 | <tr class="field"><th class="field-name">Returns:</th><td class="field-body"><p class="first">if <tt class="docutils literal"><span class="pre">is_convertible<Dr2,Dr1>::value</span></tt></p> | |
737 | <dl class="last docutils"> | |
738 | <dt>then</dt> | |
739 | <dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr1</span> <span class="pre">const&)lhs).distance_to((Dr2</span> <span class="pre">const&)rhs)</span> <span class="pre"><</span> <span class="pre">0</span></tt>.</p> | |
740 | </dd> | |
741 | <dt>Otherwise,</dt> | |
742 | <dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr2</span> <span class="pre">const&)rhs).distance_to((Dr1</span> <span class="pre">const&)lhs)</span> <span class="pre">></span> <span class="pre">0</span></tt>.</p> | |
743 | </dd> | |
744 | </dl> | |
745 | </td> | |
746 | </tr> | |
747 | </tbody> | |
748 | </table> | |
749 | <pre class="literal-block"> | |
750 | template <class Dr1, class V1, class TC1, class R1, class D1, | |
751 | class Dr2, class V2, class TC2, class R2, class D2> | |
752 | typename enable_if_interoperable<Dr1,Dr2,bool>::type | |
753 | operator <=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, | |
754 | iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); | |
755 | </pre> | |
756 | <table class="docutils field-list" frame="void" rules="none"> | |
757 | <col class="field-name" /> | |
758 | <col class="field-body" /> | |
759 | <tbody valign="top"> | |
760 | <tr class="field"><th class="field-name">Returns:</th><td class="field-body"><p class="first">if <tt class="docutils literal"><span class="pre">is_convertible<Dr2,Dr1>::value</span></tt></p> | |
761 | <dl class="last docutils"> | |
762 | <dt>then</dt> | |
763 | <dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr1</span> <span class="pre">const&)lhs).distance_to((Dr2</span> <span class="pre">const&)rhs)</span> <span class="pre"><=</span> <span class="pre">0</span></tt>.</p> | |
764 | </dd> | |
765 | <dt>Otherwise,</dt> | |
766 | <dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr2</span> <span class="pre">const&)rhs).distance_to((Dr1</span> <span class="pre">const&)lhs)</span> <span class="pre">>=</span> <span class="pre">0</span></tt>.</p> | |
767 | </dd> | |
768 | </dl> | |
769 | </td> | |
770 | </tr> | |
771 | </tbody> | |
772 | </table> | |
773 | <pre class="literal-block"> | |
774 | template <class Dr1, class V1, class TC1, class R1, class D1, | |
775 | class Dr2, class V2, class TC2, class R2, class D2> | |
776 | typename enable_if_interoperable<Dr1,Dr2,bool>::type | |
777 | operator >(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, | |
778 | iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); | |
779 | </pre> | |
780 | <table class="docutils field-list" frame="void" rules="none"> | |
781 | <col class="field-name" /> | |
782 | <col class="field-body" /> | |
783 | <tbody valign="top"> | |
784 | <tr class="field"><th class="field-name">Returns:</th><td class="field-body"><p class="first">if <tt class="docutils literal"><span class="pre">is_convertible<Dr2,Dr1>::value</span></tt></p> | |
785 | <dl class="last docutils"> | |
786 | <dt>then</dt> | |
787 | <dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr1</span> <span class="pre">const&)lhs).distance_to((Dr2</span> <span class="pre">const&)rhs)</span> <span class="pre">></span> <span class="pre">0</span></tt>.</p> | |
788 | </dd> | |
789 | <dt>Otherwise,</dt> | |
790 | <dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr2</span> <span class="pre">const&)rhs).distance_to((Dr1</span> <span class="pre">const&)lhs)</span> <span class="pre"><</span> <span class="pre">0</span></tt>.</p> | |
791 | </dd> | |
792 | </dl> | |
793 | </td> | |
794 | </tr> | |
795 | </tbody> | |
796 | </table> | |
797 | <pre class="literal-block"> | |
798 | template <class Dr1, class V1, class TC1, class R1, class D1, | |
799 | class Dr2, class V2, class TC2, class R2, class D2> | |
800 | typename enable_if_interoperable<Dr1,Dr2,bool>::type | |
801 | operator >=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, | |
802 | iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); | |
803 | </pre> | |
804 | <table class="docutils field-list" frame="void" rules="none"> | |
805 | <col class="field-name" /> | |
806 | <col class="field-body" /> | |
807 | <tbody valign="top"> | |
808 | <tr class="field"><th class="field-name">Returns:</th><td class="field-body"><p class="first">if <tt class="docutils literal"><span class="pre">is_convertible<Dr2,Dr1>::value</span></tt></p> | |
809 | <dl class="last docutils"> | |
810 | <dt>then</dt> | |
811 | <dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr1</span> <span class="pre">const&)lhs).distance_to((Dr2</span> <span class="pre">const&)rhs)</span> <span class="pre">>=</span> <span class="pre">0</span></tt>.</p> | |
812 | </dd> | |
813 | <dt>Otherwise,</dt> | |
814 | <dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr2</span> <span class="pre">const&)rhs).distance_to((Dr1</span> <span class="pre">const&)lhs)</span> <span class="pre"><=</span> <span class="pre">0</span></tt>.</p> | |
815 | </dd> | |
816 | </dl> | |
817 | </td> | |
818 | </tr> | |
819 | </tbody> | |
820 | </table> | |
821 | <pre class="literal-block" id="minus"> | |
822 | template <class Dr1, class V1, class TC1, class R1, class D1, | |
823 | class Dr2, class V2, class TC2, class R2, class D2> | |
824 | typename enable_if_interoperable<Dr1,Dr2,difference>::type | |
825 | operator -(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs, | |
826 | iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs); | |
827 | </pre> | |
828 | <table class="docutils field-list" frame="void" rules="none"> | |
829 | <col class="field-name" /> | |
830 | <col class="field-body" /> | |
831 | <tbody valign="top"> | |
832 | <tr class="field"><th class="field-name">Return Type:</th><td class="field-body"><p class="first">if <tt class="docutils literal"><span class="pre">is_convertible<Dr2,Dr1>::value</span></tt></p> | |
833 | <blockquote> | |
834 | <dl class="docutils"> | |
835 | <dt>then</dt> | |
836 | <dd><p class="first last"><tt class="docutils literal"><span class="pre">difference</span></tt> shall be | |
837 | <tt class="docutils literal"><span class="pre">iterator_traits<Dr1>::difference_type</span></tt>.</p> | |
838 | </dd> | |
839 | <dt>Otherwise</dt> | |
840 | <dd><p class="first last"><tt class="docutils literal"><span class="pre">difference</span></tt> shall be <tt class="docutils literal"><span class="pre">iterator_traits<Dr2>::difference_type</span></tt></p> | |
841 | </dd> | |
842 | </dl> | |
843 | </blockquote> | |
844 | </td> | |
845 | </tr> | |
846 | <tr class="field"><th class="field-name">Returns:</th><td class="field-body"><p class="first">if <tt class="docutils literal"><span class="pre">is_convertible<Dr2,Dr1>::value</span></tt></p> | |
847 | <dl class="last docutils"> | |
848 | <dt>then</dt> | |
849 | <dd><p class="first last"><tt class="docutils literal"><span class="pre">-((Dr1</span> <span class="pre">const&)lhs).distance_to((Dr2</span> <span class="pre">const&)rhs)</span></tt>.</p> | |
850 | </dd> | |
851 | <dt>Otherwise,</dt> | |
852 | <dd><p class="first last"><tt class="docutils literal"><span class="pre">((Dr2</span> <span class="pre">const&)rhs).distance_to((Dr1</span> <span class="pre">const&)lhs)</span></tt>.</p> | |
853 | </dd> | |
854 | </dl> | |
855 | </td> | |
856 | </tr> | |
857 | </tbody> | |
858 | </table> | |
859 | </div> | |
860 | </div> | |
861 | <div class="section" id="tutorial-example"> | |
862 | <h1><a class="toc-backref" href="#id31">Tutorial Example</a></h1> | |
863 | <!-- Copyright David Abrahams 2004. Use, modification and distribution is --> | |
864 | <!-- subject to the Boost Software License, Version 1.0. (See accompanying --> | |
865 | <!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) --> | |
866 | <p>In this section we'll walk through the implementation of a few | |
867 | iterators using <tt class="docutils literal"><span class="pre">iterator_facade</span></tt>, based around the simple | |
868 | example of a linked list of polymorphic objects. This example was | |
869 | inspired by a <a class="reference external" href="http://thread.gmane.org/gmane.comp.lib.boost.user/5100">posting</a> by Keith Macdonald on the <a class="reference external" href="http://www.boost.org/more/mailing_lists.htm#users">Boost-Users</a> | |
870 | mailing list.</p> | |
871 | <div class="section" id="the-problem"> | |
872 | <h2><a class="toc-backref" href="#id32">The Problem</a></h2> | |
873 | <p>Say we've written a polymorphic linked list node base class:</p> | |
874 | <pre class="literal-block"> | |
875 | # include <iostream> | |
876 | ||
877 | struct node_base | |
878 | { | |
879 | node_base() : m_next(0) {} | |
880 | ||
881 | // Each node manages all of its tail nodes | |
882 | virtual ~node_base() { delete m_next; } | |
883 | ||
884 | // Access the rest of the list | |
885 | node_base* next() const { return m_next; } | |
886 | ||
887 | // print to the stream | |
888 | virtual void print(std::ostream& s) const = 0; | |
889 | ||
890 | // double the value | |
891 | virtual void double_me() = 0; | |
892 | ||
893 | void append(node_base* p) | |
894 | { | |
895 | if (m_next) | |
896 | m_next->append(p); | |
897 | else | |
898 | m_next = p; | |
899 | } | |
900 | ||
901 | private: | |
902 | node_base* m_next; | |
903 | }; | |
904 | </pre> | |
905 | <p>Lists can hold objects of different types by linking together | |
906 | specializations of the following template:</p> | |
907 | <pre class="literal-block"> | |
908 | template <class T> | |
909 | struct node : node_base | |
910 | { | |
911 | node(T x) | |
912 | : m_value(x) | |
913 | {} | |
914 | ||
915 | void print(std::ostream& s) const { s << this->m_value; } | |
916 | void double_me() { m_value += m_value; } | |
917 | ||
918 | private: | |
919 | T m_value; | |
920 | }; | |
921 | </pre> | |
922 | <p>And we can print any node using the following streaming operator:</p> | |
923 | <pre class="literal-block"> | |
924 | inline std::ostream& operator<<(std::ostream& s, node_base const& n) | |
925 | { | |
926 | n.print(s); | |
927 | return s; | |
928 | } | |
929 | </pre> | |
930 | <p>Our first challenge is to build an appropriate iterator over these | |
931 | lists.</p> | |
932 | </div> | |
933 | <div class="section" id="a-basic-iterator-using-iterator-facade"> | |
934 | <h2><a class="toc-backref" href="#id33">A Basic Iterator Using <tt class="docutils literal"><span class="pre">iterator_facade</span></tt></a></h2> | |
935 | <p>We will construct a <tt class="docutils literal"><span class="pre">node_iterator</span></tt> class using inheritance from | |
936 | <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> to implement most of the iterator's operations.</p> | |
937 | <pre class="literal-block"> | |
938 | # include "node.hpp" | |
939 | # include <boost/iterator/iterator_facade.hpp> | |
940 | ||
941 | class node_iterator | |
942 | : public boost::iterator_facade<...> | |
943 | { | |
944 | ... | |
945 | }; | |
946 | </pre> | |
947 | <div class="section" id="template-arguments-for-iterator-facade"> | |
948 | <h3><a class="toc-backref" href="#id34">Template Arguments for <tt class="docutils literal"><span class="pre">iterator_facade</span></tt></a></h3> | |
949 | <p><tt class="docutils literal"><span class="pre">iterator_facade</span></tt> has several template parameters, so we must decide | |
950 | what types to use for the arguments. The parameters are <tt class="docutils literal"><span class="pre">Derived</span></tt>, | |
951 | <tt class="docutils literal"><span class="pre">Value</span></tt>, <tt class="docutils literal"><span class="pre">CategoryOrTraversal</span></tt>, <tt class="docutils literal"><span class="pre">Reference</span></tt>, and <tt class="docutils literal"><span class="pre">Difference</span></tt>.</p> | |
952 | <div class="section" id="derived"> | |
953 | <h4><a class="toc-backref" href="#id35"><tt class="docutils literal"><span class="pre">Derived</span></tt></a></h4> | |
954 | <p>Because <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> is meant to be used with the CRTP | |
955 | <a class="citation-reference" href="#cop95" id="id10">[Cop95]</a> the first parameter is the iterator class name itself, | |
956 | <tt class="docutils literal"><span class="pre">node_iterator</span></tt>.</p> | |
957 | </div> | |
958 | <div class="section" id="value"> | |
959 | <h4><a class="toc-backref" href="#id36"><tt class="docutils literal"><span class="pre">Value</span></tt></a></h4> | |
960 | <p>The <tt class="docutils literal"><span class="pre">Value</span></tt> parameter determines the <tt class="docutils literal"><span class="pre">node_iterator</span></tt>'s | |
961 | <tt class="docutils literal"><span class="pre">value_type</span></tt>. In this case, we are iterating over <tt class="docutils literal"><span class="pre">node_base</span></tt> | |
962 | objects, so <tt class="docutils literal"><span class="pre">Value</span></tt> will be <tt class="docutils literal"><span class="pre">node_base</span></tt>.</p> | |
963 | </div> | |
964 | <div class="section" id="categoryortraversal"> | |
965 | <h4><a class="toc-backref" href="#id37"><tt class="docutils literal"><span class="pre">CategoryOrTraversal</span></tt></a></h4> | |
966 | <p>Now we have to determine which <a class="reference external" href="new-iter-concepts.html#iterator-traversal-concepts-lib-iterator-traversal">iterator traversal concept</a> our | |
967 | <tt class="docutils literal"><span class="pre">node_iterator</span></tt> is going to model. Singly-linked lists only have | |
968 | forward links, so our iterator can't can't be a <a class="reference external" href="new-iter-concepts.html#bidirectional-traversal-iterators-lib-bidirectional-traversal-iterators">bidirectional | |
969 | traversal iterator</a>. Our iterator should be able to make multiple | |
970 | passes over the same linked list (unlike, say, an | |
971 | <tt class="docutils literal"><span class="pre">istream_iterator</span></tt> which consumes the stream it traverses), so it | |
972 | must be a <a class="reference external" href="new-iter-concepts.html#forward-traversal-iterators-lib-forward-traversal-iterators">forward traversal iterator</a>. Therefore, we'll pass | |
973 | <tt class="docutils literal"><span class="pre">boost::forward_traversal_tag</span></tt> in this position<a class="footnote-reference" href="#category" id="id11"><sup>1</sup></a>.</p> | |
974 | <table class="docutils footnote" frame="void" id="category" rules="none"> | |
975 | <colgroup><col class="label" /><col /></colgroup> | |
976 | <tbody valign="top"> | |
977 | <tr><td class="label"><a class="fn-backref" href="#id11">[1]</a></td><td><tt class="docutils literal"><span class="pre">iterator_facade</span></tt> also supports old-style category | |
978 | tags, so we could have passed <tt class="docutils literal"><span class="pre">std::forward_iterator_tag</span></tt> here; | |
979 | either way, the resulting iterator's <tt class="docutils literal"><span class="pre">iterator_category</span></tt> will | |
980 | end up being <tt class="docutils literal"><span class="pre">std::forward_iterator_tag</span></tt>.</td></tr> | |
981 | </tbody> | |
982 | </table> | |
983 | </div> | |
984 | <div class="section" id="id12"> | |
985 | <h4><a class="toc-backref" href="#id38"><tt class="docutils literal"><span class="pre">Reference</span></tt></a></h4> | |
986 | <p>The <tt class="docutils literal"><span class="pre">Reference</span></tt> argument becomes the type returned by | |
987 | <tt class="docutils literal"><span class="pre">node_iterator</span></tt>'s dereference operation, and will also be the | |
988 | same as <tt class="docutils literal"><span class="pre">std::iterator_traits<node_iterator>::reference</span></tt>. The | |
989 | library's default for this parameter is <tt class="docutils literal"><span class="pre">Value&</span></tt>; since | |
990 | <tt class="docutils literal"><span class="pre">node_base&</span></tt> is a good choice for the iterator's <tt class="docutils literal"><span class="pre">reference</span></tt> | |
991 | type, we can omit this argument, or pass <tt class="docutils literal"><span class="pre">use_default</span></tt>.</p> | |
992 | </div> | |
993 | <div class="section" id="difference"> | |
994 | <h4><a class="toc-backref" href="#id39"><tt class="docutils literal"><span class="pre">Difference</span></tt></a></h4> | |
995 | <p>The <tt class="docutils literal"><span class="pre">Difference</span></tt> argument determines how the distance between | |
996 | two <tt class="docutils literal"><span class="pre">node_iterator</span></tt>s will be measured and will also be the | |
997 | same as <tt class="docutils literal"><span class="pre">std::iterator_traits<node_iterator>::difference_type</span></tt>. | |
998 | The library's default for <tt class="docutils literal"><span class="pre">Difference</span></tt> is <tt class="docutils literal"><span class="pre">std::ptrdiff_t</span></tt>, an | |
999 | appropriate type for measuring the distance between any two | |
1000 | addresses in memory, and one that works for almost any iterator, | |
1001 | so we can omit this argument, too.</p> | |
1002 | <p>The declaration of <tt class="docutils literal"><span class="pre">node_iterator</span></tt> will therefore look something | |
1003 | like:</p> | |
1004 | <pre class="literal-block"> | |
1005 | # include "node.hpp" | |
1006 | # include <boost/iterator/iterator_facade.hpp> | |
1007 | ||
1008 | class node_iterator | |
1009 | : public boost::iterator_facade< | |
1010 | node_iterator | |
1011 | , node_base | |
1012 | , boost::forward_traversal_tag | |
1013 | > | |
1014 | { | |
1015 | ... | |
1016 | }; | |
1017 | </pre> | |
1018 | </div> | |
1019 | </div> | |
1020 | <div class="section" id="constructors-and-data-members"> | |
1021 | <h3><a class="toc-backref" href="#id40">Constructors and Data Members</a></h3> | |
1022 | <p>Next we need to decide how to represent the iterator's position. | |
1023 | This representation will take the form of data members, so we'll | |
1024 | also need to write constructors to initialize them. The | |
1025 | <tt class="docutils literal"><span class="pre">node_iterator</span></tt>'s position is quite naturally represented using | |
1026 | a pointer to a <tt class="docutils literal"><span class="pre">node_base</span></tt>. We'll need a constructor to build an | |
1027 | iterator from a <tt class="docutils literal"><span class="pre">node_base*</span></tt>, and a default constructor to | |
1028 | satisfy the <a class="reference external" href="new-iter-concepts.html#forward-traversal-iterators-lib-forward-traversal-iterators">forward traversal iterator</a> requirements<a class="footnote-reference" href="#default" id="id13"><sup>2</sup></a>. | |
1029 | Our <tt class="docutils literal"><span class="pre">node_iterator</span></tt> then becomes:</p> | |
1030 | <pre class="literal-block"> | |
1031 | # include "node.hpp" | |
1032 | # include <boost/iterator/iterator_facade.hpp> | |
1033 | ||
1034 | class node_iterator | |
1035 | : public boost::iterator_facade< | |
1036 | node_iterator | |
1037 | , node_base | |
1038 | , boost::forward_traversal_tag | |
1039 | > | |
1040 | { | |
1041 | public: | |
1042 | node_iterator() | |
1043 | : m_node(0) | |
1044 | {} | |
1045 | ||
1046 | explicit node_iterator(node_base* p) | |
1047 | : m_node(p) | |
1048 | {} | |
1049 | ||
1050 | private: | |
1051 | ... | |
1052 | node_base* m_node; | |
1053 | }; | |
1054 | </pre> | |
1055 | <table class="docutils footnote" frame="void" id="default" rules="none"> | |
1056 | <colgroup><col class="label" /><col /></colgroup> | |
1057 | <tbody valign="top"> | |
1058 | <tr><td class="label"><a class="fn-backref" href="#id13">[2]</a></td><td>Technically, the C++ standard places almost no | |
1059 | requirements on a default-constructed iterator, so if we were | |
1060 | really concerned with efficiency, we could've written the | |
1061 | default constructor to leave <tt class="docutils literal"><span class="pre">m_node</span></tt> uninitialized.</td></tr> | |
1062 | </tbody> | |
1063 | </table> | |
1064 | </div> | |
1065 | <div class="section" id="implementing-the-core-operations"> | |
1066 | <h3><a class="toc-backref" href="#id41">Implementing the Core Operations</a></h3> | |
1067 | <p>The last step is to implement the <a class="reference internal" href="#core-operations">core operations</a> required by | |
1068 | the concepts we want our iterator to model. Referring to the | |
1069 | <a class="reference internal" href="#core-operations">table</a>, we can see that the first three rows are applicable | |
1070 | because <tt class="docutils literal"><span class="pre">node_iterator</span></tt> needs to satisfy the requirements for | |
1071 | <a class="reference external" href="new-iter-concepts.html#readable-iterators-lib-readable-iterators">readable iterator</a>, <a class="reference external" href="new-iter-concepts.html#single-pass-iterators-lib-single-pass-iterators">single pass iterator</a>, and <a class="reference external" href="new-iter-concepts.html#incrementable-iterators-lib-incrementable-iterators">incrementable | |
1072 | iterator</a>.</p> | |
1073 | <p>We therefore need to supply <tt class="docutils literal"><span class="pre">dereference</span></tt>, | |
1074 | <tt class="docutils literal"><span class="pre">equal</span></tt>, and <tt class="docutils literal"><span class="pre">increment</span></tt> members. We don't want these members | |
1075 | to become part of <tt class="docutils literal"><span class="pre">node_iterator</span></tt>'s public interface, so we can | |
1076 | make them private and grant friendship to | |
1077 | <tt class="docutils literal"><span class="pre">boost::iterator_core_access</span></tt>, a "back-door" that | |
1078 | <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> uses to get access to the core operations:</p> | |
1079 | <pre class="literal-block"> | |
1080 | # include "node.hpp" | |
1081 | # include <boost/iterator/iterator_facade.hpp> | |
1082 | ||
1083 | class node_iterator | |
1084 | : public boost::iterator_facade< | |
1085 | node_iterator | |
1086 | , node_base | |
1087 | , boost::forward_traversal_tag | |
1088 | > | |
1089 | { | |
1090 | public: | |
1091 | node_iterator() | |
1092 | : m_node(0) {} | |
1093 | ||
1094 | explicit node_iterator(node_base* p) | |
1095 | : m_node(p) {} | |
1096 | ||
1097 | private: | |
1098 | friend class boost::iterator_core_access; | |
1099 | ||
1100 | void increment() { m_node = m_node->next(); } | |
1101 | ||
1102 | bool equal(node_iterator const& other) const | |
1103 | { | |
1104 | return this->m_node == other.m_node; | |
1105 | } | |
1106 | ||
1107 | node_base& dereference() const { return *m_node; } | |
1108 | ||
1109 | node_base* m_node; | |
1110 | }; | |
1111 | </pre> | |
1112 | <p>Voilà; a complete and conforming readable, forward-traversal | |
1113 | iterator! For a working example of its use, see <a class="reference external" href="../example/node_iterator1.cpp">this program</a>.</p> | |
1114 | </div> | |
1115 | </div> | |
1116 | <div class="section" id="a-constant-node-iterator"> | |
1117 | <h2><a class="toc-backref" href="#id42">A constant <tt class="docutils literal"><span class="pre">node_iterator</span></tt></a></h2> | |
1118 | <div class="sidebar"> | |
1119 | <p class="first sidebar-title">Constant and Mutable iterators</p> | |
1120 | <p>The term <strong>mutable iterator</strong> means an iterator through which | |
1121 | the object it references (its "referent") can be modified. A | |
1122 | <strong>constant iterator</strong> is one which doesn't allow modification of | |
1123 | its referent.</p> | |
1124 | <p>The words <em>constant</em> and <em>mutable</em> don't refer to the ability to | |
1125 | modify the iterator itself. For example, an <tt class="docutils literal"><span class="pre">int</span> <span class="pre">const*</span></tt> is a | |
1126 | non-<tt class="docutils literal"><span class="pre">const</span></tt> <em>constant iterator</em>, which can be incremented | |
1127 | but doesn't allow modification of its referent, and <tt class="docutils literal"><span class="pre">int*</span> | |
1128 | <span class="pre">const</span></tt> is a <tt class="docutils literal"><span class="pre">const</span></tt> <em>mutable iterator</em>, which cannot be | |
1129 | modified but which allows modification of its referent.</p> | |
1130 | <p class="last">Confusing? We agree, but those are the standard terms. It | |
1131 | probably doesn't help much that a container's constant iterator | |
1132 | is called <tt class="docutils literal"><span class="pre">const_iterator</span></tt>.</p> | |
1133 | </div> | |
1134 | <p>Now, our <tt class="docutils literal"><span class="pre">node_iterator</span></tt> gives clients access to both <tt class="docutils literal"><span class="pre">node</span></tt>'s <tt class="docutils literal"><span class="pre">print(std::ostream&)</span> <span class="pre">const</span></tt> member function, but also its | |
1135 | mutating <tt class="docutils literal"><span class="pre">double_me()</span></tt> member. If we wanted to build a | |
1136 | <em>constant</em> <tt class="docutils literal"><span class="pre">node_iterator</span></tt>, we'd only have to make three | |
1137 | changes:</p> | |
1138 | <pre class="literal-block"> | |
1139 | class const_node_iterator | |
1140 | : public boost::iterator_facade< | |
1141 | const_node_iterator | |
1142 | , node_base <strong>const</strong> | |
1143 | , boost::forward_traversal_tag | |
1144 | > | |
1145 | { | |
1146 | public: | |
1147 | const_node_iterator() | |
1148 | : m_node(0) {} | |
1149 | ||
1150 | explicit const_node_iterator(node_base* p) | |
1151 | : m_node(p) {} | |
1152 | ||
1153 | private: | |
1154 | friend class boost::iterator_core_access; | |
1155 | ||
1156 | void increment() { m_node = m_node->next(); } | |
1157 | ||
1158 | bool equal(const_node_iterator const& other) const | |
1159 | { | |
1160 | return this->m_node == other.m_node; | |
1161 | } | |
1162 | ||
1163 | node_base <strong>const</strong>& dereference() const { return *m_node; } | |
1164 | ||
1165 | node_base <strong>const</strong>* m_node; | |
1166 | }; | |
1167 | </pre> | |
1168 | <div class="sidebar"> | |
1169 | <p class="first sidebar-title"><tt class="docutils literal"><span class="pre">const</span></tt> and an iterator's <tt class="docutils literal"><span class="pre">value_type</span></tt></p> | |
1170 | <p class="last">The C++ standard requires an iterator's <tt class="docutils literal"><span class="pre">value_type</span></tt> <em>not</em> be | |
1171 | <tt class="docutils literal"><span class="pre">const</span></tt>-qualified, so <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> strips the | |
1172 | <tt class="docutils literal"><span class="pre">const</span></tt> from its <tt class="docutils literal"><span class="pre">Value</span></tt> parameter in order to produce the | |
1173 | iterator's <tt class="docutils literal"><span class="pre">value_type</span></tt>. Making the <tt class="docutils literal"><span class="pre">Value</span></tt> argument | |
1174 | <tt class="docutils literal"><span class="pre">const</span></tt> provides a useful hint to <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> that the | |
1175 | iterator is a <em>constant iterator</em>, and the default <tt class="docutils literal"><span class="pre">Reference</span></tt> | |
1176 | argument will be correct for all lvalue iterators.</p> | |
1177 | </div> | |
1178 | <p>As a matter of fact, <tt class="docutils literal"><span class="pre">node_iterator</span></tt> and <tt class="docutils literal"><span class="pre">const_node_iterator</span></tt> | |
1179 | are so similar that it makes sense to factor the common code out | |
1180 | into a template as follows:</p> | |
1181 | <pre class="literal-block"> | |
1182 | template <class Value> | |
1183 | class node_iter | |
1184 | : public boost::iterator_facade< | |
1185 | node_iter<Value> | |
1186 | , Value | |
1187 | , boost::forward_traversal_tag | |
1188 | > | |
1189 | { | |
1190 | public: | |
1191 | node_iter() | |
1192 | : m_node(0) {} | |
1193 | ||
1194 | explicit node_iter(Value* p) | |
1195 | : m_node(p) {} | |
1196 | ||
1197 | private: | |
1198 | friend class boost::iterator_core_access; | |
1199 | ||
1200 | bool equal(node_iter<Value> const& other) const | |
1201 | { | |
1202 | return this->m_node == other.m_node; | |
1203 | } | |
1204 | ||
1205 | void increment() | |
1206 | { m_node = m_node->next(); } | |
1207 | ||
1208 | Value& dereference() const | |
1209 | { return *m_node; } | |
1210 | ||
1211 | Value* m_node; | |
1212 | }; | |
1213 | typedef node_iter<node_base> node_iterator; | |
1214 | typedef node_iter<node_base const> node_const_iterator; | |
1215 | </pre> | |
1216 | </div> | |
1217 | <div class="section" id="interoperability"> | |
1218 | <h2><a class="toc-backref" href="#id43">Interoperability</a></h2> | |
1219 | <p>Our <tt class="docutils literal"><span class="pre">const_node_iterator</span></tt> works perfectly well on its own, but | |
1220 | taken together with <tt class="docutils literal"><span class="pre">node_iterator</span></tt> it doesn't quite meet | |
1221 | expectations. For example, we'd like to be able to pass a | |
1222 | <tt class="docutils literal"><span class="pre">node_iterator</span></tt> where a <tt class="docutils literal"><span class="pre">node_const_iterator</span></tt> was expected, | |
1223 | just as you can with <tt class="docutils literal"><span class="pre">std::list<int></span></tt>'s <tt class="docutils literal"><span class="pre">iterator</span></tt> and | |
1224 | <tt class="docutils literal"><span class="pre">const_iterator</span></tt>. Furthermore, given a <tt class="docutils literal"><span class="pre">node_iterator</span></tt> and a | |
1225 | <tt class="docutils literal"><span class="pre">node_const_iterator</span></tt> into the same list, we should be able to | |
1226 | compare them for equality.</p> | |
1227 | <p>This expected ability to use two different iterator types together | |
1228 | is known as <a class="reference external" href="new-iter-concepts.html#interoperable-iterators-lib-interoperable-iterators"><strong>interoperability</strong></a>. Achieving interoperability in | |
1229 | our case is as simple as templatizing the <tt class="docutils literal"><span class="pre">equal</span></tt> function and | |
1230 | adding a templatized converting constructor<a class="footnote-reference" href="#broken" id="id16"><sup>3</sup></a><a class="footnote-reference" href="#random" id="id17"><sup>4</sup></a>:</p> | |
1231 | <pre class="literal-block"> | |
1232 | template <class Value> | |
1233 | class node_iter | |
1234 | : public boost::iterator_facade< | |
1235 | node_iter<Value> | |
1236 | , Value | |
1237 | , boost::forward_traversal_tag | |
1238 | > | |
1239 | { | |
1240 | public: | |
1241 | node_iter() | |
1242 | : m_node(0) {} | |
1243 | ||
1244 | explicit node_iter(Value* p) | |
1245 | : m_node(p) {} | |
1246 | ||
1247 | template <class OtherValue> | |
1248 | node_iter(node_iter<OtherValue> const& other) | |
1249 | : m_node(other.m_node) {} | |
1250 | ||
1251 | private: | |
1252 | friend class boost::iterator_core_access; | |
1253 | template <class> friend class node_iter; | |
1254 | ||
1255 | template <class OtherValue> | |
1256 | bool equal(node_iter<OtherValue> const& other) const | |
1257 | { | |
1258 | return this->m_node == other.m_node; | |
1259 | } | |
1260 | ||
1261 | void increment() | |
1262 | { m_node = m_node->next(); } | |
1263 | ||
1264 | Value& dereference() const | |
1265 | { return *m_node; } | |
1266 | ||
1267 | Value* m_node; | |
1268 | }; | |
1269 | typedef impl::node_iterator<node_base> node_iterator; | |
1270 | typedef impl::node_iterator<node_base const> node_const_iterator; | |
1271 | </pre> | |
1272 | <table class="docutils footnote" frame="void" id="broken" rules="none"> | |
1273 | <colgroup><col class="label" /><col /></colgroup> | |
1274 | <tbody valign="top"> | |
1275 | <tr><td class="label"><a class="fn-backref" href="#id16">[3]</a></td><td>If you're using an older compiler and it can't handle | |
1276 | this example, see the <a class="reference external" href="../example/node_iterator2.hpp">example code</a> for workarounds.</td></tr> | |
1277 | </tbody> | |
1278 | </table> | |
1279 | <table class="docutils footnote" frame="void" id="random" rules="none"> | |
1280 | <colgroup><col class="label" /><col /></colgroup> | |
1281 | <tbody valign="top"> | |
1282 | <tr><td class="label"><a class="fn-backref" href="#id17">[4]</a></td><td>If <tt class="docutils literal"><span class="pre">node_iterator</span></tt> had been a <a class="reference external" href="new-iter-concepts.html#random-access-traversal-iterators-lib-random-access-traversal-iterators">random access | |
1283 | traversal iterator</a>, we'd have had to templatize its | |
1284 | <tt class="docutils literal"><span class="pre">distance_to</span></tt> function as well.</td></tr> | |
1285 | </tbody> | |
1286 | </table> | |
1287 | <p>You can see an example program which exercises our interoperable | |
1288 | iterators <a class="reference external" href="../example/node_iterator2.cpp">here</a>.</p> | |
1289 | </div> | |
1290 | <div class="section" id="telling-the-truth"> | |
1291 | <h2><a class="toc-backref" href="#id44">Telling the Truth</a></h2> | |
1292 | <p>Now <tt class="docutils literal"><span class="pre">node_iterator</span></tt> and <tt class="docutils literal"><span class="pre">node_const_iterator</span></tt> behave exactly as | |
1293 | you'd expect... almost. We can compare them and we can convert in | |
1294 | one direction: from <tt class="docutils literal"><span class="pre">node_iterator</span></tt> to <tt class="docutils literal"><span class="pre">node_const_iterator</span></tt>. | |
1295 | If we try to convert from <tt class="docutils literal"><span class="pre">node_const_iterator</span></tt> to | |
1296 | <tt class="docutils literal"><span class="pre">node_iterator</span></tt>, we'll get an error when the converting | |
1297 | constructor tries to initialize <tt class="docutils literal"><span class="pre">node_iterator</span></tt>'s <tt class="docutils literal"><span class="pre">m_node</span></tt>, a | |
1298 | <tt class="docutils literal"><span class="pre">node*</span></tt> with a <tt class="docutils literal"><span class="pre">node</span> <span class="pre">const*</span></tt>. So what's the problem?</p> | |
1299 | <p>The problem is that | |
1300 | <tt class="docutils literal"><span class="pre">boost::</span></tt><a class="reference external" href="../../type_traits/index.html#relationships"><tt class="docutils literal"><span class="pre">is_convertible</span></tt></a><tt class="docutils literal"><span class="pre"><node_const_iterator,node_iterator>::value</span></tt> | |
1301 | will be <tt class="docutils literal"><span class="pre">true</span></tt>, but it should be <tt class="docutils literal"><span class="pre">false</span></tt>. <a class="reference external" href="../../type_traits/index.html#relationships"><tt class="docutils literal"><span class="pre">is_convertible</span></tt></a> | |
1302 | lies because it can only see as far as the <em>declaration</em> of | |
1303 | <tt class="docutils literal"><span class="pre">node_iter</span></tt>'s converting constructor, but can't look inside at | |
1304 | the <em>definition</em> to make sure it will compile. A perfect solution | |
1305 | would make <tt class="docutils literal"><span class="pre">node_iter</span></tt>'s converting constructor disappear when | |
1306 | the <tt class="docutils literal"><span class="pre">m_node</span></tt> conversion would fail.</p> | |
1307 | <p>In fact, that sort of magic is possible using | |
1308 | <a class="reference external" href="../../utility/enable_if.html"><tt class="docutils literal"><span class="pre">boost::enable_if</span></tt></a>. By rewriting the converting constructor as | |
1309 | follows, we can remove it from the overload set when it's not | |
1310 | appropriate:</p> | |
1311 | <pre class="literal-block"> | |
1312 | #include <boost/type_traits/is_convertible.hpp> | |
1313 | #include <boost/utility/enable_if.hpp> | |
1314 | ||
1315 | ... | |
1316 | ||
1317 | private: | |
1318 | struct enabler {}; | |
1319 | ||
1320 | public: | |
1321 | template <class OtherValue> | |
1322 | node_iter( | |
1323 | node_iter<OtherValue> const& other | |
1324 | , typename boost::enable_if< | |
1325 | boost::is_convertible<OtherValue*,Value*> | |
1326 | , enabler | |
1327 | >::type = enabler() | |
1328 | ) | |
1329 | : m_node(other.m_node) {} | |
1330 | </pre> | |
1331 | </div> | |
1332 | <div class="section" id="wrap-up"> | |
1333 | <h2><a class="toc-backref" href="#id45">Wrap Up</a></h2> | |
1334 | <p>This concludes our <tt class="docutils literal"><span class="pre">iterator_facade</span></tt> tutorial, but before you | |
1335 | stop reading we urge you to take a look at <a class="reference external" href="iterator_adaptor.html"><tt class="docutils literal"><span class="pre">iterator_adaptor</span></tt></a>. | |
1336 | There's another way to approach writing these iterators which might | |
1337 | even be superior.</p> | |
1338 | </div> | |
1339 | </div> | |
1340 | </div> | |
1341 | <div class="footer"> | |
1342 | <hr class="footer" /> | |
1343 | <a class="reference external" href="iterator_facade.rst">View document source</a>. | |
1344 | 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. | |
1345 | ||
1346 | </div> | |
1347 | </body> | |
1348 | </html> |