196 lines
8.6 KiB
ReStructuredText
196 lines
8.6 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)
|
|
|
|
.. Version 1.1 of this ReStructuredText document corresponds to
|
|
n1530_, the paper accepted by the LWG for TR1.
|
|
|
|
.. Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003.
|
|
|
|
|
|
While the iterator interface is rich, there is a core subset of the
|
|
interface that is necessary for all the functionality. We have
|
|
identified the following core behaviors for iterators:
|
|
|
|
* dereferencing
|
|
* incrementing
|
|
* decrementing
|
|
* equality comparison
|
|
* random-access motion
|
|
* distance measurement
|
|
|
|
In addition to the behaviors listed above, the core interface elements
|
|
include the associated types exposed through iterator traits:
|
|
``value_type``, ``reference``, ``difference_type``, and
|
|
``iterator_category``.
|
|
|
|
Iterator facade uses the Curiously Recurring Template
|
|
Pattern (CRTP) [Cop95]_ so that the user can specify the behavior
|
|
of ``iterator_facade`` in a derived class. Former designs used
|
|
policy objects to specify the behavior, but that approach was
|
|
discarded for several reasons:
|
|
|
|
1. the creation and eventual copying of the policy object may create
|
|
overhead that can be avoided with the current approach.
|
|
|
|
2. The policy object approach does not allow for custom constructors
|
|
on the created iterator types, an essential feature if
|
|
``iterator_facade`` should be used in other library
|
|
implementations.
|
|
|
|
3. Without the use of CRTP, the standard requirement that an
|
|
iterator's ``operator++`` returns the iterator type itself
|
|
would mean that all iterators built with the library would
|
|
have to be specializations of ``iterator_facade<...>``, rather
|
|
than something more descriptive like
|
|
``indirect_iterator<T*>``. Cumbersome type generator
|
|
metafunctions would be needed to build new parameterized
|
|
iterators, and a separate ``iterator_adaptor`` layer would be
|
|
impossible.
|
|
|
|
Usage
|
|
-----
|
|
|
|
The user of ``iterator_facade`` derives his iterator class from a
|
|
specialization of ``iterator_facade`` and passes the derived
|
|
iterator class as ``iterator_facade``\ 's first template parameter.
|
|
The order of the other template parameters have been carefully
|
|
chosen to take advantage of useful defaults. For example, when
|
|
defining a constant lvalue iterator, the user can pass a
|
|
const-qualified version of the iterator's ``value_type`` as
|
|
``iterator_facade``\ 's ``Value`` parameter and omit the
|
|
``Reference`` parameter which follows.
|
|
|
|
The derived iterator class must define member functions implementing
|
|
the iterator's core behaviors. The following table describes
|
|
expressions which are required to be valid depending on the category
|
|
of the derived iterator type. These member functions are described
|
|
briefly below and in more detail in the iterator facade
|
|
requirements.
|
|
|
|
+------------------------+-------------------------------+
|
|
|Expression |Effects |
|
|
+========================+===============================+
|
|
|``i.dereference()`` |Access the value referred to |
|
|
+------------------------+-------------------------------+
|
|
|``i.equal(j)`` |Compare for equality with ``j``|
|
|
+------------------------+-------------------------------+
|
|
|``i.increment()`` |Advance by one position |
|
|
+------------------------+-------------------------------+
|
|
|``i.decrement()`` |Retreat by one position |
|
|
+------------------------+-------------------------------+
|
|
|``i.advance(n)`` |Advance by ``n`` positions |
|
|
+------------------------+-------------------------------+
|
|
|``i.distance_to(j)`` |Measure the distance to ``j`` |
|
|
+------------------------+-------------------------------+
|
|
|
|
.. Should we add a comment that a zero overhead implementation of iterator_facade
|
|
is possible with proper inlining?
|
|
|
|
In addition to implementing the core interface functions, an iterator
|
|
derived from ``iterator_facade`` typically defines several
|
|
constructors. To model any of the standard iterator concepts, the
|
|
iterator must at least have a copy constructor. Also, if the iterator
|
|
type ``X`` is meant to be automatically interoperate with another
|
|
iterator type ``Y`` (as with constant and mutable iterators) then
|
|
there must be an implicit conversion from ``X`` to ``Y`` or from ``Y``
|
|
to ``X`` (but not both), typically implemented as a conversion
|
|
constructor. Finally, if the iterator is to model Forward Traversal
|
|
Iterator or a more-refined iterator concept, a default constructor is
|
|
required.
|
|
|
|
|
|
|
|
Iterator Core Access
|
|
--------------------
|
|
|
|
``iterator_facade`` and the operator implementations need to be able
|
|
to access the core member functions in the derived class. Making the
|
|
core member functions public would expose an implementation detail to
|
|
the user. The design used here ensures that implementation details do
|
|
not appear in the public interface of the derived iterator type.
|
|
|
|
Preventing direct access to the core member functions has two
|
|
advantages. First, there is no possibility for the user to accidently
|
|
use a member function of the iterator when a member of the value_type
|
|
was intended. This has been an issue with smart pointer
|
|
implementations in the past. The second and main advantage is that
|
|
library implementers can freely exchange a hand-rolled iterator
|
|
implementation for one based on ``iterator_facade`` without fear of
|
|
breaking code that was accessing the public core member functions
|
|
directly.
|
|
|
|
In a naive implementation, keeping the derived class' core member
|
|
functions private would require it to grant friendship to
|
|
``iterator_facade`` and each of the seven operators. In order to
|
|
reduce the burden of limiting access, ``iterator_core_access`` is
|
|
provided, a class that acts as a gateway to the core member functions
|
|
in the derived iterator class. The author of the derived class only
|
|
needs to grant friendship to ``iterator_core_access`` to make his core
|
|
member functions available to the library.
|
|
|
|
.. This is no long uptodate -thw
|
|
.. Yes it is; I made sure of it! -DWA
|
|
|
|
``iterator_core_access`` will be typically implemented as an empty
|
|
class containing only private static member functions which invoke the
|
|
iterator core member functions. There is, however, no need to
|
|
standardize the gateway protocol. Note that even if
|
|
``iterator_core_access`` used public member functions it would not
|
|
open a safety loophole, as every core member function preserves the
|
|
invariants of the iterator.
|
|
|
|
``operator[]``
|
|
--------------
|
|
|
|
The indexing operator for a generalized iterator presents special
|
|
challenges. A random access iterator's ``operator[]`` is only
|
|
required to return something convertible to its ``value_type``.
|
|
Requiring that it return an lvalue would rule out currently-legal
|
|
random-access iterators which hold the referenced value in a data
|
|
member (e.g. |counting|_), because ``*(p+n)`` is a reference
|
|
into the temporary iterator ``p+n``, which is destroyed when
|
|
``operator[]`` returns.
|
|
|
|
.. |counting| replace:: ``counting_iterator``
|
|
|
|
Writable iterators built with ``iterator_facade`` implement the
|
|
semantics required by the preferred resolution to `issue 299`_ and
|
|
adopted by proposal n1550_: the result of ``p[n]`` is an object
|
|
convertible to the iterator's ``value_type``, and ``p[n] = x`` is
|
|
equivalent to ``*(p + n) = x`` (Note: This result object may be
|
|
implemented as a proxy containing a copy of ``p+n``). This approach
|
|
will work properly for any random-access iterator regardless of the
|
|
other details of its implementation. A user who knows more about
|
|
the implementation of her iterator is free to implement an
|
|
``operator[]`` that returns an lvalue in the derived iterator
|
|
class; it will hide the one supplied by ``iterator_facade`` from
|
|
clients of her iterator.
|
|
|
|
.. _n1550: http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2003/n1550.htm
|
|
|
|
.. _`issue 299`: http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#299
|
|
|
|
.. _`operator arrow`:
|
|
|
|
|
|
``operator->``
|
|
--------------
|
|
|
|
The ``reference`` type of a readable iterator (and today's input
|
|
iterator) need not in fact be a reference, so long as it is
|
|
convertible to the iterator's ``value_type``. When the ``value_type``
|
|
is a class, however, it must still be possible to access members
|
|
through ``operator->``. Therefore, an iterator whose ``reference``
|
|
type is not in fact a reference must return a proxy containing a copy
|
|
of the referenced value from its ``operator->``.
|
|
|
|
The return types for ``iterator_facade``\ 's ``operator->`` and
|
|
``operator[]`` are not explicitly specified. Instead, those types
|
|
are described in terms of a set of requirements, which must be
|
|
satisfied by the ``iterator_facade`` implementation.
|
|
|
|
.. [Cop95] [Coplien, 1995] Coplien, J., Curiously Recurring Template
|
|
Patterns, C++ Report, February 1995, pp. 24-27.
|
|
|