Boost
C++ Libraries
...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Boost
C++ Libraries
...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Table of Contents
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.
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 Standard Proposal for New-Style
Iterators.
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 specialized adaptors mentioned below have been proposed for standardization (Standard Proposal For Iterator Facade and Adaptor).
The iterator library supplies a useful suite of standard-conforming iterator templates based on the Boost iterator facade and adaptor templates.
counting_iterator:
an iterator over a sequence of consecutive values. Implements a "lazy
sequence"
filter_iterator:
an iterator over the subset of elements of some sequence which satisfy
a given predicate
function_input_iterator:
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_iterator:
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_iterator:
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_iterator.
indirect_iterator:
an iterator over the objects pointed-to
by the elements of some sequence.
permutation_iterator:
an iterator over the elements of some random-access sequence, rearranged
according to some sequence of integer indices.
reverse_iterator:
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_container_iterator:
an iterator over elements of a container whose lifetime is maintained by
a shared_ptr
stored in the iterator.
transform_iterator:
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_iterator:
an iterator over tuples of the elements at corresponding positions of heterogeneous
underlying iterators.
pointee.hpp:
Provides the capability to deduce the referent types of pointers, smart
pointers and iterators in generic code. Used in indirect_iterator.
iterator_traits.hpp:
Provides MPL
compatible metafunctions which retrieve an iterator's traits. Also corrects
for the deficiencies of broken implementations of std::iterator_traits.
iterator_concepts.hpp:
Concept checking classes for the new iterator concepts.
iterator_archetypes.hpp:
Concept archetype classes for the new iterators concepts.
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.
advance.hpp:
Provides advance()
function for advancing an iterator a given number of positions forward
or backward.
distance.hpp:
Provides distance()
function for computing distance between two iterators.
next_prior.hpp:
Provides next()
and prior()
functions for obtaining next and prior iterators to a given iterator. The
functions are also compatible with non-iterator types.