new-iter-concepts.rst

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

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

++++++++++++++++++++++
 New Iterator Concepts
++++++++++++++++++++++

.. Version 1.25 of this ReStructuredText document is the same as
   n1550_, the paper accepted by the LWG.

:Author: David Abrahams, Jeremy Siek, Thomas Witt
:Contact: [e-mail], [e-mail], [e-mail]
:organization: `Boost Consulting`_, Indiana University `Open Systems
               Lab`_, `Zephyr Associates, Inc.`_
:date: $Date: 2007-11-25 13:38:02 -0500 (Sun, 25 Nov 2007) $

:Number: This is a revised version of n1550_\ =03-0133, which was
         accepted for Technical Report 1 by the C++ standard
         committee's library working group. This proposal is a
         revision of paper n1297_, n1477_, and n1531_.

: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

.. _`Institute for Transport Railway Operation and Construction`:
   http://www.ive.uni-hannover.de 

:Abstract: We propose a new system of iterator concepts that treat
           access and positioning independently. This allows the
           concepts to more closely match the requirements
           of algorithms and provides better categorizations
           of iterators that are used in practice. 
          
.. contents:: Table of Contents

.. _n1297: http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2001/n1297.html
.. _n1477: http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1477.html
.. _n1531: http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1531.html
.. _n1550: http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1550.html

============
 Motivation
============

The standard iterator categories and requirements are flawed because
they use a single hierarchy of concepts to address two orthogonal
issues: *iterator traversal* and *value access*. As a result, many
algorithms with requirements expressed in terms of the iterator
categories are too strict. Also, many real-world iterators can not be
accurately categorized.  A proxy-based iterator with random-access
traversal, for example, may only legally have a category of "input
iterator", so generic algorithms are unable to take advantage of its
random-access capabilities.  The current iterator concept hierarchy is
geared towards iterator traversal (hence the category names), while
requirements that address value access sneak in at various places. The
following table gives a summary of the current value access
requirements in the iterator categories.

+------------------------------------------------------------------------------+
|Value Access Requirements in Existing Iterator Categories                     |
+========================+=====================================================+
|Output Iterator         |``*i = a``                                           |
+------------------------+-----------------------------------------------------+
|Input Iterator          |``*i`` is convertible to ``T``                       |
+------------------------+-----------------------------------------------------+
|Forward Iterator        |``*i`` is ``T&`` (or ``const T&`` once `issue 200`_  |
|                        |is resolved)                                         |
+------------------------+-----------------------------------------------------+
|Random Access Iterator  |``i[n]`` is convertible to ``T`` (also ``i[n] = t``  |
|                        |is required for mutable iterators once `issue 299`_  |
|                        |is resolved)                                         |
+------------------------+-----------------------------------------------------+

.. _issue 200: http://anubis.dkuug.dk/JTC1/SC22/WG21/docs/lwg-active.html#200
.. _issue 299: http://anubis.dkuug.dk/JTC1/SC22/WG21/docs/lwg-active.html#299


Because iterator traversal and value access are mixed together in a
single hierarchy, many useful iterators can not be appropriately
categorized. For example, ``vector<bool>::iterator`` is almost a
random access iterator, but the return type is not ``bool&`` (see
`issue 96`_ and Herb Sutter's paper J16/99-0008 = WG21
N1185). Therefore, the iterators of ``vector<bool>`` only meet the
requirements of input iterator and output iterator.  This is so
nonintuitive that the C++ standard contradicts itself on this point.
In paragraph 23.2.4/1 it says that a ``vector`` is a sequence that
supports random access iterators.

.. _issue 96: http://anubis.dkuug.dk/JTC1/SC22/WG21/docs/lwg-active.html#96

Another difficult-to-categorize iterator is the transform iterator, an
adaptor which applies a unary function object to the dereferenced
value of the some underlying iterator (see `transform_iterator`_).
For unary functions such as ``times``, the return type of
``operator*`` clearly needs to be the ``result_type`` of the function
object, which is typically not a reference.  Because random access
iterators are required to return lvalues from ``operator*``, if you
wrap ``int*`` with a transform iterator, you do not get a random
access iterator as might be expected, but an input iterator.

.. _`transform_iterator`: http://www.boost.org/libs/utility/transform_iterator.htm

A third example is found in the vertex and edge iterators of the
`Boost Graph Library`_. These iterators return vertex and edge
descriptors, which are lightweight handles created on-the-fly. They
must be returned by-value. As a result, their current standard
iterator category is ``input_iterator_tag``, which means that,
strictly speaking, you could not use these iterators with algorithms
like ``min_element()``. As a temporary solution, the concept
`Multi-Pass Input Iterator`_ was introduced to describe the vertex and
edge descriptors, but as the design notes for the concept suggest, a
better solution is needed.

