1
2[library Boost.Iterator
3    [/ version 1.0.1]
4    [authors [Abrahams, David], [Siek, Jeremy], [Witt, Thomas]]
5    [copyright 2003 2005 David Abrahams Jeremy Siek Thomas Witt]
6    [category iterator]
7    [id iterator]
8    [dirname iterator]
9    [purpose
10    ]
11    [license
12        Distributed under the Boost Software License, Version 1.0.
13        (See accompanying file LICENSE_1_0.txt or copy at
14        <ulink url="http://www.boost.org/LICENSE_1_0.txt">
15            http://www.boost.org/LICENSE_1_0.txt
16        </ulink>)
17    ]
18]
19
20[/ QuickBook Document version 1.0 ]
21
22[/  Images   ]
23
24[def _note_               [$images/note.png]]
25[def _alert_              [$images/caution.png]]
26[def _detail_             [$images/note.png]]
27[def _tip_                [$images/tip.png]]
28
29[/  Links   ]
30
31[def _iterator_           [@../../libs/iterator/doc/index.html Boost.Iterator]]
32
33[section:intro Introduction]
34
35[def _concepts_ [@http://www.boost.org/more/generic_programming.html#concept concepts]]
36
37The Boost Iterator Library contains two parts. The first
38is a system of _concepts_ which extend the C++ standard
39iterator requirements. The second is a framework of
40components for building iterators based on these
41extended concepts and includes several useful iterator
42adaptors. The extended iterator concepts have been
43carefully designed so that old-style iterators
44can fit in the new concepts and so that new-style
45iterators will be compatible with old-style algorithms,
46though algorithms may need to be updated if they want to
47take full advantage of the new-style iterator
48capabilities.  Several components of this library have
49been accepted into the C++ standard technical report.
50The components of the Boost Iterator Library replace the
51older Boost Iterator Adaptor Library.
52
53
54[h2 New-Style Iterators]
55
56[def _N1185_      [@http://www.gotw.ca/publications/N1185.pdf N1185]]
57[def _N1211_      [@http://www.gotw.ca/publications/N1211.pdf N1211]]
58[def _GOTW_50_    [@http://www.gotw.ca/gotw/050.htm Guru of the Week]]
59
60The iterator categories defined in C++98 are extremely limiting
61because they bind together two orthogonal concepts: traversal and
62element access.  For example, because a random access iterator is
63required to return a reference (and not a proxy) when dereferenced,
64it is impossible to capture the capabilities of
65`vector<bool>::iterator` using the C++98 categories.  This is the
66infamous "`vector<bool>` is not a container, and its iterators
67aren't random access iterators", debacle about which Herb Sutter
68wrote two papers for the standards comittee (_N1185_ and _N1211_),
69and a _GOTW_50_.  New-style iterators go well beyond
70patching up `vector<bool>`, though: there are lots of other
71iterators already in use which can't be adequately represented by
72the existing concepts.  For details about the new iterator
73concepts, see our [@./new-iter-concepts.html Standard Proposal for New-Style Iterators].
74
75[h2 Iterator Facade and Adaptor]
76
77[def _facade_ [@./iterator_facade.html facade]]
78[def _adaptor_ [@./iterator_adaptor.html adaptor]]
79
80Writing standard-conforming iterators is tricky, but the need comes
81up often.  In order to ease the implementation of new iterators,
82the Boost.Iterator library provides the _facade_ class template,
83which implements many useful defaults and compile-time checks
84designed to help the iterator author ensure that his iterator is
85correct.
86
87It is also common to define a new iterator that is similar to some
88underlying iterator or iterator-like type, but that modifies some
89aspect of the underlying type's behavior.  For that purpose, the
90library supplies the _adaptor_ class template, which is specially
91designed to take advantage of as much of the underlying type's
92behavior as possible.
93
94Both _facade_ and _adaptor_ as well as many of the `specialized
95adaptors`_ mentioned below have been proposed for standardization
96([@./facade-and-adaptor.html Standard Proposal For Iterator Facade and Adaptor]).
97
98[h2 Specialized Adaptors]
99
100The iterator library supplies a useful suite of standard-conforming
101iterator templates based on the Boost [link
102intro.iterator_facade_and_adaptor iterator facade and adaptor]
103templates.
104
105[def _counting_    [@./counting_iterator.html         `counting_iterator`]]
106[def _filter_      [@./filter_iterator.html           `filter_iterator`]]
107[def _function_    [@./function_output_iterator.html  `function_output_iterator`]]
108[def _indirect_    [@./indirect_iterator.html         `indirect_iterator`]]
109[def _permutation_ [@./permutation_iterator.html      `permutation_iterator`]]
110[def _reverse_     [@./reverse_iterator.html          `reverse_iterator`]]
111[def _shared_      [@./shared_container_iterator.html `shared_container_iterator`]]
112[def _transform_   [@./transform_iterator.html        `transform_iterator`]]
113[def _zip_         [@./zip_iterator.html              `zip_iterator`]]
114
115[def _shared_ptr_  [@../../smart_ptr/shared_ptr.htm `shared_ptr`]]
116
117* _counting_: an iterator over a sequence of consecutive values.
118  Implements a "lazy sequence"
119
120* _filter_: an iterator over the subset of elements of some
121  sequence which satisfy a given predicate
122
123* _function_: an output iterator wrapping a unary function
124  object; each time an element is written into the dereferenced
125  iterator, it is passed as a parameter to the function object.
126
127* _indirect_: an iterator over the objects *pointed-to* by the
128  elements of some sequence.
129
130* _permutation_: an iterator over the elements of some random-access
131  sequence, rearranged according to some sequence of integer indices.
132
133* _reverse_: an iterator which traverses the elements of some
134  bidirectional sequence in reverse.  Corrects many of the
135  shortcomings of C++98's ``std::reverse_iterator``.
136
137* _shared_: an iterator over elements of a container whose
138  lifetime is maintained by a _shared_ptr_ stored in the iterator.
139
140* _transform_: an iterator over elements which are the result of
141  applying some functional transformation to the elements of an
142  underlying sequence.  This component also replaces the old
143  ``projection_iterator_adaptor``.
144
145* _zip_: an iterator over tuples of the elements at corresponding
146  positions of heterogeneous underlying iterators.
147
148[h2 Iterator Utilities]
149
150[h3 Traits]
151
152[def _pointee_          [@./pointee.html         `pointee.hpp`]]
153[def _iterator_traits_  [@./iterator_traits.html `iterator_traits.hpp`]]
154[def _interoperable_    [@./interoperable.html   `interoperable.hpp`]]
155[def _MPL_              [@../../mpl/doc/index.html   [*MPL]]]
156
157* _pointee_: Provides the capability to deduce the referent types
158  of pointers, smart pointers and iterators in generic code.  Used
159  in _indirect_.
160
161* _iterator_traits_: Provides _MPL_ compatible metafunctions which
162  retrieve an iterator's traits.  Also corrects for the deficiencies
163  of broken implementations of `std::iterator_traits`.
164
165[\ * |interoperable|_ (PDF__): Provides an _MPL_ compatible metafunction for
166     testing iterator interoperability
167]
168
169[h3 Testing and Concept Checking]
170
171[def _iterator_concepts_  [@./iterator_concepts.html `iterator_concepts.hpp`]]
172[def _iterator_archetypes_  [@./iterator_archetypes.html `iterator_archetypes.hpp`]]
173
174* _iterator_concepts_: Concept checking classes for the new iterator concepts.
175
176* _iterator_archetypes_: Concept archetype classes for the new iterators concepts.
177
178[endsect]
179
180[include concepts.qbk]
181
182[section:generic Generic Iterators]
183
184[include facade.qbk]
185
186[include adaptor.qbk]
187
188[endsect]
189
190[include specialized_adaptors.qbk]
191
192[section:utilities Utilities]
193
194[include archetypes.qbk]
195
196[include concept_checking.qbk]
197
198[include traits.qbk]
199
200[include utilities.qbk]
201
202[endsect]
203
204[section:upgrading Upgrading from the old Boost Iterator Adaptor Library]
205
206[def _type_generator_ [@http://www.boost.org/more/generic_programming.html#type_generator type generator]]
207
208If you have been using the old Boost Iterator Adaptor library to
209implement iterators, you probably wrote a `Policies` class which
210captures the core operations of your iterator.  In the new library
211design, you'll move those same core operations into the body of the
212iterator class itself.  If you were writing a family of iterators,
213you probably wrote a _type_generator_ to build the
214`iterator_adaptor` specialization you needed; in the new library
215design you don't need a type generator (though may want to keep it
216around as a compatibility aid for older code) because, due to the
217use of the Curiously Recurring Template Pattern (CRTP) [Cop95]_,
218you can now define the iterator class yourself and acquire
219functionality through inheritance from `iterator_facade` or
220`iterator_adaptor`.  As a result, you also get much finer control
221over how your iterator works: you can add additional constructors,
222or even override the iterator functionality provided by the
223library.
224
225
226If you're looking for the old `projection_iterator` component,
227its functionality has been merged into _transform_iterator_: as
228long as the function object's `result_type` (or the `Reference`
229template argument, if explicitly specified) is a true reference
230type, _transform_iterator_ will behave like
231`projection_iterator` used to.
232
233[endsect]
234
235[section:history History]
236
237In 2000 Dave Abrahams was writing an iterator for a container of
238pointers, which would access the pointed-to elements when
239dereferenced.  Naturally, being a library writer, he decided to
240generalize the idea and the Boost Iterator Adaptor library was born.
241Dave was inspired by some writings of Andrei Alexandrescu and chose a
242policy based design (though he probably didn't capture Andrei's idea
243very well - there was only one policy class for all the iterator's
244orthogonal properties).  Soon Jeremy Siek realized he would need the
245library and they worked together to produce a "Boostified" version,
246which was reviewed and accepted into the library.  They wrote a paper
247and made several important revisions of the code.
248
249Eventually, several shortcomings of the older library began to make
250the need for a rewrite apparent.  Dave and Jeremy started working
251at the Santa Cruz C++ committee meeting in 2002, and had quickly
252generated a working prototype.  At the urging of Mat Marcus, they
253decided to use the GenVoca/CRTP pattern approach, and moved the
254policies into the iterator class itself.  Thomas Witt expressed
255interest and became the voice of strict compile-time checking for
256the project, adding uses of the SFINAE technique to eliminate false
257converting constructors and operators from the overload set.  He
258also recognized the need for a separate `iterator_facade`, and
259factored it out of `iterator_adaptor`.  Finally, after a
260near-complete rewrite of the prototype, they came up with the
261library you see today.
262
263[:\[Coplien, 1995\] Coplien, J., Curiously Recurring Template
264   Patterns, C++ Report, February 1995, pp. 24-27.]
265
266[endsect]
267
268