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
58The iterator categories defined in C++98 are extremely limiting
59because they bind together two orthogonal concepts: traversal and
60element access.  For example, because a random access iterator is
61required to return a reference (and not a proxy) when dereferenced,
62it is impossible to capture the capabilities of
63``vector<bool>::iterator`` using the C++98 categories.  This is the
64infamous "``vector<bool>`` is not a container, and its iterators
65aren't random access iterators", debacle about which Herb Sutter
66wrote two papers for the standards comittee (n1185_ and n1211_),
67and a `Guru of the Week`__.  New-style iterators go well beyond
68patching up ``vector<bool>``, though: there are lots of other
69iterators already in use which can't be adequately represented by
70the existing concepts.  For details about the new iterator
71concepts, 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
87Writing standard-conforming iterators is tricky, but the need comes
88up often.  In order to ease the implementation of new iterators,
89the Boost.Iterator library provides the |facade| class template,
90which implements many useful defaults and compile-time checks
91designed to help the iterator author ensure that his iterator is
92correct.
93
94It is also common to define a new iterator that is similar to some
95underlying iterator or iterator-like type, but that modifies some
96aspect of the underlying type's behavior.  For that purpose, the
97library supplies the |adaptor| class template, which is specially
98designed to take advantage of as much of the underlying type's
99behavior as possible.
100
101The documentation for these two classes can be found at the following
102web 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
117Both |facade| and |adaptor| as well as many of the `specialized
118adaptors`_ mentioned below have been proposed for standardization;
119see our
120
121   `Standard Proposal For Iterator Facade and Adaptor`__ (PDF__)
122
123for more details.
124
125__ facade-and-adaptor.html
126__ facade-and-adaptor.pdf
127
128======================
129 Specialized Adaptors
130======================
131
132The iterator library supplies a useful suite of standard-conforming
133iterator 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* |generator|_: an input iterator wrapping a generator (nullary
150  function object); each time the iterator is dereferenced, the function object
151  is called to get the value to return. This is an outdated analogue of |function_input|_.
152
153* |indirect|_ (PDF__): an iterator over the objects *pointed-to* by the
154  elements of some sequence.
155
156* |permutation|_ (PDF__): an iterator over the elements of some random-access
157  sequence, rearranged according to some sequence of integer indices.
158
159* |reverse|_ (PDF__): an iterator which traverses the elements of some
160  bidirectional sequence in reverse.  Corrects many of the
161  shortcomings of C++98's ``std::reverse_iterator``.
162
163* |shared|_: an iterator over elements of a container whose
164  lifetime is maintained by a |shared_ptr|_ stored in the iterator.
165
166* |transform|_ (PDF__): an iterator over elements which are the result of
167  applying some functional transformation to the elements of an
168  underlying sequence.  This component also replaces the old
169  ``projection_iterator_adaptor``.
170
171* |zip|_ (PDF__): an iterator over tuples of the elements at corresponding
172  positions of heterogeneous underlying iterators.
173
174.. |counting| replace:: ``counting_iterator``
175.. _counting: counting_iterator.html
176__ counting_iterator.pdf
177
178.. |filter| replace:: ``filter_iterator``
179.. _filter: filter_iterator.html
180__ filter_iterator.pdf
181
182.. |function_input| replace:: ``function_input_iterator``
183.. _function_input: function_input_iterator.html
184__ function_input_iterator.pdf
185
186.. |function_output| replace:: ``function_output_iterator``
187.. _function_output: function_output_iterator.html
188__ function_output_iterator.pdf
189
190.. |generator| replace:: ``generator_iterator``
191.. _generator: generator_iterator.htm
192
193.. |indirect| replace:: ``indirect_iterator``
194.. _indirect: indirect_iterator.html
195__ indirect_iterator.pdf
196
197.. |permutation| replace:: ``permutation_iterator``
198.. _permutation: permutation_iterator.html
199__ permutation_iterator.pdf
200
201.. |reverse| replace:: ``reverse_iterator``
202.. _reverse: reverse_iterator.html
203__ reverse_iterator.pdf
204
205.. |shared| replace:: ``shared_container_iterator``
206.. _shared: ../../utility/shared_container_iterator.html
207
208.. |transform| replace:: ``transform_iterator``
209.. _transform: transform_iterator.html
210__ transform_iterator.pdf
211
212.. |zip| replace:: ``zip_iterator``
213.. _zip: zip_iterator.html
214__ zip_iterator.pdf
215
216.. |shared_ptr| replace:: ``shared_ptr``
217.. _shared_ptr: ../../smart_ptr/shared_ptr.htm
218
219====================
220 Iterator Utilities
221====================
222
223Operations
224----------
225
226The standard library does not handle new-style iterators properly,
227because it knows nothing about the iterator traversal concepts.
228The Boost.Iterator library provides implementations that fully understand
229the new concepts for the two basic operations:
230
231- |advance|_
232- |distance|_
233
234.. |advance| replace:: ``advance``
235.. _advance: advance.html
236
237.. |distance| replace:: ``distance``
238.. _distance: distance.html
239
240Traits
241------
242
243* |pointee|_ (PDF__): Provides the capability to deduce the referent types
244  of pointers, smart pointers and iterators in generic code.  Used
245  in |indirect|.
246
247* |iterator_traits|_ (PDF__): Provides MPL_\ -compatible metafunctions which
248  retrieve an iterator's traits.  Also corrects for the deficiencies
249  of broken implementations of ``std::iterator_traits``.
250
251.. * |interoperable|_ (PDF__): Provides an MPL_\ -compatible metafunction for
252     testing iterator interoperability
253
254.. |pointee| replace:: ``pointee.hpp``
255.. _pointee: pointee.html
256__ pointee.pdf
257
258.. |iterator_traits| replace:: ``iterator_traits.hpp``
259.. _iterator_traits: iterator_traits.html
260__ iterator_traits.pdf
261
262.. |interoperable| replace:: ``interoperable.hpp``
263.. _interoperable: interoperable.html
264.. comment! __ interoperable.pdf
265
266.. _MPL: ../../mpl/doc/index.html
267
268Testing and Concept Checking
269----------------------------
270
271* |iterator_concepts|_ (PDF__): Concept checking classes for the new iterator concepts.
272
273* |iterator_archetypes|_ (PDF__): Concept archetype classes for the new iterators concepts.
274
275.. |iterator_concepts| replace:: ``iterator_concepts.hpp``
276.. _iterator_concepts: iterator_concepts.html
277__ iterator_concepts.pdf
278
279.. |iterator_archetypes| replace:: ``iterator_archetypes.hpp``
280.. _iterator_archetypes: iterator_archetypes.html
281__ iterator_archetypes.pdf
282
283=======================================================
284 Upgrading from the old Boost Iterator Adaptor Library
285=======================================================
286
287.. _Upgrading:
288
289If you have been using the old Boost Iterator Adaptor library to
290implement iterators, you probably wrote a ``Policies`` class which
291captures the core operations of your iterator.  In the new library
292design, you'll move those same core operations into the body of the
293iterator class itself.  If you were writing a family of iterators,
294you probably wrote a `type generator`_ to build the
295``iterator_adaptor`` specialization you needed; in the new library
296design you don't need a type generator (though may want to keep it
297around as a compatibility aid for older code) because, due to the
298use of the Curiously Recurring Template Pattern (CRTP) [Cop95]_,
299you can now define the iterator class yourself and acquire
300functionality through inheritance from ``iterator_facade`` or
301``iterator_adaptor``.  As a result, you also get much finer control
302over how your iterator works: you can add additional constructors,
303or even override the iterator functionality provided by the
304library.
305
306.. _`type generator`: http://www.boost.org/more/generic_programming.html#type_generator
307
308If you're looking for the old ``projection_iterator`` component,
309its functionality has been merged into ``transform_iterator``: as
310long as the function object's ``result_type`` (or the ``Reference``
311template argument, if explicitly specified) is a true reference
312type, ``transform_iterator`` will behave like
313``projection_iterator`` used to.
314
315=========
316 History
317=========
318
319In 2000 Dave Abrahams was writing an iterator for a container of
320pointers, which would access the pointed-to elements when
321dereferenced.  Naturally, being a library writer, he decided to
322generalize the idea and the Boost Iterator Adaptor library was born.
323Dave was inspired by some writings of Andrei Alexandrescu and chose a
324policy based design (though he probably didn't capture Andrei's idea
325very well - there was only one policy class for all the iterator's
326orthogonal properties).  Soon Jeremy Siek realized he would need the
327library and they worked together to produce a "Boostified" version,
328which was reviewed and accepted into the library.  They wrote a paper
329and made several important revisions of the code.
330
331Eventually, several shortcomings of the older library began to make
332the need for a rewrite apparent.  Dave and Jeremy started working
333at the Santa Cruz C++ committee meeting in 2002, and had quickly
334generated a working prototype.  At the urging of Mat Marcus, they
335decided to use the GenVoca/CRTP pattern approach, and moved the
336policies into the iterator class itself.  Thomas Witt expressed
337interest and became the voice of strict compile-time checking for
338the project, adding uses of the SFINAE technique to eliminate false
339converting constructors and operators from the overload set.  He
340also recognized the need for a separate ``iterator_facade``, and
341factored it out of ``iterator_adaptor``.  Finally, after a
342near-complete rewrite of the prototype, they came up with the
343library you see today.
344
345.. [Cop95] [Coplien, 1995] Coplien, J., Curiously Recurring Template
346   Patterns, C++ Report, February 1995, pp. 24-27.
347
348..
349 LocalWords:  Abrahams Siek Witt const bool Sutter's WG int UL LI href Lvalue
350 LocalWords:  ReadableIterator WritableIterator SwappableIterator cv pre iter
351 LocalWords:  ConstantLvalueIterator MutableLvalueIterator CopyConstructible TR
352 LocalWords:  ForwardTraversalIterator BidirectionalTraversalIterator lvalue
353 LocalWords:  RandomAccessTraversalIterator dereferenceable Incrementable tmp
354 LocalWords:  incrementable xxx min prev inplace png oldeqnew AccessTag struct
355 LocalWords:  TraversalTag typename lvalues DWA Hmm JGS
356