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 11While the iterator interface is rich, there is a core subset of the 12interface that is necessary for all the functionality. We have 13identified the following core behaviors for iterators: 14 15* dereferencing 16* incrementing 17* decrementing 18* equality comparison 19* random-access motion 20* distance measurement 21 22In addition to the behaviors listed above, the core interface elements 23include the associated types exposed through iterator traits: 24``value_type``, ``reference``, ``difference_type``, and 25``iterator_category``. 26 27Iterator facade uses the Curiously Recurring Template 28Pattern (CRTP) [Cop95]_ so that the user can specify the behavior 29of ``iterator_facade`` in a derived class. Former designs used 30policy objects to specify the behavior, but that approach was 31discarded 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 51Usage 52----- 53 54The user of ``iterator_facade`` derives his iterator class from a 55specialization of ``iterator_facade`` and passes the derived 56iterator class as ``iterator_facade``\ 's first template parameter. 57The order of the other template parameters have been carefully 58chosen to take advantage of useful defaults. For example, when 59defining a constant lvalue iterator, the user can pass a 60const-qualified version of the iterator's ``value_type`` as 61``iterator_facade``\ 's ``Value`` parameter and omit the 62``Reference`` parameter which follows. 63 64The derived iterator class must define member functions implementing 65the iterator's core behaviors. The following table describes 66expressions which are required to be valid depending on the category 67of the derived iterator type. These member functions are described 68briefly below and in more detail in the iterator facade 69requirements. 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 90In addition to implementing the core interface functions, an iterator 91derived from ``iterator_facade`` typically defines several 92constructors. To model any of the standard iterator concepts, the 93iterator must at least have a copy constructor. Also, if the iterator 94type ``X`` is meant to be automatically interoperate with another 95iterator type ``Y`` (as with constant and mutable iterators) then 96there must be an implicit conversion from ``X`` to ``Y`` or from ``Y`` 97to ``X`` (but not both), typically implemented as a conversion 98constructor. Finally, if the iterator is to model Forward Traversal 99Iterator or a more-refined iterator concept, a default constructor is 100required. 101 102 103 104Iterator Core Access 105-------------------- 106 107``iterator_facade`` and the operator implementations need to be able 108to access the core member functions in the derived class. Making the 109core member functions public would expose an implementation detail to 110the user. The design used here ensures that implementation details do 111not appear in the public interface of the derived iterator type. 112 113Preventing direct access to the core member functions has two 114advantages. First, there is no possibility for the user to accidently 115use a member function of the iterator when a member of the value_type 116was intended. This has been an issue with smart pointer 117implementations in the past. The second and main advantage is that 118library implementers can freely exchange a hand-rolled iterator 119implementation for one based on ``iterator_facade`` without fear of 120breaking code that was accessing the public core member functions 121directly. 122 123In a naive implementation, keeping the derived class' core member 124functions private would require it to grant friendship to 125``iterator_facade`` and each of the seven operators. In order to 126reduce the burden of limiting access, ``iterator_core_access`` is 127provided, a class that acts as a gateway to the core member functions 128in the derived iterator class. The author of the derived class only 129needs to grant friendship to ``iterator_core_access`` to make his core 130member 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 136class containing only private static member functions which invoke the 137iterator core member functions. There is, however, no need to 138standardize the gateway protocol. Note that even if 139``iterator_core_access`` used public member functions it would not 140open a safety loophole, as every core member function preserves the 141invariants of the iterator. 142 143``operator[]`` 144-------------- 145 146The indexing operator for a generalized iterator presents special 147challenges. A random access iterator's ``operator[]`` is only 148required to return something convertible to its ``value_type``. 149Requiring that it return an lvalue would rule out currently-legal 150random-access iterators which hold the referenced value in a data 151member (e.g. |counting|_), because ``*(p+n)`` is a reference 152into the temporary iterator ``p+n``, which is destroyed when 153``operator[]`` returns. 154 155.. |counting| replace:: ``counting_iterator`` 156 157Writable iterators built with ``iterator_facade`` implement the 158semantics required by the preferred resolution to `issue 299`_ and 159adopted by proposal n1550_: the result of ``p[n]`` is an object 160convertible to the iterator's ``value_type``, and ``p[n] = x`` is 161equivalent to ``*(p + n) = x`` (Note: This result object may be 162implemented as a proxy containing a copy of ``p+n``). This approach 163will work properly for any random-access iterator regardless of the 164other details of its implementation. A user who knows more about 165the implementation of her iterator is free to implement an 166``operator[]`` that returns an lvalue in the derived iterator 167class; it will hide the one supplied by ``iterator_facade`` from 168clients 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 180The ``reference`` type of a readable iterator (and today's input 181iterator) need not in fact be a reference, so long as it is 182convertible to the iterator's ``value_type``. When the ``value_type`` 183is a class, however, it must still be possible to access members 184through ``operator->``. Therefore, an iterator whose ``reference`` 185type is not in fact a reference must return a proxy containing a copy 186of the referenced value from its ``operator->``. 187 188The return types for ``iterator_facade``\ 's ``operator->`` and 189``operator[]`` are not explicitly specified. Instead, those types 190are described in terms of a set of requirements, which must be 191satisfied 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 196