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

Next

Chapter 1. Boost.Iterator

David Abrahams

Jeremy Siek

Thomas Witt

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>)

Table of Contents

Introduction
Iterator Concepts
Access
Readable Iterator Concept
Writable Iterator Concept
Swappable Iterator Concept
Lvalue Iterator Concept
Traversal
Incrementable Iterator Concept
Single Pass Iterator Concept
Forward Traversal Concept
Bidirectional Traversal Concept
Random Access Traversal Concept
Generic Iterators
Iterator Facade
Reference
Tutorial
Iterator Adaptor
Reference
Tutorial
Specialized Adaptors
Counting Iterator
Filter Iterator
Function Output Iterator
Indirect Iterator
Permutation Iterator
Reverse Iterator
Shared Container Iterator
The Shared Container Iterator Type
The Shared Container Iterator Object Generator
The Shared Container Iterator Range Generator
Transform Iterator
Zip Iterator
Example
Reference
Utilities
Iterator Archetypes
Concept Checking
Iterator Traits
Type Traits
Algorithms
Function template advance()
Function template distance()
Function templates next() and prior()
Upgrading from the old Boost Iterator Adaptor Library
History

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.

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 Standard Proposal for New-Style Iterators.

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.

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).

Specialized Adaptors

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.

Iterator Utilities

Traits

  • 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.

Testing and Concept Checking

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.

  • 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.

Next