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