.. _Boost Graph Library: http://www.boost.org/libs/graph/doc/table_of_contents.html
.. _Multi-Pass Input Iterator: http://www.boost.org/libs/utility/MultiPassInputIterator.html

In short, there are many useful iterators that do not fit into the
current standard iterator categories. As a result, the following bad
things happen:

- Iterators are often mis-categorized. 

- Algorithm requirements are more strict than necessary, because they
  cannot separate the need for random access or bidirectional
  traversal from the need for a true reference return type.


========================
 Impact on the Standard
========================

This proposal for TR1 is a pure extension. Further, the new iterator
concepts are backward-compatible with the old iterator requirements,
and old iterators are forward-compatible with the new iterator
concepts. That is to say, iterators that satisfy the old requirements
also satisfy appropriate concepts in the new system, and iterators
modeling the new concepts will automatically satisfy the appropriate
old requirements.

.. I think we need to say something about the resolution to allow
   convertibility to any of the old-style tags as a TR issue (hope it
   made it). -DWA

.. Hmm, not sure I understand. Are you talking about whether a
   standards conforming input iterator is allowed to have
   a tag that is not input_iterator_tag but that
   is convertible to input_iterator_tag? -JGS

Possible (but not proposed) Changes to the Working Paper
========================================================

The extensions in this paper suggest several changes we might make
to the working paper for the next standard.  These changes are not
a formal part of this proposal for TR1.

Changes to Algorithm Requirements
+++++++++++++++++++++++++++++++++

The algorithms in the standard library could benefit from the new
iterator concepts because the new concepts provide a more accurate way
to express their type requirements. The result is algorithms that are
usable in more situations and have fewer type requirements.

For the next working paper (but not for TR1), the committee should
consider the following changes to the type requirements of algorithms.
These changes are phrased as textual substitutions, listing the
algorithms to which each textual substitution applies.

Forward Iterator -> Forward Traversal Iterator and Readable Iterator

  ``find_end, adjacent_find, search, search_n, rotate_copy,
  lower_bound, upper_bound, equal_range, binary_search,
  min_element, max_element``

Forward Iterator (1) -> Single Pass Iterator and Readable Iterator,
Forward Iterator (2) -> Forward Traversal Iterator and Readable Iterator

  ``find_first_of``

Forward Iterator -> Readable Iterator and Writable Iterator

  ``iter_swap``

Forward Iterator -> Single Pass Iterator and Writable Iterator

  ``fill, generate``

Forward Iterator -> Forward Traversal Iterator and Swappable Iterator

  ``rotate``

Forward Iterator (1) -> Swappable Iterator and Single Pass Iterator,
Forward Iterator (2) -> Swappable Iterator and  Incrementable Iterator

  ``swap_ranges``

Forward Iterator -> Forward Traversal Iterator and Readable Iterator and Writable Iterator
  ``remove, remove_if, unique``

Forward Iterator -> Single Pass Iterator and Readable Iterator and Writable Iterator

  ``replace, replace_if``

Bidirectional Iterator -> Bidirectional Traversal Iterator and Swappable Iterator
  ``reverse``

Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable and Swappable Iterator
  ``partition``

Bidirectional Iterator (1) -> Bidirectional Traversal Iterator and Readable Iterator, 
Bidirectional Iterator (2) -> Bidirectional Traversal Iterator and Writable Iterator

  ``copy_backwards``

Bidirectional Iterator -> Bidirectional Traversal Iterator and Swappable Iterator and Readable Iterator
  ``next_permutation, prev_permutation``

Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable Iterator and Writable Iterator
  ``stable_partition, inplace_merge``

Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable Iterator
  ``reverse_copy``

Random Access Iterator -> Random Access Traversal Iterator and Readable and Writable Iterator
  ``random_shuffle, sort, stable_sort, partial_sort, nth_element, push_heap, pop_heap
  make_heap, sort_heap``

Input Iterator (2) -> Incrementable Iterator and Readable Iterator
  ``equal, mismatch``

Input Iterator (2) -> Incrementable Iterator and Readable Iterator
  ``transform``

Deprecations
++++++++++++

For the next working paper (but not for TR1), the committee should
consider deprecating the old iterator tags, and
std::iterator_traits, since it will be superceded by individual
traits metafunctions.

``vector<bool>``
++++++++++++++++

For the next working paper (but not for TR1), the committee should
consider reclassifying ``vector<bool>::iterator`` as a Random
Access Traversal Iterator and Readable Iterator and Writable
Iterator.

========
 Design
========

The iterator requirements are to be separated into two groups. One set
of concepts handles the syntax and semantics of value access:

- Readable Iterator
- Writable Iterator
- Swappable Iterator
- Lvalue Iterator

The access concepts describe requirements related to ``operator*`` and
``operator->``, including the ``value_type``, ``reference``, and