]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |