439 lines
14 KiB
ReStructuredText
439 lines
14 KiB
ReStructuredText
.. 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)
|
|
|
|
+++++++++++++++++++++++++++++
|
|
Iterator Facade and Adaptor
|
|
+++++++++++++++++++++++++++++
|
|
|
|
:Author: David Abrahams, Jeremy Siek, Thomas Witt
|
|
:Contact: dave@boost-consulting.com, jsiek@osl.iu.edu, witt@styleadvisor.com
|
|
:organization: `Boost Consulting`_, Indiana University `Open Systems
|
|
Lab`_, `Zephyr Associates, Inc.`_
|
|
:date: $Date$
|
|
|
|
:Number: This is a revised version of N1530_\ =03-0113, which was
|
|
accepted for Technical Report 1 by the C++ standard
|
|
committee's library working group.
|
|
|
|
.. Version 1.9 of this ReStructuredText document corresponds to
|
|
n1530_, the paper accepted by the LWG.
|
|
|
|
.. _n1530: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1530.html
|
|
|
|
:copyright: Copyright David Abrahams, Jeremy Siek, and 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: We propose a set of class templates that help programmers
|
|
build standard-conforming iterators, both from scratch and
|
|
by adapting other iterators.
|
|
|
|
.. contents:: Table of Contents
|
|
|
|
============
|
|
Motivation
|
|
============
|
|
|
|
Iterators play an important role in modern C++ programming. The
|
|
iterator is the central abstraction of the algorithms of the Standard
|
|
Library, allowing algorithms to be re-used in in a wide variety of
|
|
contexts. The C++ Standard Library contains a wide variety of useful
|
|
iterators. Every one of the standard containers comes with constant
|
|
and mutable iterators [#mutable]_, and also reverse versions of those
|
|
same iterators which traverse the container in the opposite direction.
|
|
The Standard also supplies ``istream_iterator`` and
|
|
``ostream_iterator`` for reading from and writing to streams,
|
|
``insert_iterator``, ``front_insert_iterator`` and
|
|
``back_insert_iterator`` for inserting elements into containers, and
|
|
``raw_storage_iterator`` for initializing raw memory [7].
|
|
|
|
Despite the many iterators supplied by the Standard Library, obvious
|
|
and useful iterators are missing, and creating new iterator types is
|
|
still a common task for C++ programmers. The literature documents
|
|
several of these, for example line_iterator [3] and Constant_iterator
|
|
[9]. The iterator abstraction is so powerful that we expect
|
|
programmers will always need to invent new iterator types.
|
|
|
|
Although it is easy to create iterators that *almost* conform to the
|
|
standard, the iterator requirements contain subtleties which can make
|
|
creating an iterator which *actually* conforms quite difficult.
|
|
Further, the iterator interface is rich, containing many operators
|
|
that are technically redundant and tedious to implement. To automate
|
|
the repetitive work of constructing iterators, we propose
|
|
``iterator_facade``, an iterator base class template which provides
|
|
the rich interface of standard iterators and delegates its
|
|
implementation to member functions of the derived class. In addition
|
|
to reducing the amount of code necessary to create an iterator, the
|
|
``iterator_facade`` also provides compile-time error detection.
|
|
Iterator implementation mistakes that often go unnoticed are turned
|
|
into compile-time errors because the derived class implementation must
|
|
match the expectations of the ``iterator_facade``.
|
|
|
|
A common pattern of iterator construction is the adaptation of one
|
|
iterator to form a new one. The functionality of an iterator is
|
|
composed of four orthogonal aspects: traversal, indirection, equality
|
|
comparison and distance measurement. Adapting an old iterator to
|
|
create a new one often saves work because one can reuse one aspect of
|
|
functionality while redefining the other. For example, the Standard
|
|
provides ``reverse_iterator``, which adapts any Bidirectional Iterator
|
|
by inverting its direction of traversal. As with plain iterators,
|
|
iterator adaptors defined outside the Standard have become commonplace
|
|
in the literature:
|
|
|
|
* Checked iter[13] adds bounds-checking to an existing iterator.
|
|
|
|
* The iterators of the View Template Library[14], which adapts
|
|
containers, are themselves adaptors over the underlying iterators.
|
|
|
|
* Smart iterators [5] adapt an iterator's dereferencing behavior by
|
|
applying a function object to the object being referenced and
|
|
returning the result.
|
|
|
|
* Custom iterators [4], in which a variety of adaptor types are enumerated.
|
|
|
|
* Compound iterators [1], which access a slice out of a container of containers.
|
|
|
|
* Several iterator adaptors from the MTL [12]. The MTL contains a
|
|
strided iterator, where each call to ``operator++()`` moves the
|
|
iterator ahead by some constant factor, and a scaled iterator, which
|
|
multiplies the dereferenced value by some constant.
|
|
|
|
.. [#concept] We use the term concept to mean a set of requirements
|
|
that a type must satisfy to be used with a particular template
|
|
parameter.
|
|
|
|
.. [#mutable] The term mutable iterator refers to iterators over objects that
|
|
can be changed by assigning to the dereferenced iterator, while
|
|
constant iterator refers to iterators over objects that cannot be
|
|
modified.
|
|
|
|
To fulfill the need for constructing adaptors, we propose the
|
|
``iterator_adaptor`` class template. Instantiations of
|
|
``iterator_adaptor`` serve as a base classes for new iterators,
|
|
providing the default behavior of forwarding all operations to the
|
|
underlying iterator. The user can selectively replace these features
|
|
in the derived iterator class. This proposal also includes a number
|
|
of more specialized adaptors, such as the ``transform_iterator`` that
|
|
applies some user-specified function during the dereference of the
|
|
iterator.
|
|
|
|
========================
|
|
Impact on the Standard
|
|
========================
|
|
|
|
This proposal is purely an addition to the C++ standard library.
|
|
However, note that this proposal relies on the proposal for New
|
|
Iterator Concepts.
|
|
|
|
========
|
|
Design
|
|
========
|
|
|
|
Iterator Concepts
|
|
=================
|
|
|
|
This proposal is formulated in terms of the new ``iterator concepts``
|
|
as proposed in n1550_, since user-defined and especially adapted
|
|
iterators suffer from the well known categorization problems that are
|
|
inherent to the current iterator categories.
|
|
|
|
.. _n1550: http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2003/n1550.htm
|
|
|
|
This proposal does not strictly depend on proposal n1550_, as there
|
|
is a direct mapping between new and old categories. This proposal
|
|
could be reformulated using this mapping if n1550_ was not accepted.
|
|
|
|
Interoperability
|
|
================
|
|
|
|
The question of iterator interoperability is poorly addressed in the
|
|
current standard. There are currently two defect reports that are
|
|
concerned with interoperability issues.
|
|
|
|
Issue 179_ concerns the fact that mutable container iterator types
|
|
are only required to be convertible to the corresponding constant
|
|
iterator types, but objects of these types are not required to
|
|
interoperate in comparison or subtraction expressions. This situation
|
|
is tedious in practice and out of line with the way built in types
|
|
work. This proposal implements the proposed resolution to issue
|
|
179_, as most standard library implementations do nowadays. In other
|
|
words, if an iterator type A has an implicit or user defined
|
|
conversion to an iterator type B, the iterator types are interoperable
|
|
and the usual set of operators are available.
|
|
|
|
Issue 280_ concerns the current lack of interoperability between
|
|
reverse iterator types. The proposed new reverse_iterator template
|
|
fixes the issues raised in 280. It provides the desired
|
|
interoperability without introducing unwanted overloads.
|
|
|
|
.. _179: http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#179
|
|
.. _280: http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#280
|
|
|
|
|
|
Iterator Facade
|
|
===============
|
|
|
|
.. include:: iterator_facade_body.rst
|
|
|
|
Iterator Adaptor
|
|
================
|
|
|
|
.. include:: iterator_adaptor_body.rst
|
|
|
|
Specialized Adaptors
|
|
====================
|
|
|
|
This proposal also contains several examples of specialized adaptors
|
|
which were easily implemented using ``iterator_adaptor``:
|
|
|
|
* ``indirect_iterator``, which iterates over iterators, pointers,
|
|
or smart pointers and applies an extra level of dereferencing.
|
|
|
|
* A new ``reverse_iterator``, which inverts the direction of a Base
|
|
iterator's motion, while allowing adapted constant and mutable
|
|
iterators to interact in the expected ways (unlike those in most
|
|
implementations of C++98).
|
|
|
|
* ``transform_iterator``, which applies a user-defined function object
|
|
to the underlying values when dereferenced.
|
|
|
|
* ``filter_iterator``, which provides a view of an iterator range in
|
|
which some elements of the underlying range are skipped.
|
|
|
|
.. _counting:
|
|
|
|
* ``counting_iterator``, which adapts any incrementable type
|
|
(e.g. integers, iterators) so that incrementing/decrementing the
|
|
adapted iterator and dereferencing it produces successive values of
|
|
the Base type.
|
|
|
|
* ``function_output_iterator``, which makes it easier to create custom
|
|
output iterators.
|
|
|
|
Based on examples in the Boost library, users have generated many new
|
|
adaptors, among them a permutation adaptor which applies some
|
|
permutation to a random access iterator, and a strided adaptor, which
|
|
adapts a random access iterator by multiplying its unit of motion by a
|
|
constant factor. In addition, the Boost Graph Library (BGL) uses
|
|
iterator adaptors to adapt other graph libraries, such as LEDA [10]
|
|
and Stanford GraphBase [8], to the BGL interface (which requires C++
|
|
Standard compliant iterators).
|
|
|
|
===============
|
|
Proposed Text
|
|
===============
|
|
|
|
|
|
Header ``<iterator_helper>`` synopsis [lib.iterator.helper.synopsis]
|
|
=======================================================================
|
|
|
|
|
|
::
|
|
|
|
struct use_default;
|
|
|
|
struct iterator_core_access { /* implementation detail */ };
|
|
|
|
template <
|
|
class Derived
|
|
, class Value
|
|
, class CategoryOrTraversal
|
|
, class Reference = Value&
|
|
, class Difference = ptrdiff_t
|
|
>
|
|
class iterator_facade;
|
|
|
|
template <
|
|
class Derived
|
|
, class Base
|
|
, class Value = use_default
|
|
, class CategoryOrTraversal = use_default
|
|
, class Reference = use_default
|
|
, class Difference = use_default
|
|
>
|
|
class iterator_adaptor;
|
|
|
|
template <
|
|
class Iterator
|
|
, class Value = use_default
|
|
, class CategoryOrTraversal = use_default
|
|
, class Reference = use_default
|
|
, class Difference = use_default
|
|
>
|
|
class indirect_iterator;
|
|
|
|
template <class Dereferenceable>
|
|
struct pointee;
|
|
|
|
template <class Dereferenceable>
|
|
struct indirect_reference;
|
|
|
|
template <class Iterator>
|
|
class reverse_iterator;
|
|
|
|
template <
|
|
class UnaryFunction
|
|
, class Iterator
|
|
, class Reference = use_default
|
|
, class Value = use_default
|
|
>
|
|
class transform_iterator;
|
|
|
|
template <class Predicate, class Iterator>
|
|
class filter_iterator;
|
|
|
|
template <
|
|
class Incrementable
|
|
, class CategoryOrTraversal = use_default
|
|
, class Difference = use_default
|
|
>
|
|
class counting_iterator;
|
|
|
|
template <class UnaryFunction>
|
|
class function_output_iterator;
|
|
|
|
|
|
|
|
Iterator facade [lib.iterator.facade]
|
|
=====================================
|
|
|
|
.. include:: iterator_facade_abstract.rst
|
|
|
|
Class template ``iterator_facade``
|
|
----------------------------------
|
|
|
|
.. include:: iterator_facade_ref.rst
|
|
|
|
Iterator adaptor [lib.iterator.adaptor]
|
|
=======================================
|
|
|
|
.. include:: iterator_adaptor_abstract.rst
|
|
|
|
Class template ``iterator_adaptor``
|
|
-----------------------------------
|
|
|
|
.. include:: iterator_adaptor_ref.rst
|
|
|
|
|
|
Specialized adaptors [lib.iterator.special.adaptors]
|
|
====================================================
|
|
|
|
|
|
The ``enable_if_convertible<X,Y>::type`` expression used in
|
|
this section is for exposition purposes. The converting constructors
|
|
for specialized adaptors should be only be in an overload set provided
|
|
that an object of type ``X`` is implicitly convertible to an object of
|
|
type ``Y``.
|
|
The signatures involving ``enable_if_convertible`` should behave
|
|
*as-if* ``enable_if_convertible`` were defined to be::
|
|
|
|
template <bool> enable_if_convertible_impl
|
|
{};
|
|
|
|
template <> enable_if_convertible_impl<true>
|
|
{ struct type; };
|
|
|
|
template<typename From, typename To>
|
|
struct enable_if_convertible
|
|
: enable_if_convertible_impl<is_convertible<From,To>::value>
|
|
{};
|
|
|
|
If an expression other than the default argument is used to supply
|
|
the value of a function parameter whose type is written in terms
|
|
of ``enable_if_convertible``, the program is ill-formed, no
|
|
diagnostic required.
|
|
|
|
[*Note:* The ``enable_if_convertible`` approach uses SFINAE to
|
|
take the constructor out of the overload set when the types are not
|
|
implicitly convertible.
|
|
]
|
|
|
|
|
|
Indirect iterator
|
|
-----------------
|
|
|
|
.. include:: indirect_iterator_abstract.rst
|
|
|
|
Class template ``pointee``
|
|
....................................
|
|
|
|
.. include:: pointee_ref.rst
|
|
|
|
Class template ``indirect_reference``
|
|
.....................................
|
|
|
|
.. include:: indirect_reference_ref.rst
|
|
|
|
Class template ``indirect_iterator``
|
|
....................................
|
|
|
|
.. include:: indirect_iterator_ref.rst
|
|
|
|
Reverse iterator
|
|
----------------
|
|
|
|
.. include:: reverse_iterator_abstract.rst
|
|
|
|
Class template ``reverse_iterator``
|
|
...................................
|
|
|
|
.. include:: reverse_iterator_ref.rst
|
|
|
|
|
|
Transform iterator
|
|
------------------
|
|
|
|
.. include:: transform_iterator_abstract.rst
|
|
|
|
Class template ``transform_iterator``
|
|
.....................................
|
|
|
|
.. include:: transform_iterator_ref.rst
|
|
|
|
|
|
Filter iterator
|
|
---------------
|
|
|
|
.. include:: filter_iterator_abstract.rst
|
|
|
|
|
|
Class template ``filter_iterator``
|
|
..................................
|
|
|
|
.. include:: filter_iterator_ref.rst
|
|
|
|
|
|
Counting iterator
|
|
-----------------
|
|
|
|
.. include:: counting_iterator_abstract.rst
|
|
|
|
Class template ``counting_iterator``
|
|
....................................
|
|
|
|
.. include:: counting_iterator_ref.rst
|
|
|
|
|
|
Function output iterator
|
|
------------------------
|
|
|
|
.. include:: func_output_iter_abstract.rst
|
|
|
|
Class template ``function_output_iterator``
|
|
...........................................
|
|
|
|
.. include:: func_output_iter_ref.rst
|
|
|
|
|
|
|
|
|
|
.. LocalWords: Abrahams Siek Witt istream ostream iter MTL strided interoperate
|
|
LocalWords: CRTP metafunctions inlining lvalue JGS incrementable BGL LEDA cv
|
|
LocalWords: GraphBase struct ptrdiff UnaryFunction const int typename bool pp
|
|
LocalWords: lhs rhs SFINAE markup iff tmp OtherDerived OtherIterator DWA foo
|
|
LocalWords: dereferenceable subobject AdaptableUnaryFunction impl pre ifdef'd
|
|
LocalWords: OtherIncrementable Coplien
|