123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308 |
- [library Boost.Iterator
- [/ version 1.0.1]
- [quickbook 1.6]
- [authors [Abrahams, David], [Siek, Jeremy], [Witt, Thomas]]
- [copyright 2003 2005 David Abrahams Jeremy Siek Thomas Witt]
- [category iterator]
- [id iterator]
- [dirname iterator]
- [purpose
- ]
- [license
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- <ulink url="http://www.boost.org/LICENSE_1_0.txt">
- http://www.boost.org/LICENSE_1_0.txt
- </ulink>)
- ]
- ]
- [/ QuickBook Document version 1.0 ]
- [/ Images ]
- [def _note_ [$images/note.png]]
- [def _alert_ [$images/caution.png]]
- [def _detail_ [$images/note.png]]
- [def _tip_ [$images/tip.png]]
- [/ Links ]
- [def _iterator_ [@../../../iterator/doc/index.html Boost.Iterator]]
- [def _concept_check_ [@../../../concept_check/index.html Boost.ConceptCheck]]
- [template sub[x]'''<subscript>'''[x]'''</subscript>''']
- [section:intro Introduction]
- [def _concepts_ [@http://www.boost.org/more/generic_programming.html#concept concepts]]
- The Boost Iterator Library contains two parts. The first
- is a system of _concepts_ which extend the C++ standard
- iterator requirements. The second is a framework of
- components for building iterators based on these
- extended concepts and includes several useful iterator
- adaptors. The extended iterator concepts have been
- carefully designed so that old-style iterators
- can fit in the new concepts and so that new-style
- iterators will be compatible with old-style algorithms,
- though algorithms may need to be updated if they want to
- take full advantage of the new-style iterator
- capabilities. Several components of this library have
- been accepted into the C++ standard technical report.
- The components of the Boost Iterator Library replace the
- older Boost Iterator Adaptor Library.
- [h2 New-Style Iterators]
- [def _N1185_ [@http://www.gotw.ca/publications/N1185.pdf N1185]]
- [def _N1211_ [@http://www.gotw.ca/publications/N1211.pdf N1211]]
- [def _GOTW_50_ [@http://www.gotw.ca/gotw/050.htm Guru of the Week]]
- The iterator categories defined in C++98 are extremely limiting
- because they bind together two orthogonal concepts: traversal and
- element access. For example, because a random access iterator is
- required to return a reference (and not a proxy) when dereferenced,
- it is impossible to capture the capabilities of
- `vector<bool>::iterator` using the C++98 categories. This is the
- infamous "`vector<bool>` is not a container, and its iterators
- aren't random access iterators", debacle about which Herb Sutter
- wrote two papers for the standards comittee (_N1185_ and _N1211_),
- and a _GOTW_50_. New-style iterators go well beyond
- patching up `vector<bool>`, though: there are lots of other
- iterators already in use which can't be adequately represented by
- the existing concepts. For details about the new iterator
- concepts, see our [@../new-iter-concepts.html Standard Proposal for New-Style Iterators].
- [h2 Iterator Facade and Adaptor]
- [/
- [def _facade_ [link iterator.generic.facade facade]]
- [def _adaptor_ [link iterator.generic.adaptor adaptor]]
- ]
- [def _facade_ [@../iterator_facade.html facade]]
- [def _adaptor_ [@../iterator_adaptor.html adaptor]]
- Writing standard-conforming iterators is tricky, but the need comes
- up often. In order to ease the implementation of new iterators,
- the Boost.Iterator library provides the _facade_ class template,
- which implements many useful defaults and compile-time checks
- designed to help the iterator author ensure that his iterator is
- correct.
- It is also common to define a new iterator that is similar to some
- underlying iterator or iterator-like type, but that modifies some
- aspect of the underlying type's behavior. For that purpose, the
- library supplies the _adaptor_ class template, which is specially
- designed to take advantage of as much of the underlying type's
- behavior as possible.
- Both _facade_ and _adaptor_ as well as many of the [link iterator.specialized specialized
- adaptors] mentioned below have been proposed for standardization
- ([@../facade-and-adaptor.html Standard Proposal For Iterator Facade and Adaptor]).
- [h2 Specialized Adaptors]
- The iterator library supplies a useful suite of standard-conforming
- iterator templates based on the Boost [link
- iterator.intro.iterator_facade_and_adaptor iterator facade and adaptor]
- templates.
- [def _counting_ [link iterator.specialized.counting `counting_iterator`]]
- [def _filter_ [link iterator.specialized.filter `filter_iterator`]]
- [def _function_input_ [@../function_input_iterator.html `function_input_iterator`]]
- [def _function_output_ [link iterator.specialized.function_output `function_output_iterator`]]
- [def _generator_ [@../generator_iterator.htm `generator_iterator`]]
- [def _indirect_ [link iterator.specialized.indirect `indirect_iterator`]]
- [def _permutation_ [link iterator.specialized.permutation `permutation_iterator`]]
- [def _reverse_ [link iterator.specialized.reverse `reverse_iterator`]]
- [def _shared_ [link iterator.specialized.shared_container `shared_container_iterator`]]
- [def _transform_ [link iterator.specialized.transform `transform_iterator`]]
- [def _zip_ [link iterator.specialized.zip `zip_iterator`]]
- [def _shared_ptr_ [@../../smart_ptr/shared_ptr.htm `shared_ptr`]]
- * _counting_: an iterator over a sequence of consecutive values.
- Implements a "lazy sequence"
- * _filter_: an iterator over the subset of elements of some
- sequence which satisfy a given predicate
- * _function_input_: an input iterator wrapping a generator (nullary
- function object); each time the iterator is dereferenced, the function object
- is called to get the value to return.
- * _function_output_: an output iterator wrapping a unary function
- object; each time an element is written into the dereferenced
- iterator, it is passed as a parameter to the function object.
- * _generator_: an input iterator wrapping a generator (nullary
- function object); each time the iterator is dereferenced, the function object
- is called to get the value to return. An outdated analogue of _function_input_.
- * _indirect_: an iterator over the objects *pointed-to* by the
- elements of some sequence.
- * _permutation_: an iterator over the elements of some random-access
- sequence, rearranged according to some sequence of integer indices.
- * _reverse_: an iterator which traverses the elements of some
- bidirectional sequence in reverse. Corrects many of the
- shortcomings of C++98's `std::reverse_iterator`.
- * _shared_: an iterator over elements of a container whose
- lifetime is maintained by a _shared_ptr_ stored in the iterator.
- * _transform_: an iterator over elements which are the result of
- applying some functional transformation to the elements of an
- underlying sequence. This component also replaces the old
- `projection_iterator_adaptor`.
- * _zip_: an iterator over tuples of the elements at corresponding
- positions of heterogeneous underlying iterators.
- [h2 Iterator Utilities]
- [h3 Traits]
- [def _pointee_ [link iterator.utilities.traits `pointee.hpp`]]
- [def _iterator_traits_ [link iterator.utilities.iterator_traits `iterator_traits.hpp`]]
- [def _interoperable_ [@../interoperable.html `interoperable.hpp`]]
- [def _MPL_ [@../../mpl/doc/index.html [*MPL]]]
- * _pointee_: Provides the capability to deduce the referent types
- of pointers, smart pointers and iterators in generic code. Used
- in _indirect_.
- * _iterator_traits_: Provides _MPL_ compatible metafunctions which
- retrieve an iterator's traits. Also corrects for the deficiencies
- of broken implementations of `std::iterator_traits`.
- [/
- * _interoperable_: Provides an _MPL_ compatible metafunction for
- testing iterator interoperability
- ]
- [h3 Testing and Concept Checking]
- [def _iterator_concepts_ [link iterator.concepts `iterator_concepts.hpp`]]
- [def _iterator_archetypes_ [link iterator.utilities.archetypes `iterator_archetypes.hpp`]]
- * _iterator_concepts_: Concept checking classes for the new iterator concepts.
- * _iterator_archetypes_: Concept archetype classes for the new iterators concepts.
- [h2 Iterator Algorithms]
- The library provides a number of generic algorithms for use with iterators. These
- algorithms take advantage of the new concepts defined by the library to provide
- better performance and functionality.
- [def _advance_ [link iterator.algorithms.advance `advance.hpp`]]
- [def _distance_ [link iterator.algorithms.distance `distance.hpp`]]
- [def _next_prior_ [link iterator.algorithms.next_prior `next_prior.hpp`]]
- * _advance_: Provides `advance()` function for advancing an iterator a given number
- of positions forward or backward.
- * _distance_: Provides `distance()` function for computing distance between two
- iterators.
- * _next_prior_: Provides `next()` and `prior()` functions for obtaining
- next and prior iterators to a given iterator. The functions are also compatible
- with non-iterator types.
- [endsect]
- [include concepts.qbk]
- [section:generic Generic Iterators]
- [include facade.qbk]
- [include adaptor.qbk]
- [endsect]
- [include specialized_adaptors.qbk]
- [section:utilities Utilities]
- [include archetypes.qbk]
- [include concept_checking.qbk]
- [include iterator_traits.qbk]
- [include type_traits.qbk]
- [endsect]
- [include algorithms.qbk]
- [section:upgrading Upgrading from the old Boost Iterator Adaptor Library]
- [def _type_generator_ [@http://www.boost.org/more/generic_programming.html#type_generator type generator]]
- If you have been using the old Boost Iterator Adaptor library to
- implement iterators, you probably wrote a `Policies` class which
- captures the core operations of your iterator. In the new library
- design, you'll move those same core operations into the body of the
- iterator class itself. If you were writing a family of iterators,
- you probably wrote a _type_generator_ to build the
- `iterator_adaptor` specialization you needed; in the new library
- design you don't need a type generator (though may want to keep it
- around as a compatibility aid for older code) because, due to the
- use of the Curiously Recurring Template Pattern (CRTP) [Cop95]_,
- you can now define the iterator class yourself and acquire
- functionality through inheritance from `iterator_facade` or
- `iterator_adaptor`. As a result, you also get much finer control
- over how your iterator works: you can add additional constructors,
- or even override the iterator functionality provided by the
- library.
- If you're looking for the old `projection_iterator` component,
- its functionality has been merged into _transform_iterator_: as
- long as the function object's `result_type` (or the `Reference`
- template argument, if explicitly specified) is a true reference
- type, _transform_iterator_ will behave like
- `projection_iterator` used to.
- [endsect]
- [section:history History]
- In 2000 Dave Abrahams was writing an iterator for a container of
- pointers, which would access the pointed-to elements when
- dereferenced. Naturally, being a library writer, he decided to
- generalize the idea and the Boost Iterator Adaptor library was born.
- Dave was inspired by some writings of Andrei Alexandrescu and chose a
- policy based design (though he probably didn't capture Andrei's idea
- very well - there was only one policy class for all the iterator's
- orthogonal properties). Soon Jeremy Siek realized he would need the
- library and they worked together to produce a "Boostified" version,
- which was reviewed and accepted into the library. They wrote a paper
- and made several important revisions of the code.
- Eventually, several shortcomings of the older library began to make
- the need for a rewrite apparent. Dave and Jeremy started working
- at the Santa Cruz C++ committee meeting in 2002, and had quickly
- generated a working prototype. At the urging of Mat Marcus, they
- decided to use the GenVoca/CRTP pattern approach, and moved the
- policies into the iterator class itself. Thomas Witt expressed
- interest and became the voice of strict compile-time checking for
- the project, adding uses of the SFINAE technique to eliminate false
- converting constructors and operators from the overload set. He
- also recognized the need for a separate `iterator_facade`, and
- factored it out of `iterator_adaptor`. Finally, after a
- near-complete rewrite of the prototype, they came up with the
- library you see today.
- [:\[Coplien, 1995\] Coplien, J., Curiously Recurring Template
- Patterns, C++ Report, February 1995, pp. 24-27.]
- [endsect]
|