123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355 |
- .. Distributed under the Boost
- .. Software License, Version 1.0. (See accompanying
- .. file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- +++++++++++++++++++++++++++++++++++++++++++++++++
- The Boost.Iterator Library |(logo)|__
- +++++++++++++++++++++++++++++++++++++++++++++++++
- .. |(logo)| image:: ../../../boost.png
- :alt: Boost
- __ ../../../index.htm
- -------------------------------------
- :Authors: David Abrahams, Jeremy Siek, Thomas Witt
- :Contact: dave@boost-consulting.com, jsiek@osl.iu.edu, witt@styleadvisor.com
- :organizations: `Boost Consulting`_, Indiana University `Open Systems
- Lab`_, `Zephyr Associates, Inc.`_
- :date: $Date$
- :copyright: Copyright David Abrahams, Jeremy Siek, Thomas Witt 2003.
- .. _`Boost Consulting`: http://www.boost-consulting.com
- .. _`Open Systems Lab`: http://www.osl.iu.edu
- .. _`Zephyr Associates, Inc.`: http://www.styleadvisor.com
- :Abstract: 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.
- .. _concepts: http://www.boost.org/more/generic_programming.html#concept
- .. contents:: **Table of Contents**
- -------------------------------------
- =====================
- New-Style Iterators
- =====================
- 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 `Guru of the Week`__. 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
- .. _n1185: http://www.gotw.ca/publications/N1185.pdf
- .. _n1211: http://www.gotw.ca/publications/N1211.pdf
- __ http://www.gotw.ca/gotw/050.htm
- `Standard Proposal For New-Style Iterators`__ (PDF__)
- __ new-iter-concepts.html
- __ new-iter-concepts.pdf
- =============================
- Iterator Facade and 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.
- The documentation for these two classes can be found at the following
- web pages:
- * |facade|_ (PDF__)
- * |adaptor|_ (PDF__)
- .. |facade| replace:: ``iterator_facade``
- .. _facade: iterator_facade.html
- __ iterator_facade.pdf
- .. |adaptor| replace:: ``iterator_adaptor``
- .. _adaptor: iterator_adaptor.html
- __ iterator_adaptor.pdf
- Both |facade| and |adaptor| as well as many of the `specialized
- adaptors`_ mentioned below have been proposed for standardization;
- see our
- `Standard Proposal For Iterator Facade and Adaptor`__ (PDF__)
- for more details.
- __ facade-and-adaptor.html
- __ facade-and-adaptor.pdf
- ======================
- Specialized Adaptors
- ======================
- The iterator library supplies a useful suite of standard-conforming
- iterator templates based on the Boost `iterator facade and adaptor`_.
- * |counting|_ (PDF__): an iterator over a sequence of consecutive values.
- Implements a "lazy sequence"
- * |filter|_ (PDF__): an iterator over the subset of elements of some
- sequence which satisfy a given predicate
- * |function_input|_ (PDF__): 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|_ (PDF__): 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. This is an outdated analogue of |function_input|_.
- * |indirect|_ (PDF__): an iterator over the objects *pointed-to* by the
- elements of some sequence.
- * |permutation|_ (PDF__): an iterator over the elements of some random-access
- sequence, rearranged according to some sequence of integer indices.
- * |reverse|_ (PDF__): 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|_ (PDF__): 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|_ (PDF__): an iterator over tuples of the elements at corresponding
- positions of heterogeneous underlying iterators.
- .. |counting| replace:: ``counting_iterator``
- .. _counting: counting_iterator.html
- __ counting_iterator.pdf
- .. |filter| replace:: ``filter_iterator``
- .. _filter: filter_iterator.html
- __ filter_iterator.pdf
- .. |function_input| replace:: ``function_input_iterator``
- .. _function_input: function_input_iterator.html
- __ function_input_iterator.pdf
- .. |function_output| replace:: ``function_output_iterator``
- .. _function_output: function_output_iterator.html
- __ function_output_iterator.pdf
- .. |generator| replace:: ``generator_iterator``
- .. _generator: generator_iterator.htm
- .. |indirect| replace:: ``indirect_iterator``
- .. _indirect: indirect_iterator.html
- __ indirect_iterator.pdf
- .. |permutation| replace:: ``permutation_iterator``
- .. _permutation: permutation_iterator.html
- __ permutation_iterator.pdf
- .. |reverse| replace:: ``reverse_iterator``
- .. _reverse: reverse_iterator.html
- __ reverse_iterator.pdf
- .. |shared| replace:: ``shared_container_iterator``
- .. _shared: ../../utility/shared_container_iterator.html
- .. |transform| replace:: ``transform_iterator``
- .. _transform: transform_iterator.html
- __ transform_iterator.pdf
- .. |zip| replace:: ``zip_iterator``
- .. _zip: zip_iterator.html
- __ zip_iterator.pdf
- .. |shared_ptr| replace:: ``shared_ptr``
- .. _shared_ptr: ../../smart_ptr/shared_ptr.htm
- ====================
- Iterator Utilities
- ====================
- Operations
- ----------
- The standard library does not handle new-style iterators properly,
- because it knows nothing about the iterator traversal concepts.
- The Boost.Iterator library provides implementations that fully understand
- the new concepts for the two basic operations:
- - |advance|_
- - |distance|_
- .. |advance| replace:: ``advance``
- .. _advance: advance.html
- .. |distance| replace:: ``distance``
- .. _distance: distance.html
- Traits
- ------
- * |pointee|_ (PDF__): Provides the capability to deduce the referent types
- of pointers, smart pointers and iterators in generic code. Used
- in |indirect|.
- * |iterator_traits|_ (PDF__): Provides MPL_\ -compatible metafunctions which
- retrieve an iterator's traits. Also corrects for the deficiencies
- of broken implementations of ``std::iterator_traits``.
- .. * |interoperable|_ (PDF__): Provides an MPL_\ -compatible metafunction for
- testing iterator interoperability
- .. |pointee| replace:: ``pointee.hpp``
- .. _pointee: pointee.html
- __ pointee.pdf
- .. |iterator_traits| replace:: ``iterator_traits.hpp``
- .. _iterator_traits: iterator_traits.html
- __ iterator_traits.pdf
- .. |interoperable| replace:: ``interoperable.hpp``
- .. _interoperable: interoperable.html
- .. comment! __ interoperable.pdf
- .. _MPL: ../../mpl/doc/index.html
- Testing and Concept Checking
- ----------------------------
- * |iterator_concepts|_ (PDF__): Concept checking classes for the new iterator concepts.
- * |iterator_archetypes|_ (PDF__): Concept archetype classes for the new iterators concepts.
- .. |iterator_concepts| replace:: ``iterator_concepts.hpp``
- .. _iterator_concepts: iterator_concepts.html
- __ iterator_concepts.pdf
- .. |iterator_archetypes| replace:: ``iterator_archetypes.hpp``
- .. _iterator_archetypes: iterator_archetypes.html
- __ iterator_archetypes.pdf
- =======================================================
- Upgrading from the old Boost Iterator Adaptor Library
- =======================================================
- .. _Upgrading:
- 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.
- .. _`type generator`: http://www.boost.org/more/generic_programming.html#type_generator
- 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.
- =========
- 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.
- .. [Cop95] [Coplien, 1995] Coplien, J., Curiously Recurring Template
- Patterns, C++ Report, February 1995, pp. 24-27.
- ..
- LocalWords: Abrahams Siek Witt const bool Sutter's WG int UL LI href Lvalue
- LocalWords: ReadableIterator WritableIterator SwappableIterator cv pre iter
- LocalWords: ConstantLvalueIterator MutableLvalueIterator CopyConstructible TR
- LocalWords: ForwardTraversalIterator BidirectionalTraversalIterator lvalue
- LocalWords: RandomAccessTraversalIterator dereferenceable Incrementable tmp
- LocalWords: incrementable xxx min prev inplace png oldeqnew AccessTag struct
- LocalWords: TraversalTag typename lvalues DWA Hmm JGS
|