ceph/src/boost/libs/iterator/doc/iterator_facade_body.rst

   1 .. Distributed under the Boost
   2 .. Software License, Version 1.0. (See accompanying
   3 .. file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   4
   5 .. Version 1.1 of this ReStructuredText document corresponds to
   6    n1530_, the paper accepted by the LWG for TR1.
   7
   8 .. Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003.
   9
  10
  11 While the iterator interface is rich, there is a core subset of the
  12 interface that is necessary for all the functionality.  We have
  13 identified the following core behaviors for iterators:
  14
  15 * dereferencing
  16 * incrementing
  17 * decrementing
  18 * equality comparison
  19 * random-access motion
  20 * distance measurement
  21
  22 In addition to the behaviors listed above, the core interface elements
  23 include the associated types exposed through iterator traits:
  24 ``value_type``, ``reference``, ``difference_type``, and
  25 ``iterator_category``.
  26
  27 Iterator facade uses the Curiously Recurring Template
  28 Pattern (CRTP) [Cop95]_ so that the user can specify the behavior
  29 of ``iterator_facade`` in a derived class.  Former designs used
  30 policy objects to specify the behavior, but that approach was
  31 discarded for several reasons:
  32
  33   1. the creation and eventual copying of the policy object may create
  34      overhead that can be avoided with the current approach.
  35
  36   2. The policy object approach does not allow for custom constructors
  37      on the created iterator types, an essential feature if
  38      ``iterator_facade`` should be used in other library
  39      implementations.
  40
  41   3. Without the use of CRTP, the standard requirement that an
  42      iterator's ``operator++`` returns the iterator type itself
  43      would mean that all iterators built with the library would
  44      have to be specializations of ``iterator_facade<...>``, rather
  45      than something more descriptive like
  46      ``indirect_iterator<T*>``.  Cumbersome type generator
  47      metafunctions would be needed to build new parameterized
  48      iterators, and a separate ``iterator_adaptor`` layer would be
  49      impossible.
  50
  51 Usage
  52 -----
  53
  54 The user of ``iterator_facade`` derives his iterator class from a
  55 specialization of ``iterator_facade`` and passes the derived
  56 iterator class as ``iterator_facade``\ 's first template parameter.
  57 The order of the other template parameters have been carefully
  58 chosen to take advantage of useful defaults.  For example, when
  59 defining a constant lvalue iterator, the user can pass a
  60 const-qualified version of the iterator's ``value_type`` as
  61 ``iterator_facade``\ 's ``Value`` parameter and omit the
  62 ``Reference`` parameter which follows.
  63
  64 The derived iterator class must define member functions implementing
  65 the iterator's core behaviors.  The following table describes
  66 expressions which are required to be valid depending on the category
  67 of the derived iterator type.  These member functions are described
  68 briefly below and in more detail in the iterator facade
  69 requirements.
  70
  71    +------------------------+-------------------------------+
  72    |Expression              |Effects                        |
  73    +========================+===============================+
  74    |``i.dereference()``     |Access the value referred to   |
  75    +------------------------+-------------------------------+
  76    |``i.equal(j)``          |Compare for equality with ``j``|
  77    +------------------------+-------------------------------+
  78    |``i.increment()``       |Advance by one position        |
  79    +------------------------+-------------------------------+
  80    |``i.decrement()``       |Retreat by one position        |
  81    +------------------------+-------------------------------+
  82    |``i.advance(n)``        |Advance by ``n`` positions     |
  83    +------------------------+-------------------------------+
  84    |``i.distance_to(j)``    |Measure the distance to ``j``  |
  85    +------------------------+-------------------------------+
  86
  87 .. Should we add a comment that a zero overhead implementation of iterator_facade
  88    is possible with proper inlining?
  89
  90 In addition to implementing the core interface functions, an iterator
  91 derived from ``iterator_facade`` typically defines several
  92 constructors. To model any of the standard iterator concepts, the
  93 iterator must at least have a copy constructor. Also, if the iterator
  94 type ``X`` is meant to be automatically interoperate with another
  95 iterator type ``Y`` (as with constant and mutable iterators) then
  96 there must be an implicit conversion from ``X`` to ``Y`` or from ``Y``
  97 to ``X`` (but not both), typically implemented as a conversion
  98 constructor. Finally, if the iterator is to model Forward Traversal
  99 Iterator or a more-refined iterator concept, a default constructor is
 100 required.
 101
 102
 103
 104 Iterator Core Access
 105 --------------------
 106
 107 ``iterator_facade`` and the operator implementations need to be able
 108 to access the core member functions in the derived class.  Making the
 109 core member functions public would expose an implementation detail to
 110 the user.  The design used here ensures that implementation details do
 111 not appear in the public interface of the derived iterator type.
 112
 113 Preventing direct access to the core member functions has two
 114 advantages.  First, there is no possibility for the user to accidently
 115 use a member function of the iterator when a member of the value_type
 116 was intended.  This has been an issue with smart pointer
 117 implementations in the past.  The second and main advantage is that
 118 library implementers can freely exchange a hand-rolled iterator
 119 implementation for one based on ``iterator_facade`` without fear of
 120 breaking code that was accessing the public core member functions
 121 directly.
 122
 123 In a naive implementation, keeping the derived class' core member
 124 functions private would require it to grant friendship to
 125 ``iterator_facade`` and each of the seven operators.  In order to
 126 reduce the burden of limiting access, ``iterator_core_access`` is
 127 provided, a class that acts as a gateway to the core member functions
 128 in the derived iterator class.  The author of the derived class only
 129 needs to grant friendship to ``iterator_core_access`` to make his core
 130 member functions available to the library.
 131
 132 .. This is no long uptodate -thw
 133 .. Yes it is; I made sure of it! -DWA
 134
 135 ``iterator_core_access`` will be typically implemented as an empty
 136 class containing only private static member functions which invoke the
 137 iterator core member functions. There is, however, no need to
 138 standardize the gateway protocol.  Note that even if
 139 ``iterator_core_access`` used public member functions it would not
 140 open a safety loophole, as every core member function preserves the
 141 invariants of the iterator.
 142
 143 ``operator[]``
 144 --------------
 145
 146 The indexing operator for a generalized iterator presents special
 147 challenges.  A random access iterator's ``operator[]`` is only
 148 required to return something convertible to its ``value_type``.
 149 Requiring that it return an lvalue would rule out currently-legal
 150 random-access iterators which hold the referenced value in a data
 151 member (e.g. |counting|_), because ``*(p+n)`` is a reference
 152 into the temporary iterator ``p+n``, which is destroyed when
 153 ``operator[]`` returns.
 154
 155 .. |counting| replace:: ``counting_iterator``
 156
 157 Writable iterators built with ``iterator_facade`` implement the
 158 semantics required by the preferred resolution to `issue 299`_ and
 159 adopted by proposal n1550_: the result of ``p[n]`` is an object
 160 convertible to the iterator's ``value_type``, and ``p[n] = x`` is
 161 equivalent to ``*(p + n) = x`` (Note: This result object may be
 162 implemented as a proxy containing a copy of ``p+n``).  This approach
 163 will work properly for any random-access iterator regardless of the
 164 other details of its implementation.  A user who knows more about
 165 the implementation of her iterator is free to implement an
 166 ``operator[]`` that returns an lvalue in the derived iterator
 167 class; it will hide the one supplied by ``iterator_facade`` from
 168 clients of her iterator.
 169
 170 .. _n1550: http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2003/n1550.htm
 171
 172 .. _`issue 299`: http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#299
 173
 174 .. _`operator arrow`:
 175
 176
 177 ``operator->``
 178 --------------
 179
 180 The ``reference`` type of a readable iterator (and today's input
 181 iterator) need not in fact be a reference, so long as it is
 182 convertible to the iterator's ``value_type``.  When the ``value_type``
 183 is a class, however, it must still be possible to access members
 184 through ``operator->``.  Therefore, an iterator whose ``reference``
 185 type is not in fact a reference must return a proxy containing a copy
 186 of the referenced value from its ``operator->``.
 187
 188 The return types for ``iterator_facade``\ 's ``operator->`` and
 189 ``operator[]`` are not explicitly specified. Instead, those types
 190 are described in terms of a set of requirements, which must be
 191 satisfied by the ``iterator_facade`` implementation.
 192
 193 .. [Cop95] [Coplien, 1995] Coplien, J., Curiously Recurring Template
 194    Patterns, C++ Report, February 1995, pp. 24-27.
 195