]>
Commit | Line | Data |
---|---|---|
1 | .. Distributed under the Boost | |
2 | .. Software License, Version 1.0. (See accompanying | |
3 | .. file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
4 | ||
5 | +++++++++++++++++++++++++++++ | |
6 | Iterator Facade and Adaptor | |
7 | +++++++++++++++++++++++++++++ | |
8 | ||
9 | :Author: David Abrahams, Jeremy Siek, Thomas Witt | |
10 | :Contact: dave@boost-consulting.com, jsiek@osl.iu.edu, witt@styleadvisor.com | |
11 | :organization: `Boost Consulting`_, Indiana University `Open Systems | |
12 | Lab`_, `Zephyr Associates, Inc.`_ | |
13 | :date: $Date$ | |
14 | ||
15 | :Number: This is a revised version of N1530_\ =03-0113, which was | |
16 | accepted for Technical Report 1 by the C++ standard | |
17 | committee's library working group. | |
18 | ||
19 | .. Version 1.9 of this ReStructuredText document corresponds to | |
20 | n1530_, the paper accepted by the LWG. | |
21 | ||
22 | .. _n1530: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1530.html | |
23 | ||
24 | :copyright: Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003. | |
25 | ||
26 | .. _`Boost Consulting`: http://www.boost-consulting.com | |
27 | .. _`Open Systems Lab`: http://www.osl.iu.edu | |
28 | .. _`Zephyr Associates, Inc.`: http://www.styleadvisor.com | |
29 | ||
30 | :abstract: We propose a set of class templates that help programmers | |
31 | build standard-conforming iterators, both from scratch and | |
32 | by adapting other iterators. | |
33 | ||
34 | .. contents:: Table of Contents | |
35 | ||
36 | ============ | |
37 | Motivation | |
38 | ============ | |
39 | ||
40 | Iterators play an important role in modern C++ programming. The | |
41 | iterator is the central abstraction of the algorithms of the Standard | |
42 | Library, allowing algorithms to be re-used in in a wide variety of | |
43 | contexts. The C++ Standard Library contains a wide variety of useful | |
44 | iterators. Every one of the standard containers comes with constant | |
45 | and mutable iterators [#mutable]_, and also reverse versions of those | |
46 | same iterators which traverse the container in the opposite direction. | |
47 | The Standard also supplies ``istream_iterator`` and | |
48 | ``ostream_iterator`` for reading from and writing to streams, | |
49 | ``insert_iterator``, ``front_insert_iterator`` and | |
50 | ``back_insert_iterator`` for inserting elements into containers, and | |
51 | ``raw_storage_iterator`` for initializing raw memory [7]. | |
52 | ||
53 | Despite the many iterators supplied by the Standard Library, obvious | |
54 | and useful iterators are missing, and creating new iterator types is | |
55 | still a common task for C++ programmers. The literature documents | |
56 | several of these, for example line_iterator [3] and Constant_iterator | |
57 | [9]. The iterator abstraction is so powerful that we expect | |
58 | programmers will always need to invent new iterator types. | |
59 | ||
60 | Although it is easy to create iterators that *almost* conform to the | |
61 | standard, the iterator requirements contain subtleties which can make | |
62 | creating an iterator which *actually* conforms quite difficult. | |
63 | Further, the iterator interface is rich, containing many operators | |
64 | that are technically redundant and tedious to implement. To automate | |
65 | the repetitive work of constructing iterators, we propose | |
66 | ``iterator_facade``, an iterator base class template which provides | |
67 | the rich interface of standard iterators and delegates its | |
68 | implementation to member functions of the derived class. In addition | |
69 | to reducing the amount of code necessary to create an iterator, the | |
70 | ``iterator_facade`` also provides compile-time error detection. | |
71 | Iterator implementation mistakes that often go unnoticed are turned | |
72 | into compile-time errors because the derived class implementation must | |
73 | match the expectations of the ``iterator_facade``. | |
74 | ||
75 | A common pattern of iterator construction is the adaptation of one | |
76 | iterator to form a new one. The functionality of an iterator is | |
77 | composed of four orthogonal aspects: traversal, indirection, equality | |
78 | comparison and distance measurement. Adapting an old iterator to | |
79 | create a new one often saves work because one can reuse one aspect of | |
80 | functionality while redefining the other. For example, the Standard | |
81 | provides ``reverse_iterator``, which adapts any Bidirectional Iterator | |
82 | by inverting its direction of traversal. As with plain iterators, | |
83 | iterator adaptors defined outside the Standard have become commonplace | |
84 | in the literature: | |
85 | ||
86 | * Checked iter[13] adds bounds-checking to an existing iterator. | |
87 | ||
88 | * The iterators of the View Template Library[14], which adapts | |
89 | containers, are themselves adaptors over the underlying iterators. | |
90 | ||
91 | * Smart iterators [5] adapt an iterator's dereferencing behavior by | |
92 | applying a function object to the object being referenced and | |
93 | returning the result. | |
94 | ||
95 | * Custom iterators [4], in which a variety of adaptor types are enumerated. | |
96 | ||
97 | * Compound iterators [1], which access a slice out of a container of containers. | |
98 | ||
99 | * Several iterator adaptors from the MTL [12]. The MTL contains a | |
100 | strided iterator, where each call to ``operator++()`` moves the | |
101 | iterator ahead by some constant factor, and a scaled iterator, which | |
102 | multiplies the dereferenced value by some constant. | |
103 | ||
104 | .. [#concept] We use the term concept to mean a set of requirements | |
105 | that a type must satisfy to be used with a particular template | |
106 | parameter. | |
107 | ||
108 | .. [#mutable] The term mutable iterator refers to iterators over objects that | |
109 | can be changed by assigning to the dereferenced iterator, while | |
110 | constant iterator refers to iterators over objects that cannot be | |
111 | modified. | |
112 | ||
113 | To fulfill the need for constructing adaptors, we propose the | |
114 | ``iterator_adaptor`` class template. Instantiations of | |
115 | ``iterator_adaptor`` serve as a base classes for new iterators, | |
116 | providing the default behavior of forwarding all operations to the | |
117 | underlying iterator. The user can selectively replace these features | |
118 | in the derived iterator class. This proposal also includes a number | |
119 | of more specialized adaptors, such as the ``transform_iterator`` that | |
120 | applies some user-specified function during the dereference of the | |
121 | iterator. | |
122 | ||
123 | ======================== | |
124 | Impact on the Standard | |
125 | ======================== | |
126 | ||
127 | This proposal is purely an addition to the C++ standard library. | |
128 | However, note that this proposal relies on the proposal for New | |
129 | Iterator Concepts. | |
130 | ||
131 | ======== | |
132 | Design | |
133 | ======== | |
134 | ||
135 | Iterator Concepts | |
136 | ================= | |
137 | ||
138 | This proposal is formulated in terms of the new ``iterator concepts`` | |
139 | as proposed in n1550_, since user-defined and especially adapted | |
140 | iterators suffer from the well known categorization problems that are | |
141 | inherent to the current iterator categories. | |
142 | ||
143 | .. _n1550: http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2003/n1550.htm | |
144 | ||
145 | This proposal does not strictly depend on proposal n1550_, as there | |
146 | is a direct mapping between new and old categories. This proposal | |
147 | could be reformulated using this mapping if n1550_ was not accepted. | |
148 | ||
149 | Interoperability | |
150 | ================ | |
151 | ||
152 | The question of iterator interoperability is poorly addressed in the | |
153 | current standard. There are currently two defect reports that are | |
154 | concerned with interoperability issues. | |
155 | ||
156 | Issue 179_ concerns the fact that mutable container iterator types | |
157 | are only required to be convertible to the corresponding constant | |
158 | iterator types, but objects of these types are not required to | |
159 | interoperate in comparison or subtraction expressions. This situation | |
160 | is tedious in practice and out of line with the way built in types | |
161 | work. This proposal implements the proposed resolution to issue | |
162 | 179_, as most standard library implementations do nowadays. In other | |
163 | words, if an iterator type A has an implicit or user defined | |
164 | conversion to an iterator type B, the iterator types are interoperable | |
165 | and the usual set of operators are available. | |
166 | ||
167 | Issue 280_ concerns the current lack of interoperability between | |
168 | reverse iterator types. The proposed new reverse_iterator template | |
169 | fixes the issues raised in 280. It provides the desired | |
170 | interoperability without introducing unwanted overloads. | |
171 | ||
172 | .. _179: http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#179 | |
173 | .. _280: http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#280 | |
174 | ||
175 | ||
176 | Iterator Facade | |
177 | =============== | |
178 | ||
179 | .. include:: iterator_facade_body.rst | |
180 | ||
181 | Iterator Adaptor | |
182 | ================ | |
183 | ||
184 | .. include:: iterator_adaptor_body.rst | |
185 | ||
186 | Specialized Adaptors | |
187 | ==================== | |
188 | ||
189 | This proposal also contains several examples of specialized adaptors | |
190 | which were easily implemented using ``iterator_adaptor``: | |
191 | ||
192 | * ``indirect_iterator``, which iterates over iterators, pointers, | |
193 | or smart pointers and applies an extra level of dereferencing. | |
194 | ||
195 | * A new ``reverse_iterator``, which inverts the direction of a Base | |
196 | iterator's motion, while allowing adapted constant and mutable | |
197 | iterators to interact in the expected ways (unlike those in most | |
198 | implementations of C++98). | |
199 | ||
200 | * ``transform_iterator``, which applies a user-defined function object | |
201 | to the underlying values when dereferenced. | |
202 | ||
203 | * ``filter_iterator``, which provides a view of an iterator range in | |
204 | which some elements of the underlying range are skipped. | |
205 | ||
206 | .. _counting: | |
207 | ||
208 | * ``counting_iterator``, which adapts any incrementable type | |
209 | (e.g. integers, iterators) so that incrementing/decrementing the | |
210 | adapted iterator and dereferencing it produces successive values of | |
211 | the Base type. | |
212 | ||
213 | * ``function_output_iterator``, which makes it easier to create custom | |
214 | output iterators. | |
215 | ||
216 | Based on examples in the Boost library, users have generated many new | |
217 | adaptors, among them a permutation adaptor which applies some | |
218 | permutation to a random access iterator, and a strided adaptor, which | |
219 | adapts a random access iterator by multiplying its unit of motion by a | |
220 | constant factor. In addition, the Boost Graph Library (BGL) uses | |
221 | iterator adaptors to adapt other graph libraries, such as LEDA [10] | |
222 | and Stanford GraphBase [8], to the BGL interface (which requires C++ | |
223 | Standard compliant iterators). | |
224 | ||
225 | =============== | |
226 | Proposed Text | |
227 | =============== | |
228 | ||
229 | ||
230 | Header ``<iterator_helper>`` synopsis [lib.iterator.helper.synopsis] | |
231 | ======================================================================= | |
232 | ||
233 | ||
234 | :: | |
235 | ||
236 | struct use_default; | |
237 | ||
238 | struct iterator_core_access { /* implementation detail */ }; | |
239 | ||
240 | template < | |
241 | class Derived | |
242 | , class Value | |
243 | , class CategoryOrTraversal | |
244 | , class Reference = Value& | |
245 | , class Difference = ptrdiff_t | |
246 | > | |
247 | class iterator_facade; | |
248 | ||
249 | template < | |
250 | class Derived | |
251 | , class Base | |
252 | , class Value = use_default | |
253 | , class CategoryOrTraversal = use_default | |
254 | , class Reference = use_default | |
255 | , class Difference = use_default | |
256 | > | |
257 | class iterator_adaptor; | |
258 | ||
259 | template < | |
260 | class Iterator | |
261 | , class Value = use_default | |
262 | , class CategoryOrTraversal = use_default | |
263 | , class Reference = use_default | |
264 | , class Difference = use_default | |
265 | > | |
266 | class indirect_iterator; | |
267 | ||
268 | template <class Dereferenceable> | |
269 | struct pointee; | |
270 | ||
271 | template <class Dereferenceable> | |
272 | struct indirect_reference; | |
273 | ||
274 | template <class Iterator> | |
275 | class reverse_iterator; | |
276 | ||
277 | template < | |
278 | class UnaryFunction | |
279 | , class Iterator | |
280 | , class Reference = use_default | |
281 | , class Value = use_default | |
282 | > | |
283 | class transform_iterator; | |
284 | ||
285 | template <class Predicate, class Iterator> | |
286 | class filter_iterator; | |
287 | ||
288 | template < | |
289 | class Incrementable | |
290 | , class CategoryOrTraversal = use_default | |
291 | , class Difference = use_default | |
292 | > | |
293 | class counting_iterator; | |
294 | ||
295 | template <class UnaryFunction> | |
296 | class function_output_iterator; | |
297 | ||
298 | ||
299 | ||
300 | Iterator facade [lib.iterator.facade] | |
301 | ===================================== | |
302 | ||
303 | .. include:: iterator_facade_abstract.rst | |
304 | ||
305 | Class template ``iterator_facade`` | |
306 | ---------------------------------- | |
307 | ||
308 | .. include:: iterator_facade_ref.rst | |
309 | ||
310 | Iterator adaptor [lib.iterator.adaptor] | |
311 | ======================================= | |
312 | ||
313 | .. include:: iterator_adaptor_abstract.rst | |
314 | ||
315 | Class template ``iterator_adaptor`` | |
316 | ----------------------------------- | |
317 | ||
318 | .. include:: iterator_adaptor_ref.rst | |
319 | ||
320 | ||
321 | Specialized adaptors [lib.iterator.special.adaptors] | |
322 | ==================================================== | |
323 | ||
324 | ||
325 | The ``enable_if_convertible<X,Y>::type`` expression used in | |
326 | this section is for exposition purposes. The converting constructors | |
327 | for specialized adaptors should be only be in an overload set provided | |
328 | that an object of type ``X`` is implicitly convertible to an object of | |
329 | type ``Y``. | |
330 | The signatures involving ``enable_if_convertible`` should behave | |
331 | *as-if* ``enable_if_convertible`` were defined to be:: | |
332 | ||
333 | template <bool> enable_if_convertible_impl | |
334 | {}; | |
335 | ||
336 | template <> enable_if_convertible_impl<true> | |
337 | { struct type; }; | |
338 | ||
339 | template<typename From, typename To> | |
340 | struct enable_if_convertible | |
341 | : enable_if_convertible_impl<is_convertible<From,To>::value> | |
342 | {}; | |
343 | ||
344 | If an expression other than the default argument is used to supply | |
345 | the value of a function parameter whose type is written in terms | |
346 | of ``enable_if_convertible``, the program is ill-formed, no | |
347 | diagnostic required. | |
348 | ||
349 | [*Note:* The ``enable_if_convertible`` approach uses SFINAE to | |
350 | take the constructor out of the overload set when the types are not | |
351 | implicitly convertible. | |
352 | ] | |
353 | ||
354 | ||
355 | Indirect iterator | |
356 | ----------------- | |
357 | ||
358 | .. include:: indirect_iterator_abstract.rst | |
359 | ||
360 | Class template ``pointee`` | |
361 | .................................... | |
362 | ||
363 | .. include:: pointee_ref.rst | |
364 | ||
365 | Class template ``indirect_reference`` | |
366 | ..................................... | |
367 | ||
368 | .. include:: indirect_reference_ref.rst | |
369 | ||
370 | Class template ``indirect_iterator`` | |
371 | .................................... | |
372 | ||
373 | .. include:: indirect_iterator_ref.rst | |
374 | ||
375 | Reverse iterator | |
376 | ---------------- | |
377 | ||
378 | .. include:: reverse_iterator_abstract.rst | |
379 | ||
380 | Class template ``reverse_iterator`` | |
381 | ................................... | |
382 | ||
383 | .. include:: reverse_iterator_ref.rst | |
384 | ||
385 | ||
386 | Transform iterator | |
387 | ------------------ | |
388 | ||
389 | .. include:: transform_iterator_abstract.rst | |
390 | ||
391 | Class template ``transform_iterator`` | |
392 | ..................................... | |
393 | ||
394 | .. include:: transform_iterator_ref.rst | |
395 | ||
396 | ||
397 | Filter iterator | |
398 | --------------- | |
399 | ||
400 | .. include:: filter_iterator_abstract.rst | |
401 | ||
402 | ||
403 | Class template ``filter_iterator`` | |
404 | .................................. | |
405 | ||
406 | .. include:: filter_iterator_ref.rst | |
407 | ||
408 | ||
409 | Counting iterator | |
410 | ----------------- | |
411 | ||
412 | .. include:: counting_iterator_abstract.rst | |
413 | ||
414 | Class template ``counting_iterator`` | |
415 | .................................... | |
416 | ||
417 | .. include:: counting_iterator_ref.rst | |
418 | ||
419 | ||
420 | Function output iterator | |
421 | ------------------------ | |
422 | ||
423 | .. include:: func_output_iter_abstract.rst | |
424 | ||
425 | Class template ``function_output_iterator`` | |
426 | ........................................... | |
427 | ||
428 | .. include:: func_output_iter_ref.rst | |
429 | ||
430 | ||
431 | ||
432 | ||
433 | .. LocalWords: Abrahams Siek Witt istream ostream iter MTL strided interoperate | |
434 | LocalWords: CRTP metafunctions inlining lvalue JGS incrementable BGL LEDA cv | |
435 | LocalWords: GraphBase struct ptrdiff UnaryFunction const int typename bool pp | |
436 | LocalWords: lhs rhs SFINAE markup iff tmp OtherDerived OtherIterator DWA foo | |
437 | LocalWords: dereferenceable subobject AdaptableUnaryFunction impl pre ifdef'd | |
438 | LocalWords: OtherIncrementable Coplien |