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.

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.

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

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

.. include:: iterator_facade_ref.rst

Iterator adaptor [lib.iterator.adaptor]

.. include:: iterator_adaptor_abstract.rst

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

.. include:: indirect_iterator_abstract.rst

.. include:: pointee_ref.rst

.. include:: indirect_reference_ref.rst

.. include:: indirect_iterator_ref.rst

.. include:: reverse_iterator_abstract.rst

.. include:: reverse_iterator_ref.rst

.. include:: transform_iterator_abstract.rst

.. include:: transform_iterator_ref.rst

.. include:: filter_iterator_abstract.rst

.. include:: filter_iterator_ref.rst

.. include:: counting_iterator_abstract.rst

.. include:: counting_iterator_ref.rst

.. include:: func_output_iter_abstract.rst

.. include:: func_output_iter_ref.rst