]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | The Boost.Iterator Library |(logo)|__ | |
7 | +++++++++++++++++++++++++++++++++++++++++++++++++ | |
8 | ||
9 | .. |(logo)| image:: ../../../boost.png | |
10 | :alt: Boost | |
11 | ||
12 | __ ../../../index.htm | |
13 | ||
14 | ||
15 | ------------------------------------- | |
16 | ||
17 | ||
18 | :Authors: David Abrahams, Jeremy Siek, Thomas Witt | |
19 | :Contact: dave@boost-consulting.com, jsiek@osl.iu.edu, witt@styleadvisor.com | |
20 | :organizations: `Boost Consulting`_, Indiana University `Open Systems | |
21 | Lab`_, `Zephyr Associates, Inc.`_ | |
22 | :date: $Date$ | |
23 | ||
24 | :copyright: Copyright David Abrahams, Jeremy Siek, 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: The Boost Iterator Library contains two parts. The first | |
31 | is a system of concepts_ which extend the C++ standard | |
32 | iterator requirements. The second is a framework of | |
33 | components for building iterators based on these | |
34 | extended concepts and includes several useful iterator | |
35 | adaptors. The extended iterator concepts have been | |
36 | carefully designed so that old-style iterators | |
37 | can fit in the new concepts and so that new-style | |
38 | iterators will be compatible with old-style algorithms, | |
39 | though algorithms may need to be updated if they want to | |
40 | take full advantage of the new-style iterator | |
41 | capabilities. Several components of this library have | |
42 | been accepted into the C++ standard technical report. | |
43 | The components of the Boost Iterator Library replace the | |
44 | older Boost Iterator Adaptor Library. | |
45 | ||
46 | .. _concepts: http://www.boost.org/more/generic_programming.html#concept | |
47 | ||
48 | .. contents:: **Table of Contents** | |
49 | ||
50 | ||
51 | ------------------------------------- | |
52 | ||
53 | ||
54 | ===================== | |
55 | New-Style Iterators | |
56 | ===================== | |
57 | ||
58 | The iterator categories defined in C++98 are extremely limiting | |
59 | because they bind together two orthogonal concepts: traversal and | |
60 | element access. For example, because a random access iterator is | |
61 | required to return a reference (and not a proxy) when dereferenced, | |
62 | it is impossible to capture the capabilities of | |
63 | ``vector<bool>::iterator`` using the C++98 categories. This is the | |
64 | infamous "``vector<bool>`` is not a container, and its iterators | |
65 | aren't random access iterators", debacle about which Herb Sutter | |
66 | wrote two papers for the standards comittee (n1185_ and n1211_), | |
67 | and a `Guru of the Week`__. New-style iterators go well beyond | |
68 | patching up ``vector<bool>``, though: there are lots of other | |
69 | iterators already in use which can't be adequately represented by | |
70 | the existing concepts. For details about the new iterator | |
71 | concepts, see our | |
72 | ||
73 | .. _n1185: http://www.gotw.ca/publications/N1185.pdf | |
74 | .. _n1211: http://www.gotw.ca/publications/N1211.pdf | |
75 | __ http://www.gotw.ca/gotw/050.htm | |
76 | ||
77 | ||
78 | `Standard Proposal For New-Style Iterators`__ (PDF__) | |
79 | ||
80 | __ new-iter-concepts.html | |
81 | __ new-iter-concepts.pdf | |
82 | ||
83 | ============================= | |
84 | Iterator Facade and Adaptor | |
85 | ============================= | |
86 | ||
87 | Writing standard-conforming iterators is tricky, but the need comes | |
88 | up often. In order to ease the implementation of new iterators, | |
89 | the Boost.Iterator library provides the |facade| class template, | |
90 | which implements many useful defaults and compile-time checks | |
91 | designed to help the iterator author ensure that his iterator is | |
92 | correct. | |
93 | ||
94 | It is also common to define a new iterator that is similar to some | |
95 | underlying iterator or iterator-like type, but that modifies some | |
96 | aspect of the underlying type's behavior. For that purpose, the | |
97 | library supplies the |adaptor| class template, which is specially | |
98 | designed to take advantage of as much of the underlying type's | |
99 | behavior as possible. | |
100 | ||
101 | The documentation for these two classes can be found at the following | |
102 | web pages: | |
103 | ||
104 | * |facade|_ (PDF__) | |
105 | ||
106 | * |adaptor|_ (PDF__) | |
107 | ||
108 | ||
109 | .. |facade| replace:: ``iterator_facade`` | |
110 | .. _facade: iterator_facade.html | |
111 | __ iterator_facade.pdf | |
112 | ||
113 | .. |adaptor| replace:: ``iterator_adaptor`` | |
114 | .. _adaptor: iterator_adaptor.html | |
115 | __ iterator_adaptor.pdf | |
116 | ||
117 | Both |facade| and |adaptor| as well as many of the `specialized | |
118 | adaptors`_ mentioned below have been proposed for standardization, | |
119 | and accepted into the first C++ technical report; see our | |
120 | ||
121 | `Standard Proposal For Iterator Facade and Adaptor`__ (PDF__) | |
122 | ||
123 | for more details. | |
124 | ||
125 | __ facade-and-adaptor.html | |
126 | __ facade-and-adaptor.pdf | |
127 | ||
128 | ====================== | |
129 | Specialized Adaptors | |
130 | ====================== | |
131 | ||
132 | The iterator library supplies a useful suite of standard-conforming | |
133 | iterator templates based on the Boost `iterator facade and adaptor`_. | |
134 | ||
135 | * |counting|_ (PDF__): an iterator over a sequence of consecutive values. | |
136 | Implements a "lazy sequence" | |
137 | ||
138 | * |filter|_ (PDF__): an iterator over the subset of elements of some | |
139 | sequence which satisfy a given predicate | |
140 | ||
141 | * |function_input|_ (PDF__): an input iterator wrapping a generator (nullary | |
142 | function object); each time the iterator is dereferenced, the function object | |
143 | is called to get the value to return. | |
144 | ||
145 | * |function_output|_ (PDF__): an output iterator wrapping a unary function | |
146 | object; each time an element is written into the dereferenced | |
147 | iterator, it is passed as a parameter to the function object. | |
148 | ||
149 | * |indirect|_ (PDF__): an iterator over the objects *pointed-to* by the | |
150 | elements of some sequence. | |
151 | ||
152 | * |permutation|_ (PDF__): an iterator over the elements of some random-access | |
153 | sequence, rearranged according to some sequence of integer indices. | |
154 | ||
155 | * |reverse|_ (PDF__): an iterator which traverses the elements of some | |
156 | bidirectional sequence in reverse. Corrects many of the | |
157 | shortcomings of C++98's ``std::reverse_iterator``. | |
158 | ||
159 | * |shared|_: an iterator over elements of a container whose | |
160 | lifetime is maintained by a |shared_ptr|_ stored in the iterator. | |
161 | ||
162 | * |transform|_ (PDF__): an iterator over elements which are the result of | |
163 | applying some functional transformation to the elements of an | |
164 | underlying sequence. This component also replaces the old | |
165 | ``projection_iterator_adaptor``. | |
166 | ||
167 | * |zip|_ (PDF__): an iterator over tuples of the elements at corresponding | |
168 | positions of heterogeneous underlying iterators. | |
169 | ||
170 | .. |counting| replace:: ``counting_iterator`` | |
171 | .. _counting: counting_iterator.html | |
172 | __ counting_iterator.pdf | |
173 | ||
174 | .. |filter| replace:: ``filter_iterator`` | |
175 | .. _filter: filter_iterator.html | |
176 | __ filter_iterator.pdf | |
177 | ||
178 | .. |function_input| replace:: ``function_input_iterator`` | |
179 | .. _function_input: function_input_iterator.html | |
180 | __ function_input_iterator.pdf | |
181 | ||
182 | .. |function_output| replace:: ``function_output_iterator`` | |
183 | .. _function_output: function_output_iterator.html | |
184 | __ function_output_iterator.pdf | |
185 | ||
186 | .. |indirect| replace:: ``indirect_iterator`` | |
187 | .. _indirect: indirect_iterator.html | |
188 | __ indirect_iterator.pdf | |
189 | ||
190 | .. |permutation| replace:: ``permutation_iterator`` | |
191 | .. _permutation: permutation_iterator.html | |
192 | __ permutation_iterator.pdf | |
193 | ||
194 | .. |reverse| replace:: ``reverse_iterator`` | |
195 | .. _reverse: reverse_iterator.html | |
196 | __ reverse_iterator.pdf | |
197 | ||
198 | .. |shared| replace:: ``shared_container_iterator`` | |
199 | .. _shared: ../../utility/shared_container_iterator.html | |
200 | ||
201 | .. |transform| replace:: ``transform_iterator`` | |
202 | .. _transform: transform_iterator.html | |
203 | __ transform_iterator.pdf | |
204 | ||
205 | .. |zip| replace:: ``zip_iterator`` | |
206 | .. _zip: zip_iterator.html | |
207 | __ zip_iterator.pdf | |
208 | ||
209 | .. |shared_ptr| replace:: ``shared_ptr`` | |
210 | .. _shared_ptr: ../../smart_ptr/shared_ptr.htm | |
211 | ||
212 | ==================== | |
213 | Iterator Utilities | |
214 | ==================== | |
215 | ||
216 | Traits | |
217 | ------ | |
218 | ||
219 | * |pointee|_ (PDF__): Provides the capability to deduce the referent types | |
220 | of pointers, smart pointers and iterators in generic code. Used | |
221 | in |indirect|. | |
222 | ||
223 | * |iterator_traits|_ (PDF__): Provides MPL_\ -compatible metafunctions which | |
224 | retrieve an iterator's traits. Also corrects for the deficiencies | |
225 | of broken implementations of ``std::iterator_traits``. | |
226 | ||
227 | .. * |interoperable|_ (PDF__): Provides an MPL_\ -compatible metafunction for | |
228 | testing iterator interoperability | |
229 | ||
230 | .. |pointee| replace:: ``pointee.hpp`` | |
231 | .. _pointee: pointee.html | |
232 | __ pointee.pdf | |
233 | ||
234 | .. |iterator_traits| replace:: ``iterator_traits.hpp`` | |
235 | .. _iterator_traits: iterator_traits.html | |
236 | __ iterator_traits.pdf | |
237 | ||
238 | .. |interoperable| replace:: ``interoperable.hpp`` | |
239 | .. _interoperable: interoperable.html | |
240 | .. comment! __ interoperable.pdf | |
241 | ||
242 | .. _MPL: ../../mpl/doc/index.html | |
243 | ||
244 | Testing and Concept Checking | |
245 | ---------------------------- | |
246 | ||
247 | * |iterator_concepts|_ (PDF__): Concept checking classes for the new iterator concepts. | |
248 | ||
249 | * |iterator_archetypes|_ (PDF__): Concept archetype classes for the new iterators concepts. | |
250 | ||
251 | .. |iterator_concepts| replace:: ``iterator_concepts.hpp`` | |
252 | .. _iterator_concepts: iterator_concepts.html | |
253 | __ iterator_concepts.pdf | |
254 | ||
255 | .. |iterator_archetypes| replace:: ``iterator_archetypes.hpp`` | |
256 | .. _iterator_archetypes: iterator_archetypes.html | |
257 | __ iterator_archetypes.pdf | |
258 | ||
259 | ======================================================= | |
260 | Upgrading from the old Boost Iterator Adaptor Library | |
261 | ======================================================= | |
262 | ||
263 | .. _Upgrading: | |
264 | ||
265 | If you have been using the old Boost Iterator Adaptor library to | |
266 | implement iterators, you probably wrote a ``Policies`` class which | |
267 | captures the core operations of your iterator. In the new library | |
268 | design, you'll move those same core operations into the body of the | |
269 | iterator class itself. If you were writing a family of iterators, | |
270 | you probably wrote a `type generator`_ to build the | |
271 | ``iterator_adaptor`` specialization you needed; in the new library | |
272 | design you don't need a type generator (though may want to keep it | |
273 | around as a compatibility aid for older code) because, due to the | |
274 | use of the Curiously Recurring Template Pattern (CRTP) [Cop95]_, | |
275 | you can now define the iterator class yourself and acquire | |
276 | functionality through inheritance from ``iterator_facade`` or | |
277 | ``iterator_adaptor``. As a result, you also get much finer control | |
278 | over how your iterator works: you can add additional constructors, | |
279 | or even override the iterator functionality provided by the | |
280 | library. | |
281 | ||
282 | .. _`type generator`: http://www.boost.org/more/generic_programming.html#type_generator | |
283 | ||
284 | If you're looking for the old ``projection_iterator`` component, | |
285 | its functionality has been merged into ``transform_iterator``: as | |
286 | long as the function object's ``result_type`` (or the ``Reference`` | |
287 | template argument, if explicitly specified) is a true reference | |
288 | type, ``transform_iterator`` will behave like | |
289 | ``projection_iterator`` used to. | |
290 | ||
291 | ========= | |
292 | History | |
293 | ========= | |
294 | ||
295 | In 2000 Dave Abrahams was writing an iterator for a container of | |
296 | pointers, which would access the pointed-to elements when | |
297 | dereferenced. Naturally, being a library writer, he decided to | |
298 | generalize the idea and the Boost Iterator Adaptor library was born. | |
299 | Dave was inspired by some writings of Andrei Alexandrescu and chose a | |
300 | policy based design (though he probably didn't capture Andrei's idea | |
301 | very well - there was only one policy class for all the iterator's | |
302 | orthogonal properties). Soon Jeremy Siek realized he would need the | |
303 | library and they worked together to produce a "Boostified" version, | |
304 | which was reviewed and accepted into the library. They wrote a paper | |
305 | and made several important revisions of the code. | |
306 | ||
307 | Eventually, several shortcomings of the older library began to make | |
308 | the need for a rewrite apparent. Dave and Jeremy started working | |
309 | at the Santa Cruz C++ committee meeting in 2002, and had quickly | |
310 | generated a working prototype. At the urging of Mat Marcus, they | |
311 | decided to use the GenVoca/CRTP pattern approach, and moved the | |
312 | policies into the iterator class itself. Thomas Witt expressed | |
313 | interest and became the voice of strict compile-time checking for | |
314 | the project, adding uses of the SFINAE technique to eliminate false | |
315 | converting constructors and operators from the overload set. He | |
316 | also recognized the need for a separate ``iterator_facade``, and | |
317 | factored it out of ``iterator_adaptor``. Finally, after a | |
318 | near-complete rewrite of the prototype, they came up with the | |
319 | library you see today. | |
320 | ||
321 | .. [Cop95] [Coplien, 1995] Coplien, J., Curiously Recurring Template | |
322 | Patterns, C++ Report, February 1995, pp. 24-27. | |
323 | ||
324 | .. | |
325 | LocalWords: Abrahams Siek Witt const bool Sutter's WG int UL LI href Lvalue | |
326 | LocalWords: ReadableIterator WritableIterator SwappableIterator cv pre iter | |
327 | LocalWords: ConstantLvalueIterator MutableLvalueIterator CopyConstructible TR | |
328 | LocalWords: ForwardTraversalIterator BidirectionalTraversalIterator lvalue | |
329 | LocalWords: RandomAccessTraversalIterator dereferenceable Incrementable tmp | |
330 | LocalWords: incrementable xxx min prev inplace png oldeqnew AccessTag struct | |
331 | LocalWords: TraversalTag typename lvalues DWA Hmm JGS |