]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <?xml version="1.0" encoding="utf-8" ?> |
2 | <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> | |
3 | <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> | |
4 | <head> | |
5 | <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> | |
6 | <meta name="generator" content="Docutils 0.5: http://docutils.sourceforge.net/" /> | |
7 | <title>New Iterator Concepts</title> | |
8 | <meta name="author" content="David Abrahams, Jeremy Siek, Thomas Witt" /> | |
9 | <meta name="organization" content="Boost Consulting, Indiana University Open Systems Lab, Zephyr Associates, Inc." /> | |
10 | <meta name="date" content="2006-09-11" /> | |
11 | <meta name="copyright" content="Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003." /> | |
12 | <link rel="stylesheet" href="../../../rst.css" type="text/css" /> | |
13 | </head> | |
14 | <body> | |
15 | <div class="document" id="new-iterator-concepts"> | |
16 | <h1 class="title">New Iterator Concepts</h1> | |
17 | <table class="docinfo" frame="void" rules="none"> | |
18 | <col class="docinfo-name" /> | |
19 | <col class="docinfo-content" /> | |
20 | <tbody valign="top"> | |
21 | <tr><th class="docinfo-name">Author:</th> | |
22 | <td>David Abrahams, Jeremy Siek, Thomas Witt</td></tr> | |
23 | <tr><th class="docinfo-name">Contact:</th> | |
24 | <td><a class="first reference external" href="mailto:dave@boost-consulting.com">dave@boost-consulting.com</a>, <a class="reference external" href="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</a>, <a class="last reference external" href="mailto:witt@styleadvisor.com">witt@styleadvisor.com</a></td></tr> | |
25 | <tr><th class="docinfo-name">Organization:</th> | |
26 | <td><a class="first reference external" href="http://www.boost-consulting.com">Boost Consulting</a>, Indiana University <a class="reference external" href="http://www.osl.iu.edu">Open Systems | |
27 | Lab</a>, <a class="last reference external" href="http://www.styleadvisor.com">Zephyr Associates, Inc.</a></td></tr> | |
28 | <tr><th class="docinfo-name">Date:</th> | |
29 | <td>2006-09-11</td></tr> | |
30 | <tr class="field"><th class="docinfo-name">Number:</th><td class="field-body">This is a revised version of <a class="reference external" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1550.htm">n1550</a>=03-0133, which was | |
31 | accepted for Technical Report 1 by the C++ standard | |
32 | committee's library working group. This proposal is a | |
33 | revision of paper <a class="reference external" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2001/n1297.html">n1297</a>, <a class="reference external" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1477.html">n1477</a>, and <a class="reference external" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1531.html">n1531</a>.</td> | |
34 | </tr> | |
35 | <tr><th class="docinfo-name">Copyright:</th> | |
36 | <td>Copyright David Abrahams, Jeremy Siek, and Thomas Witt | |
37 | 2003.</td></tr> | |
38 | </tbody> | |
39 | </table> | |
40 | <!-- Distributed under the Boost --> | |
41 | <!-- Software License, Version 1.0. (See accompanying --> | |
42 | <!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) --> | |
43 | <!-- Version 1.25 of this ReStructuredText document is the same as | |
44 | n1550_, the paper accepted by the LWG. --> | |
45 | <table class="docutils field-list" frame="void" rules="none"> | |
46 | <col class="field-name" /> | |
47 | <col class="field-body" /> | |
48 | <tbody valign="top"> | |
49 | <tr class="field"><th class="field-name">Abstract:</th><td class="field-body">We propose a new system of iterator concepts that treat | |
50 | access and positioning independently. This allows the | |
51 | concepts to more closely match the requirements | |
52 | of algorithms and provides better categorizations | |
53 | of iterators that are used in practice.</td> | |
54 | </tr> | |
55 | </tbody> | |
56 | </table> | |
57 | <div class="contents topic" id="table-of-contents"> | |
58 | <p class="topic-title first">Table of Contents</p> | |
59 | <ul class="simple"> | |
60 | <li><a class="reference internal" href="#motivation" id="id1">Motivation</a></li> | |
61 | <li><a class="reference internal" href="#impact-on-the-standard" id="id2">Impact on the Standard</a><ul> | |
62 | <li><a class="reference internal" href="#possible-but-not-proposed-changes-to-the-working-paper" id="id3">Possible (but not proposed) Changes to the Working Paper</a><ul> | |
63 | <li><a class="reference internal" href="#changes-to-algorithm-requirements" id="id4">Changes to Algorithm Requirements</a></li> | |
64 | <li><a class="reference internal" href="#deprecations" id="id5">Deprecations</a></li> | |
65 | <li><a class="reference internal" href="#vector-bool" id="id6"><tt class="docutils literal"><span class="pre">vector<bool></span></tt></a></li> | |
66 | </ul> | |
67 | </li> | |
68 | </ul> | |
69 | </li> | |
70 | <li><a class="reference internal" href="#design" id="id7">Design</a></li> | |
71 | <li><a class="reference internal" href="#proposed-text" id="id8">Proposed Text</a><ul> | |
72 | <li><a class="reference internal" href="#addition-to-lib-iterator-requirements" id="id9">Addition to [lib.iterator.requirements]</a><ul> | |
73 | <li><a class="reference internal" href="#iterator-value-access-concepts-lib-iterator-value-access" id="id10">Iterator Value Access Concepts [lib.iterator.value.access]</a><ul> | |
74 | <li><a class="reference internal" href="#readable-iterators-lib-readable-iterators" id="id11">Readable Iterators [lib.readable.iterators]</a></li> | |
75 | <li><a class="reference internal" href="#writable-iterators-lib-writable-iterators" id="id12">Writable Iterators [lib.writable.iterators]</a></li> | |
76 | <li><a class="reference internal" href="#swappable-iterators-lib-swappable-iterators" id="id13">Swappable Iterators [lib.swappable.iterators]</a></li> | |
77 | <li><a class="reference internal" href="#lvalue-iterators-lib-lvalue-iterators" id="id14">Lvalue Iterators [lib.lvalue.iterators]</a></li> | |
78 | </ul> | |
79 | </li> | |
80 | <li><a class="reference internal" href="#iterator-traversal-concepts-lib-iterator-traversal" id="id15">Iterator Traversal Concepts [lib.iterator.traversal]</a><ul> | |
81 | <li><a class="reference internal" href="#incrementable-iterators-lib-incrementable-iterators" id="id16">Incrementable Iterators [lib.incrementable.iterators]</a></li> | |
82 | <li><a class="reference internal" href="#single-pass-iterators-lib-single-pass-iterators" id="id17">Single Pass Iterators [lib.single.pass.iterators]</a></li> | |
83 | <li><a class="reference internal" href="#forward-traversal-iterators-lib-forward-traversal-iterators" id="id18">Forward Traversal Iterators [lib.forward.traversal.iterators]</a></li> | |
84 | <li><a class="reference internal" href="#bidirectional-traversal-iterators-lib-bidirectional-traversal-iterators" id="id19">Bidirectional Traversal Iterators [lib.bidirectional.traversal.iterators]</a></li> | |
85 | <li><a class="reference internal" href="#random-access-traversal-iterators-lib-random-access-traversal-iterators" id="id20">Random Access Traversal Iterators [lib.random.access.traversal.iterators]</a></li> | |
86 | <li><a class="reference internal" href="#interoperable-iterators-lib-interoperable-iterators" id="id21">Interoperable Iterators [lib.interoperable.iterators]</a></li> | |
87 | </ul> | |
88 | </li> | |
89 | </ul> | |
90 | </li> | |
91 | <li><a class="reference internal" href="#addition-to-lib-iterator-synopsis" id="id22">Addition to [lib.iterator.synopsis]</a></li> | |
92 | <li><a class="reference internal" href="#addition-to-lib-iterator-traits" id="id23">Addition to [lib.iterator.traits]</a></li> | |
93 | </ul> | |
94 | </li> | |
95 | <li><a class="reference internal" href="#footnotes" id="id24">Footnotes</a></li> | |
96 | </ul> | |
97 | </div> | |
98 | <div class="section" id="motivation"> | |
99 | <h1><a class="toc-backref" href="#id1">Motivation</a></h1> | |
100 | <p>The standard iterator categories and requirements are flawed because | |
101 | they use a single hierarchy of concepts to address two orthogonal | |
102 | issues: <em>iterator traversal</em> and <em>value access</em>. As a result, many | |
103 | algorithms with requirements expressed in terms of the iterator | |
104 | categories are too strict. Also, many real-world iterators can not be | |
105 | accurately categorized. A proxy-based iterator with random-access | |
106 | traversal, for example, may only legally have a category of "input | |
107 | iterator", so generic algorithms are unable to take advantage of its | |
108 | random-access capabilities. The current iterator concept hierarchy is | |
109 | geared towards iterator traversal (hence the category names), while | |
110 | requirements that address value access sneak in at various places. The | |
111 | following table gives a summary of the current value access | |
112 | requirements in the iterator categories.</p> | |
113 | <table border="1" class="docutils"> | |
114 | <colgroup> | |
115 | <col width="31%" /> | |
116 | <col width="69%" /> | |
117 | </colgroup> | |
118 | <thead valign="bottom"> | |
119 | <tr><th class="head" colspan="2">Value Access Requirements in Existing Iterator Categories</th> | |
120 | </tr> | |
121 | </thead> | |
122 | <tbody valign="top"> | |
123 | <tr><td>Output Iterator</td> | |
124 | <td><tt class="docutils literal"><span class="pre">*i</span> <span class="pre">=</span> <span class="pre">a</span></tt></td> | |
125 | </tr> | |
126 | <tr><td>Input Iterator</td> | |
127 | <td><tt class="docutils literal"><span class="pre">*i</span></tt> is convertible to <tt class="docutils literal"><span class="pre">T</span></tt></td> | |
128 | </tr> | |
129 | <tr><td>Forward Iterator</td> | |
130 | <td><tt class="docutils literal"><span class="pre">*i</span></tt> is <tt class="docutils literal"><span class="pre">T&</span></tt> (or <tt class="docutils literal"><span class="pre">const</span> <span class="pre">T&</span></tt> once <a class="reference external" href="http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#200">issue 200</a> | |
131 | is resolved)</td> | |
132 | </tr> | |
133 | <tr><td>Random Access Iterator</td> | |
134 | <td><tt class="docutils literal"><span class="pre">i[n]</span></tt> is convertible to <tt class="docutils literal"><span class="pre">T</span></tt> (also <tt class="docutils literal"><span class="pre">i[n]</span> <span class="pre">=</span> <span class="pre">t</span></tt> | |
135 | is required for mutable iterators once <a class="reference external" href="http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#299">issue 299</a> | |
136 | is resolved)</td> | |
137 | </tr> | |
138 | </tbody> | |
139 | </table> | |
140 | <p>Because iterator traversal and value access are mixed together in a | |
141 | single hierarchy, many useful iterators can not be appropriately | |
142 | categorized. For example, <tt class="docutils literal"><span class="pre">vector<bool>::iterator</span></tt> is almost a | |
143 | random access iterator, but the return type is not <tt class="docutils literal"><span class="pre">bool&</span></tt> (see | |
144 | <a class="reference external" href="http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#96">issue 96</a> and Herb Sutter's paper J16/99-0008 = WG21 | |
145 | N1185). Therefore, the iterators of <tt class="docutils literal"><span class="pre">vector<bool></span></tt> only meet the | |
146 | requirements of input iterator and output iterator. This is so | |
147 | nonintuitive that the C++ standard contradicts itself on this point. | |
148 | In paragraph 23.2.4/1 it says that a <tt class="docutils literal"><span class="pre">vector</span></tt> is a sequence that | |
149 | supports random access iterators.</p> | |
150 | <p>Another difficult-to-categorize iterator is the transform iterator, an | |
151 | adaptor which applies a unary function object to the dereferenced | |
152 | value of the some underlying iterator (see <a class="reference external" href="http://www.boost.org/libs/utility/transform_iterator.htm">transform_iterator</a>). | |
153 | For unary functions such as <tt class="docutils literal"><span class="pre">times</span></tt>, the return type of | |
154 | <tt class="docutils literal"><span class="pre">operator*</span></tt> clearly needs to be the <tt class="docutils literal"><span class="pre">result_type</span></tt> of the function | |
155 | object, which is typically not a reference. Because random access | |
156 | iterators are required to return lvalues from <tt class="docutils literal"><span class="pre">operator*</span></tt>, if you | |
157 | wrap <tt class="docutils literal"><span class="pre">int*</span></tt> with a transform iterator, you do not get a random | |
158 | access iterator as might be expected, but an input iterator.</p> | |
159 | <p>A third example is found in the vertex and edge iterators of the | |
160 | <a class="reference external" href="http://www.boost.org/libs/graph/doc/table_of_contents.html">Boost Graph Library</a>. These iterators return vertex and edge | |
161 | descriptors, which are lightweight handles created on-the-fly. They | |
162 | must be returned by-value. As a result, their current standard | |
163 | iterator category is <tt class="docutils literal"><span class="pre">input_iterator_tag</span></tt>, which means that, | |
164 | strictly speaking, you could not use these iterators with algorithms | |
165 | like <tt class="docutils literal"><span class="pre">min_element()</span></tt>. As a temporary solution, the concept | |
166 | <a class="reference external" href="http://www.boost.org/libs/utility/MultiPassInputIterator.html">Multi-Pass Input Iterator</a> was introduced to describe the vertex and | |
167 | edge descriptors, but as the design notes for the concept suggest, a | |
168 | better solution is needed.</p> | |
169 | <p>In short, there are many useful iterators that do not fit into the | |
170 | current standard iterator categories. As a result, the following bad | |
171 | things happen:</p> | |
172 | <ul class="simple"> | |
173 | <li>Iterators are often mis-categorized.</li> | |
174 | <li>Algorithm requirements are more strict than necessary, because they | |
175 | cannot separate the need for random access or bidirectional | |
176 | traversal from the need for a true reference return type.</li> | |
177 | </ul> | |
178 | </div> | |
179 | <div class="section" id="impact-on-the-standard"> | |
180 | <h1><a class="toc-backref" href="#id2">Impact on the Standard</a></h1> | |
181 | <p>This proposal for TR1 is a pure extension. Further, the new iterator | |
182 | concepts are backward-compatible with the old iterator requirements, | |
183 | and old iterators are forward-compatible with the new iterator | |
184 | concepts. That is to say, iterators that satisfy the old requirements | |
185 | also satisfy appropriate concepts in the new system, and iterators | |
186 | modeling the new concepts will automatically satisfy the appropriate | |
187 | old requirements.</p> | |
188 | <!-- I think we need to say something about the resolution to allow | |
189 | convertibility to any of the old-style tags as a TR issue (hope it | |
190 | made it). -DWA --> | |
191 | <!-- Hmm, not sure I understand. Are you talking about whether a | |
192 | standards conforming input iterator is allowed to have | |
193 | a tag that is not input_iterator_tag but that | |
194 | is convertible to input_iterator_tag? -JGS --> | |
195 | <div class="section" id="possible-but-not-proposed-changes-to-the-working-paper"> | |
196 | <h2><a class="toc-backref" href="#id3">Possible (but not proposed) Changes to the Working Paper</a></h2> | |
197 | <p>The extensions in this paper suggest several changes we might make | |
198 | to the working paper for the next standard. These changes are not | |
199 | a formal part of this proposal for TR1.</p> | |
200 | <div class="section" id="changes-to-algorithm-requirements"> | |
201 | <h3><a class="toc-backref" href="#id4">Changes to Algorithm Requirements</a></h3> | |
202 | <p>The algorithms in the standard library could benefit from the new | |
203 | iterator concepts because the new concepts provide a more accurate way | |
204 | to express their type requirements. The result is algorithms that are | |
205 | usable in more situations and have fewer type requirements.</p> | |
206 | <p>For the next working paper (but not for TR1), the committee should | |
207 | consider the following changes to the type requirements of algorithms. | |
208 | These changes are phrased as textual substitutions, listing the | |
209 | algorithms to which each textual substitution applies.</p> | |
210 | <p>Forward Iterator -> Forward Traversal Iterator and Readable Iterator</p> | |
211 | <blockquote> | |
212 | <tt class="docutils literal"><span class="pre">find_end,</span> <span class="pre">adjacent_find,</span> <span class="pre">search,</span> <span class="pre">search_n,</span> <span class="pre">rotate_copy,</span> | |
213 | <span class="pre">lower_bound,</span> <span class="pre">upper_bound,</span> <span class="pre">equal_range,</span> <span class="pre">binary_search,</span> | |
214 | <span class="pre">min_element,</span> <span class="pre">max_element</span></tt></blockquote> | |
215 | <p>Forward Iterator (1) -> Single Pass Iterator and Readable Iterator, | |
216 | Forward Iterator (2) -> Forward Traversal Iterator and Readable Iterator</p> | |
217 | <blockquote> | |
218 | <tt class="docutils literal"><span class="pre">find_first_of</span></tt></blockquote> | |
219 | <p>Forward Iterator -> Readable Iterator and Writable Iterator</p> | |
220 | <blockquote> | |
221 | <tt class="docutils literal"><span class="pre">iter_swap</span></tt></blockquote> | |
222 | <p>Forward Iterator -> Single Pass Iterator and Writable Iterator</p> | |
223 | <blockquote> | |
224 | <tt class="docutils literal"><span class="pre">fill,</span> <span class="pre">generate</span></tt></blockquote> | |
225 | <p>Forward Iterator -> Forward Traversal Iterator and Swappable Iterator</p> | |
226 | <blockquote> | |
227 | <tt class="docutils literal"><span class="pre">rotate</span></tt></blockquote> | |
228 | <p>Forward Iterator (1) -> Swappable Iterator and Single Pass Iterator, | |
229 | Forward Iterator (2) -> Swappable Iterator and Incrementable Iterator</p> | |
230 | <blockquote> | |
231 | <tt class="docutils literal"><span class="pre">swap_ranges</span></tt></blockquote> | |
232 | <dl class="docutils"> | |
233 | <dt>Forward Iterator -> Forward Traversal Iterator and Readable Iterator and Writable Iterator</dt> | |
234 | <dd><tt class="docutils literal"><span class="pre">remove,</span> <span class="pre">remove_if,</span> <span class="pre">unique</span></tt></dd> | |
235 | </dl> | |
236 | <p>Forward Iterator -> Single Pass Iterator and Readable Iterator and Writable Iterator</p> | |
237 | <blockquote> | |
238 | <tt class="docutils literal"><span class="pre">replace,</span> <span class="pre">replace_if</span></tt></blockquote> | |
239 | <dl class="docutils"> | |
240 | <dt>Bidirectional Iterator -> Bidirectional Traversal Iterator and Swappable Iterator</dt> | |
241 | <dd><tt class="docutils literal"><span class="pre">reverse</span></tt></dd> | |
242 | <dt>Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable and Swappable Iterator</dt> | |
243 | <dd><tt class="docutils literal"><span class="pre">partition</span></tt></dd> | |
244 | </dl> | |
245 | <p>Bidirectional Iterator (1) -> Bidirectional Traversal Iterator and Readable Iterator, | |
246 | Bidirectional Iterator (2) -> Bidirectional Traversal Iterator and Writable Iterator</p> | |
247 | <blockquote> | |
248 | <tt class="docutils literal"><span class="pre">copy_backwards</span></tt></blockquote> | |
249 | <dl class="docutils"> | |
250 | <dt>Bidirectional Iterator -> Bidirectional Traversal Iterator and Swappable Iterator and Readable Iterator</dt> | |
251 | <dd><tt class="docutils literal"><span class="pre">next_permutation,</span> <span class="pre">prev_permutation</span></tt></dd> | |
252 | <dt>Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable Iterator and Writable Iterator</dt> | |
253 | <dd><tt class="docutils literal"><span class="pre">stable_partition,</span> <span class="pre">inplace_merge</span></tt></dd> | |
254 | <dt>Bidirectional Iterator -> Bidirectional Traversal Iterator and Readable Iterator</dt> | |
255 | <dd><tt class="docutils literal"><span class="pre">reverse_copy</span></tt></dd> | |
256 | <dt>Random Access Iterator -> Random Access Traversal Iterator and Readable and Writable Iterator</dt> | |
257 | <dd><tt class="docutils literal"><span class="pre">random_shuffle,</span> <span class="pre">sort,</span> <span class="pre">stable_sort,</span> <span class="pre">partial_sort,</span> <span class="pre">nth_element,</span> <span class="pre">push_heap,</span> <span class="pre">pop_heap</span> | |
258 | <span class="pre">make_heap,</span> <span class="pre">sort_heap</span></tt></dd> | |
259 | <dt>Input Iterator (2) -> Incrementable Iterator and Readable Iterator</dt> | |
260 | <dd><tt class="docutils literal"><span class="pre">equal,</span> <span class="pre">mismatch</span></tt></dd> | |
261 | <dt>Input Iterator (2) -> Incrementable Iterator and Readable Iterator</dt> | |
262 | <dd><tt class="docutils literal"><span class="pre">transform</span></tt></dd> | |
263 | </dl> | |
264 | </div> | |
265 | <div class="section" id="deprecations"> | |
266 | <h3><a class="toc-backref" href="#id5">Deprecations</a></h3> | |
267 | <p>For the next working paper (but not for TR1), the committee should | |
268 | consider deprecating the old iterator tags, and | |
269 | std::iterator_traits, since it will be superceded by individual | |
270 | traits metafunctions.</p> | |
271 | </div> | |
272 | <div class="section" id="vector-bool"> | |
273 | <h3><a class="toc-backref" href="#id6"><tt class="docutils literal"><span class="pre">vector<bool></span></tt></a></h3> | |
274 | <p>For the next working paper (but not for TR1), the committee should | |
275 | consider reclassifying <tt class="docutils literal"><span class="pre">vector<bool>::iterator</span></tt> as a Random | |
276 | Access Traversal Iterator and Readable Iterator and Writable | |
277 | Iterator.</p> | |
278 | </div> | |
279 | </div> | |
280 | </div> | |
281 | <div class="section" id="design"> | |
282 | <h1><a class="toc-backref" href="#id7">Design</a></h1> | |
283 | <p>The iterator requirements are to be separated into two groups. One set | |
284 | of concepts handles the syntax and semantics of value access:</p> | |
285 | <ul class="simple"> | |
286 | <li>Readable Iterator</li> | |
287 | <li>Writable Iterator</li> | |
288 | <li>Swappable Iterator</li> | |
289 | <li>Lvalue Iterator</li> | |
290 | </ul> | |
291 | <p>The access concepts describe requirements related to <tt class="docutils literal"><span class="pre">operator*</span></tt> and | |
292 | <tt class="docutils literal"><span class="pre">operator-></span></tt>, including the <tt class="docutils literal"><span class="pre">value_type</span></tt>, <tt class="docutils literal"><span class="pre">reference</span></tt>, and | |
293 | <tt class="docutils literal"><span class="pre">pointer</span></tt> associated types.</p> | |
294 | <p>The other set of concepts handles traversal:</p> | |
295 | <ul class="simple"> | |
296 | <li>Incrementable Iterator</li> | |
297 | <li>Single Pass Iterator</li> | |
298 | <li>Forward Traversal Iterator</li> | |
299 | <li>Bidirectional Traversal Iterator</li> | |
300 | <li>Random Access Traversal Iterator</li> | |
301 | </ul> | |
302 | <p>The refinement relationships for the traversal concepts are in the | |
303 | following diagram.</p> | |
304 | <img alt="traversal.png" src="traversal.png" /> | |
305 | <p>In addition to the iterator movement operators, such as | |
306 | <tt class="docutils literal"><span class="pre">operator++</span></tt>, the traversal concepts also include requirements on | |
307 | position comparison such as <tt class="docutils literal"><span class="pre">operator==</span></tt> and <tt class="docutils literal"><span class="pre">operator<</span></tt>. The | |
308 | reason for the fine grain slicing of the concepts into the | |
309 | Incrementable and Single Pass is to provide concepts that are exact | |
310 | matches with the original input and output iterator requirements.</p> | |
311 | <p>This proposal also includes a concept for specifying when an iterator | |
312 | is interoperable with another iterator, in the sense that <tt class="docutils literal"><span class="pre">int*</span></tt> is | |
313 | interoperable with <tt class="docutils literal"><span class="pre">int</span> <span class="pre">const*</span></tt>.</p> | |
314 | <ul class="simple"> | |
315 | <li>Interoperable Iterators</li> | |
316 | </ul> | |
317 | <p>The relationship between the new iterator concepts and the old are | |
318 | given in the following diagram.</p> | |
319 | <img alt="oldeqnew.png" src="oldeqnew.png" /> | |
320 | <p>Like the old iterator requirements, we provide tags for purposes of | |
321 | dispatching based on the traversal concepts. The tags are related via | |
322 | inheritance so that a tag is convertible to another tag if the concept | |
323 | associated with the first tag is a refinement of the second tag.</p> | |
324 | <p>Our design reuses <tt class="docutils literal"><span class="pre">iterator_traits<Iter>::iterator_category</span></tt> to | |
325 | indicate an iterator's traversal capability. To specify | |
326 | capabilities not captured by any old-style iterator category, an | |
327 | iterator designer can use an <tt class="docutils literal"><span class="pre">iterator_category</span></tt> type that is | |
328 | convertible to both the the most-derived old iterator category tag | |
329 | which fits, and the appropriate new iterator traversal tag.</p> | |
330 | <!-- dwa2003/1/2: Note that we are not *requiring* convertibility to | |
331 | a new-style traversal tag in order to meet new concepts. | |
332 | Old-style iterators still fit, after all. --> | |
333 | <p>We do not provide tags for the purposes of dispatching based on the | |
334 | access concepts, in part because we could not find a way to | |
335 | automatically infer the right access tags for old-style iterators. | |
336 | An iterator's writability may be dependent on the assignability of | |
337 | its <tt class="docutils literal"><span class="pre">value_type</span></tt> and there's no known way to detect whether an | |
338 | arbitrary type is assignable. Fortunately, the need for | |
339 | dispatching based on access capability is not as great as the need | |
340 | for dispatching based on traversal capability.</p> | |
341 | <p>A difficult design decision concerned the <tt class="docutils literal"><span class="pre">operator[]</span></tt>. The direct | |
342 | approach for specifying <tt class="docutils literal"><span class="pre">operator[]</span></tt> would have a return type of | |
343 | <tt class="docutils literal"><span class="pre">reference</span></tt>; the same as <tt class="docutils literal"><span class="pre">operator*</span></tt>. However, going in this | |
344 | direction would mean that an iterator satisfying the old Random Access | |
345 | Iterator requirements would not necessarily be a model of Readable or | |
346 | Writable Lvalue Iterator. Instead we have chosen a design that | |
347 | matches the preferred resolution of <a class="reference external" href="http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#299">issue 299</a>: <tt class="docutils literal"><span class="pre">operator[]</span></tt> is | |
348 | only required to return something convertible to the <tt class="docutils literal"><span class="pre">value_type</span></tt> | |
349 | (for a Readable Iterator), and is required to support assignment | |
350 | <tt class="docutils literal"><span class="pre">i[n]</span> <span class="pre">=</span> <span class="pre">t</span></tt> (for a Writable Iterator).</p> | |
351 | </div> | |
352 | <div class="section" id="proposed-text"> | |
353 | <h1><a class="toc-backref" href="#id8">Proposed Text</a></h1> | |
354 | <div class="section" id="addition-to-lib-iterator-requirements"> | |
355 | <h2><a class="toc-backref" href="#id9">Addition to [lib.iterator.requirements]</a></h2> | |
356 | <div class="section" id="iterator-value-access-concepts-lib-iterator-value-access"> | |
357 | <h3><a class="toc-backref" href="#id10">Iterator Value Access Concepts [lib.iterator.value.access]</a></h3> | |
358 | <p>In the tables below, <tt class="docutils literal"><span class="pre">X</span></tt> is an iterator type, <tt class="docutils literal"><span class="pre">a</span></tt> is a constant | |
359 | object of type <tt class="docutils literal"><span class="pre">X</span></tt>, <tt class="docutils literal"><span class="pre">R</span></tt> is | |
360 | <tt class="docutils literal"><span class="pre">std::iterator_traits<X>::reference</span></tt>, <tt class="docutils literal"><span class="pre">T</span></tt> is | |
361 | <tt class="docutils literal"><span class="pre">std::iterator_traits<X>::value_type</span></tt>, and <tt class="docutils literal"><span class="pre">v</span></tt> is a constant | |
362 | object of type <tt class="docutils literal"><span class="pre">T</span></tt>.</p> | |
363 | <div class="section" id="readable-iterators-lib-readable-iterators"> | |
364 | <span id="readable-iterator"></span><h4><a class="toc-backref" href="#id11">Readable Iterators [lib.readable.iterators]</a></h4> | |
365 | <p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Readable Iterator</em> concept | |
366 | for value type <tt class="docutils literal"><span class="pre">T</span></tt> if, in addition to <tt class="docutils literal"><span class="pre">X</span></tt> being Assignable and | |
367 | Copy Constructible, the following expressions are valid and respect | |
368 | the stated semantics. <tt class="docutils literal"><span class="pre">U</span></tt> is the type of any specified member of | |
369 | type <tt class="docutils literal"><span class="pre">T</span></tt>.</p> | |
370 | <table border="1" class="docutils"> | |
371 | <colgroup> | |
372 | <col width="28%" /> | |
373 | <col width="20%" /> | |
374 | <col width="52%" /> | |
375 | </colgroup> | |
376 | <thead valign="bottom"> | |
377 | <tr><th class="head" colspan="3">Readable Iterator Requirements (in addition to Assignable and Copy Constructible)</th> | |
378 | </tr> | |
379 | <tr><th class="head">Expression</th> | |
380 | <th class="head">Return Type</th> | |
381 | <th class="head">Note/Precondition</th> | |
382 | </tr> | |
383 | </thead> | |
384 | <tbody valign="top"> | |
385 | <tr><td><tt class="docutils literal"><span class="pre">iterator_traits<X>::value_type</span></tt></td> | |
386 | <td><tt class="docutils literal"><span class="pre">T</span></tt></td> | |
387 | <td>Any non-reference, | |
388 | non-cv-qualified type</td> | |
389 | </tr> | |
390 | <tr><td><tt class="docutils literal"><span class="pre">*a</span></tt></td> | |
391 | <td>Convertible to <tt class="docutils literal"><span class="pre">T</span></tt></td> | |
392 | <td><dl class="first last docutils"> | |
393 | <dt>pre: <tt class="docutils literal"><span class="pre">a</span></tt> is dereferenceable. If <tt class="docutils literal"><span class="pre">a</span> <span class="pre">==</span> <span class="pre">b</span></tt> then <tt class="docutils literal"><span class="pre">*a</span></tt></dt> | |
394 | <dd>is equivalent to <tt class="docutils literal"><span class="pre">*b</span></tt>.</dd> | |
395 | </dl> | |
396 | </td> | |
397 | </tr> | |
398 | <tr><td><tt class="docutils literal"><span class="pre">a->m</span></tt></td> | |
399 | <td><tt class="docutils literal"><span class="pre">U&</span></tt></td> | |
400 | <td>pre: <tt class="docutils literal"><span class="pre">pre:</span> <span class="pre">(*a).m</span></tt> is well-defined. Equivalent to <tt class="docutils literal"><span class="pre">(*a).m</span></tt>.</td> | |
401 | </tr> | |
402 | </tbody> | |
403 | </table> | |
404 | <!-- We won't say anything about iterator_traits<X>::reference until the DR is resolved. -JGS --> | |
405 | </div> | |
406 | <div class="section" id="writable-iterators-lib-writable-iterators"> | |
407 | <span id="writable-iterator"></span><h4><a class="toc-backref" href="#id12">Writable Iterators [lib.writable.iterators]</a></h4> | |
408 | <p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Writable Iterator</em> concept | |
409 | if, in addition to <tt class="docutils literal"><span class="pre">X</span></tt> being Copy Constructible, the following | |
410 | expressions are valid and respect the stated semantics. Writable | |
411 | Iterators have an associated <em>set of value types</em>.</p> | |
412 | <table border="1" class="docutils"> | |
413 | <colgroup> | |
414 | <col width="37%" /> | |
415 | <col width="21%" /> | |
416 | <col width="42%" /> | |
417 | </colgroup> | |
418 | <thead valign="bottom"> | |
419 | <tr><th class="head" colspan="3">Writable Iterator Requirements (in addition to Copy Constructible)</th> | |
420 | </tr> | |
421 | <tr><th class="head">Expression</th> | |
422 | <th class="head">Return Type</th> | |
423 | <th class="head">Precondition</th> | |
424 | </tr> | |
425 | </thead> | |
426 | <tbody valign="top"> | |
427 | <tr><td><tt class="docutils literal"><span class="pre">*a</span> <span class="pre">=</span> <span class="pre">o</span></tt></td> | |
428 | <td> </td> | |
429 | <td>pre: The type of <tt class="docutils literal"><span class="pre">o</span></tt> | |
430 | is in the set of | |
431 | value types of <tt class="docutils literal"><span class="pre">X</span></tt></td> | |
432 | </tr> | |
433 | </tbody> | |
434 | </table> | |
435 | </div> | |
436 | <div class="section" id="swappable-iterators-lib-swappable-iterators"> | |
437 | <h4><a class="toc-backref" href="#id13">Swappable Iterators [lib.swappable.iterators]</a></h4> | |
438 | <p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Swappable Iterator</em> concept | |
439 | if, in addition to <tt class="docutils literal"><span class="pre">X</span></tt> being Copy Constructible, the following | |
440 | expressions are valid and respect the stated semantics.</p> | |
441 | <table border="1" class="docutils"> | |
442 | <colgroup> | |
443 | <col width="37%" /> | |
444 | <col width="19%" /> | |
445 | <col width="43%" /> | |
446 | </colgroup> | |
447 | <thead valign="bottom"> | |
448 | <tr><th class="head" colspan="3">Swappable Iterator Requirements (in addition to Copy Constructible)</th> | |
449 | </tr> | |
450 | <tr><th class="head">Expression</th> | |
451 | <th class="head">Return Type</th> | |
452 | <th class="head">Postcondition</th> | |
453 | </tr> | |
454 | </thead> | |
455 | <tbody valign="top"> | |
456 | <tr><td><tt class="docutils literal"><span class="pre">iter_swap(a,</span> <span class="pre">b)</span></tt></td> | |
457 | <td><tt class="docutils literal"><span class="pre">void</span></tt></td> | |
458 | <td>the pointed to values are | |
459 | exchanged</td> | |
460 | </tr> | |
461 | </tbody> | |
462 | </table> | |
463 | <p>[<em>Note:</em> An iterator that is a model of the <a class="reference internal" href="#readable-iterator">Readable Iterator</a> and | |
464 | <a class="reference internal" href="#writable-iterator">Writable Iterator</a> concepts is also a model of <em>Swappable | |
465 | Iterator</em>. <em>--end note</em>]</p> | |
466 | </div> | |
467 | <div class="section" id="lvalue-iterators-lib-lvalue-iterators"> | |
468 | <h4><a class="toc-backref" href="#id14">Lvalue Iterators [lib.lvalue.iterators]</a></h4> | |
469 | <p>The <em>Lvalue Iterator</em> concept adds the requirement that the return | |
470 | type of <tt class="docutils literal"><span class="pre">operator*</span></tt> type be a reference to the value type of the | |
471 | iterator.</p> | |
472 | <table border="1" class="docutils"> | |
473 | <colgroup> | |
474 | <col width="22%" /> | |
475 | <col width="19%" /> | |
476 | <col width="59%" /> | |
477 | </colgroup> | |
478 | <thead valign="bottom"> | |
479 | <tr><th class="head" colspan="3">Lvalue Iterator Requirements</th> | |
480 | </tr> | |
481 | <tr><th class="head">Expression</th> | |
482 | <th class="head">Return Type</th> | |
483 | <th class="head">Note/Assertion</th> | |
484 | </tr> | |
485 | </thead> | |
486 | <tbody valign="top"> | |
487 | <tr><td><tt class="docutils literal"><span class="pre">*a</span></tt></td> | |
488 | <td><tt class="docutils literal"><span class="pre">T&</span></tt></td> | |
489 | <td><tt class="docutils literal"><span class="pre">T</span></tt> is <em>cv</em> | |
490 | <tt class="docutils literal"><span class="pre">iterator_traits<X>::value_type</span></tt> | |
491 | where <em>cv</em> is an optional | |
492 | cv-qualification. pre: <tt class="docutils literal"><span class="pre">a</span></tt> is | |
493 | dereferenceable.</td> | |
494 | </tr> | |
495 | </tbody> | |
496 | </table> | |
497 | <p>If <tt class="docutils literal"><span class="pre">X</span></tt> is a <a class="reference internal" href="#writable-iterator">Writable Iterator</a> then <tt class="docutils literal"><span class="pre">a</span> <span class="pre">==</span> <span class="pre">b</span></tt> if and only if | |
498 | <tt class="docutils literal"><span class="pre">*a</span></tt> is the same object as <tt class="docutils literal"><span class="pre">*b</span></tt>. If <tt class="docutils literal"><span class="pre">X</span></tt> is a <a class="reference internal" href="#readable-iterator">Readable | |
499 | Iterator</a> then <tt class="docutils literal"><span class="pre">a</span> <span class="pre">==</span> <span class="pre">b</span></tt> implies <tt class="docutils literal"><span class="pre">*a</span></tt> is the same object as | |
500 | <tt class="docutils literal"><span class="pre">*b</span></tt>.</p> | |
501 | </div> | |
502 | </div> | |
503 | <div class="section" id="iterator-traversal-concepts-lib-iterator-traversal"> | |
504 | <h3><a class="toc-backref" href="#id15">Iterator Traversal Concepts [lib.iterator.traversal]</a></h3> | |
505 | <p>In the tables below, <tt class="docutils literal"><span class="pre">X</span></tt> is an iterator type, <tt class="docutils literal"><span class="pre">a</span></tt> and <tt class="docutils literal"><span class="pre">b</span></tt> are | |
506 | constant objects of type <tt class="docutils literal"><span class="pre">X</span></tt>, <tt class="docutils literal"><span class="pre">r</span></tt> and <tt class="docutils literal"><span class="pre">s</span></tt> are mutable objects of | |
507 | type <tt class="docutils literal"><span class="pre">X</span></tt>, <tt class="docutils literal"><span class="pre">T</span></tt> is <tt class="docutils literal"><span class="pre">std::iterator_traits<X>::value_type</span></tt>, and | |
508 | <tt class="docutils literal"><span class="pre">v</span></tt> is a constant object of type <tt class="docutils literal"><span class="pre">T</span></tt>.</p> | |
509 | <div class="section" id="incrementable-iterators-lib-incrementable-iterators"> | |
510 | <h4><a class="toc-backref" href="#id16">Incrementable Iterators [lib.incrementable.iterators]</a></h4> | |
511 | <p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Incrementable Iterator</em> | |
512 | concept if, in addition to <tt class="docutils literal"><span class="pre">X</span></tt> being Assignable and Copy | |
513 | Constructible, the following expressions are valid and respect the | |
514 | stated semantics.</p> | |
515 | <table border="1" class="docutils"> | |
516 | <colgroup> | |
517 | <col width="39%" /> | |
518 | <col width="38%" /> | |
519 | <col width="23%" /> | |
520 | </colgroup> | |
521 | <thead valign="bottom"> | |
522 | <tr><th class="head" colspan="3">Incrementable Iterator Requirements (in addition to Assignable, Copy Constructible)</th> | |
523 | </tr> | |
524 | <tr><th class="head">Expression</th> | |
525 | <th class="head">Return Type</th> | |
526 | <th class="head">Assertion</th> | |
527 | </tr> | |
528 | </thead> | |
529 | <tbody valign="top"> | |
530 | <tr><td><tt class="docutils literal"><span class="pre">++r</span></tt></td> | |
531 | <td><tt class="docutils literal"><span class="pre">X&</span></tt></td> | |
532 | <td><tt class="docutils literal"><span class="pre">&r</span> <span class="pre">==</span> <span class="pre">&++r</span></tt></td> | |
533 | </tr> | |
534 | <tr><td><tt class="docutils literal"><span class="pre">r++</span></tt></td> | |
535 | <td> </td> | |
536 | <td> </td> | |
537 | </tr> | |
538 | <tr><td><tt class="docutils literal"><span class="pre">*r++</span></tt></td> | |
539 | <td> </td> | |
540 | <td> </td> | |
541 | </tr> | |
542 | <tr><td><tt class="docutils literal"><span class="pre">iterator_traversal<X>::type</span></tt></td> | |
543 | <td>Convertible to | |
544 | <tt class="docutils literal"><span class="pre">incrementable_traversal_tag</span></tt></td> | |
545 | <td> </td> | |
546 | </tr> | |
547 | </tbody> | |
548 | </table> | |
549 | <p>If <tt class="docutils literal"><span class="pre">X</span></tt> is a <a class="reference internal" href="#writable-iterator">Writable Iterator</a> then <tt class="docutils literal"><span class="pre">X</span> <span class="pre">a(r++);</span></tt> is equivalent | |
550 | to <tt class="docutils literal"><span class="pre">X</span> <span class="pre">a(r);</span> <span class="pre">++r;</span></tt> and <tt class="docutils literal"><span class="pre">*r++</span> <span class="pre">=</span> <span class="pre">o</span></tt> is equivalent | |
551 | to <tt class="docutils literal"><span class="pre">*r</span> <span class="pre">=</span> <span class="pre">o;</span> <span class="pre">++r</span></tt>. | |
552 | If <tt class="docutils literal"><span class="pre">X</span></tt> is a <a class="reference internal" href="#readable-iterator">Readable Iterator</a> then <tt class="docutils literal"><span class="pre">T</span> <span class="pre">z(*r++);</span></tt> is equivalent | |
553 | to <tt class="docutils literal"><span class="pre">T</span> <span class="pre">z(*r);</span> <span class="pre">++r;</span></tt>.</p> | |
554 | <!-- TR1: incrementable_iterator_tag changed to | |
555 | incrementable_traversal_tag for consistency. --> | |
556 | </div> | |
557 | <div class="section" id="single-pass-iterators-lib-single-pass-iterators"> | |
558 | <h4><a class="toc-backref" href="#id17">Single Pass Iterators [lib.single.pass.iterators]</a></h4> | |
559 | <p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Single Pass Iterator</em> | |
560 | concept if the following expressions are valid and respect the stated | |
561 | semantics.</p> | |
562 | <table border="1" class="docutils"> | |
563 | <colgroup> | |
564 | <col width="37%" /> | |
565 | <col width="27%" /> | |
566 | <col width="12%" /> | |
567 | <col width="25%" /> | |
568 | </colgroup> | |
569 | <thead valign="bottom"> | |
570 | <tr><th class="head" colspan="4">Single Pass Iterator Requirements (in addition to Incrementable Iterator and Equality | |
571 | Comparable)</th> | |
572 | </tr> | |
573 | <tr><th class="head">Expression</th> | |
574 | <th class="head">Return Type</th> | |
575 | <th class="head">Operational | |
576 | Semantics</th> | |
577 | <th class="head">Assertion/ | |
578 | Pre-/Post-condition</th> | |
579 | </tr> | |
580 | </thead> | |
581 | <tbody valign="top"> | |
582 | <tr><td><tt class="docutils literal"><span class="pre">++r</span></tt></td> | |
583 | <td><tt class="docutils literal"><span class="pre">X&</span></tt></td> | |
584 | <td> </td> | |
585 | <td>pre: <tt class="docutils literal"><span class="pre">r</span></tt> is | |
586 | dereferenceable; post: | |
587 | <tt class="docutils literal"><span class="pre">r</span></tt> is dereferenceable or | |
588 | <tt class="docutils literal"><span class="pre">r</span></tt> is past-the-end</td> | |
589 | </tr> | |
590 | <tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">==</span> <span class="pre">b</span></tt></td> | |
591 | <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> | |
592 | <td> </td> | |
593 | <td><tt class="docutils literal"><span class="pre">==</span></tt> is an equivalence | |
594 | relation over its domain</td> | |
595 | </tr> | |
596 | <tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">!=</span> <span class="pre">b</span></tt></td> | |
597 | <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> | |
598 | <td><tt class="docutils literal"><span class="pre">!(a</span> <span class="pre">==</span> <span class="pre">b)</span></tt></td> | |
599 | <td> </td> | |
600 | </tr> | |
601 | <tr><td><tt class="docutils literal"><span class="pre">iterator_traits<X>::difference_type</span></tt></td> | |
602 | <td>A signed integral type | |
603 | representing the distance | |
604 | between iterators</td> | |
605 | <td> </td> | |
606 | <td> </td> | |
607 | </tr> | |
608 | <tr><td><tt class="docutils literal"><span class="pre">iterator_traversal<X>::type</span></tt></td> | |
609 | <td>Convertible to | |
610 | <tt class="docutils literal"><span class="pre">single_pass_traversal_tag</span></tt></td> | |
611 | <td> </td> | |
612 | <td> </td> | |
613 | </tr> | |
614 | </tbody> | |
615 | </table> | |
616 | <!-- TR1: single_pass_iterator_tag changed to | |
617 | single_pass_traversal_tag for consistency --> | |
618 | </div> | |
619 | <div class="section" id="forward-traversal-iterators-lib-forward-traversal-iterators"> | |
620 | <h4><a class="toc-backref" href="#id18">Forward Traversal Iterators [lib.forward.traversal.iterators]</a></h4> | |
621 | <p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Forward Traversal Iterator</em> | |
622 | concept if, in addition to <tt class="docutils literal"><span class="pre">X</span></tt> meeting the requirements of Default | |
623 | Constructible and Single Pass Iterator, the following expressions are | |
624 | valid and respect the stated semantics.</p> | |
625 | <table border="1" class="docutils"> | |
626 | <colgroup> | |
627 | <col width="38%" /> | |
628 | <col width="34%" /> | |
629 | <col width="27%" /> | |
630 | </colgroup> | |
631 | <thead valign="bottom"> | |
632 | <tr><th class="head" colspan="3">Forward Traversal Iterator Requirements (in addition to Default Constructible and Single Pass Iterator)</th> | |
633 | </tr> | |
634 | <tr><th class="head">Expression</th> | |
635 | <th class="head">Return Type</th> | |
636 | <th class="head">Assertion/Note</th> | |
637 | </tr> | |
638 | </thead> | |
639 | <tbody valign="top"> | |
640 | <tr><td><tt class="docutils literal"><span class="pre">X</span> <span class="pre">u;</span></tt></td> | |
641 | <td><tt class="docutils literal"><span class="pre">X&</span></tt></td> | |
642 | <td>note: <tt class="docutils literal"><span class="pre">u</span></tt> may have a | |
643 | singular value.</td> | |
644 | </tr> | |
645 | <tr><td><tt class="docutils literal"><span class="pre">++r</span></tt></td> | |
646 | <td><tt class="docutils literal"><span class="pre">X&</span></tt></td> | |
647 | <td><tt class="docutils literal"><span class="pre">r</span> <span class="pre">==</span> <span class="pre">s</span></tt> and <tt class="docutils literal"><span class="pre">r</span></tt> is | |
648 | dereferenceable implies | |
649 | <tt class="docutils literal"><span class="pre">++r</span> <span class="pre">==</span> <span class="pre">++s.</span></tt></td> | |
650 | </tr> | |
651 | <tr><td><tt class="docutils literal"><span class="pre">iterator_traversal<X>::type</span></tt></td> | |
652 | <td>Convertible to | |
653 | <tt class="docutils literal"><span class="pre">forward_traversal_tag</span></tt></td> | |
654 | <td> </td> | |
655 | </tr> | |
656 | </tbody> | |
657 | </table> | |
658 | <!-- TR1: forward_traversal_iterator_tag changed to | |
659 | forward_traversal_tag for consistency --> | |
660 | </div> | |
661 | <div class="section" id="bidirectional-traversal-iterators-lib-bidirectional-traversal-iterators"> | |
662 | <h4><a class="toc-backref" href="#id19">Bidirectional Traversal Iterators [lib.bidirectional.traversal.iterators]</a></h4> | |
663 | <p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Bidirectional Traversal | |
664 | Iterator</em> concept if, in addition to <tt class="docutils literal"><span class="pre">X</span></tt> meeting the requirements of | |
665 | Forward Traversal Iterator, the following expressions are valid and | |
666 | respect the stated semantics.</p> | |
667 | <table border="1" class="docutils"> | |
668 | <colgroup> | |
669 | <col width="33%" /> | |
670 | <col width="32%" /> | |
671 | <col width="14%" /> | |
672 | <col width="21%" /> | |
673 | </colgroup> | |
674 | <thead valign="bottom"> | |
675 | <tr><th class="head" colspan="4">Bidirectional Traversal Iterator Requirements (in addition to Forward Traversal | |
676 | Iterator)</th> | |
677 | </tr> | |
678 | <tr><th class="head">Expression</th> | |
679 | <th class="head">Return Type</th> | |
680 | <th class="head">Operational | |
681 | Semantics</th> | |
682 | <th class="head">Assertion/ | |
683 | Pre-/Post-condition</th> | |
684 | </tr> | |
685 | </thead> | |
686 | <tbody valign="top"> | |
687 | <tr><td><tt class="docutils literal"><span class="pre">--r</span></tt></td> | |
688 | <td><tt class="docutils literal"><span class="pre">X&</span></tt></td> | |
689 | <td> </td> | |
690 | <td><p class="first">pre: there exists | |
691 | <tt class="docutils literal"><span class="pre">s</span></tt> such that <tt class="docutils literal"><span class="pre">r</span> | |
692 | <span class="pre">==</span> <span class="pre">++s</span></tt>. post: | |
693 | <tt class="docutils literal"><span class="pre">s</span></tt> is | |
694 | dereferenceable.</p> | |
695 | <p class="last"><tt class="docutils literal"><span class="pre">++(--r)</span> <span class="pre">==</span> <span class="pre">r</span></tt>. | |
696 | <tt class="docutils literal"><span class="pre">--r</span> <span class="pre">==</span> <span class="pre">--s</span></tt> | |
697 | implies <tt class="docutils literal"><span class="pre">r</span> <span class="pre">==</span> | |
698 | <span class="pre">s</span></tt>. <tt class="docutils literal"><span class="pre">&r</span> <span class="pre">==</span> <span class="pre">&--r</span></tt>.</p> | |
699 | </td> | |
700 | </tr> | |
701 | <tr><td><tt class="docutils literal"><span class="pre">r--</span></tt></td> | |
702 | <td>convertible to <tt class="docutils literal"><span class="pre">const</span> <span class="pre">X&</span></tt></td> | |
703 | <td><pre class="first last literal-block"> | |
704 | { | |
705 | X tmp = r; | |
706 | --r; | |
707 | return tmp; | |
708 | } | |
709 | </pre> | |
710 | </td> | |
711 | <td> </td> | |
712 | </tr> | |
713 | <tr><td><tt class="docutils literal"><span class="pre">iterator_traversal<X>::type</span></tt></td> | |
714 | <td>Convertible to | |
715 | <tt class="docutils literal"><span class="pre">bidirectional_traversal_tag</span></tt></td> | |
716 | <td> </td> | |
717 | <td> </td> | |
718 | </tr> | |
719 | </tbody> | |
720 | </table> | |
721 | <!-- TR1: bidirectional_traversal_iterator_tag changed to | |
722 | bidirectional_traversal_tag for consistency --> | |
723 | </div> | |
724 | <div class="section" id="random-access-traversal-iterators-lib-random-access-traversal-iterators"> | |
725 | <h4><a class="toc-backref" href="#id20">Random Access Traversal Iterators [lib.random.access.traversal.iterators]</a></h4> | |
726 | <p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> models the <em>Random Access Traversal | |
727 | Iterator</em> concept if the following expressions are valid and respect | |
728 | the stated semantics. In the table below, <tt class="docutils literal"><span class="pre">Distance</span></tt> is | |
729 | <tt class="docutils literal"><span class="pre">iterator_traits<X>::difference_type</span></tt> and <tt class="docutils literal"><span class="pre">n</span></tt> represents a | |
730 | constant object of type <tt class="docutils literal"><span class="pre">Distance</span></tt>.</p> | |
731 | <table border="1" class="docutils"> | |
732 | <colgroup> | |
733 | <col width="28%" /> | |
734 | <col width="30%" /> | |
735 | <col width="23%" /> | |
736 | <col width="20%" /> | |
737 | </colgroup> | |
738 | <thead valign="bottom"> | |
739 | <tr><th class="head" colspan="4">Random Access Traversal Iterator Requirements (in addition to Bidirectional Traversal Iterator)</th> | |
740 | </tr> | |
741 | <tr><th class="head">Expression</th> | |
742 | <th class="head">Return Type</th> | |
743 | <th class="head">Operational Semantics</th> | |
744 | <th class="head">Assertion/ | |
745 | Precondition</th> | |
746 | </tr> | |
747 | </thead> | |
748 | <tbody valign="top"> | |
749 | <tr><td><tt class="docutils literal"><span class="pre">r</span> <span class="pre">+=</span> <span class="pre">n</span></tt></td> | |
750 | <td><tt class="docutils literal"><span class="pre">X&</span></tt></td> | |
751 | <td><pre class="first last literal-block"> | |
752 | { | |
753 | Distance m = n; | |
754 | if (m >= 0) | |
755 | while (m--) | |
756 | ++r; | |
757 | else | |
758 | while (m++) | |
759 | --r; | |
760 | return r; | |
761 | } | |
762 | </pre> | |
763 | </td> | |
764 | <td> </td> | |
765 | </tr> | |
766 | <tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">+</span> <span class="pre">n</span></tt>, <tt class="docutils literal"><span class="pre">n</span> <span class="pre">+</span> <span class="pre">a</span></tt></td> | |
767 | <td><tt class="docutils literal"><span class="pre">X</span></tt></td> | |
768 | <td><tt class="docutils literal"><span class="pre">{</span> <span class="pre">X</span> <span class="pre">tmp</span> <span class="pre">=</span> <span class="pre">a;</span> <span class="pre">return</span> <span class="pre">tmp</span> | |
769 | <span class="pre">+=</span> <span class="pre">n;</span> <span class="pre">}</span></tt></td> | |
770 | <td> </td> | |
771 | </tr> | |
772 | <tr><td><tt class="docutils literal"><span class="pre">r</span> <span class="pre">-=</span> <span class="pre">n</span></tt></td> | |
773 | <td><tt class="docutils literal"><span class="pre">X&</span></tt></td> | |
774 | <td><tt class="docutils literal"><span class="pre">return</span> <span class="pre">r</span> <span class="pre">+=</span> <span class="pre">-n</span></tt></td> | |
775 | <td> </td> | |
776 | </tr> | |
777 | <tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">-</span> <span class="pre">n</span></tt></td> | |
778 | <td><tt class="docutils literal"><span class="pre">X</span></tt></td> | |
779 | <td><tt class="docutils literal"><span class="pre">{</span> <span class="pre">X</span> <span class="pre">tmp</span> <span class="pre">=</span> <span class="pre">a;</span> <span class="pre">return</span> <span class="pre">tmp</span> | |
780 | <span class="pre">-=</span> <span class="pre">n;</span> <span class="pre">}</span></tt></td> | |
781 | <td> </td> | |
782 | </tr> | |
783 | <tr><td><tt class="docutils literal"><span class="pre">b</span> <span class="pre">-</span> <span class="pre">a</span></tt></td> | |
784 | <td><tt class="docutils literal"><span class="pre">Distance</span></tt></td> | |
785 | <td><tt class="docutils literal"><span class="pre">a</span> <span class="pre"><</span> <span class="pre">b</span> <span class="pre">?</span> <span class="pre">distance(a,b)</span> | |
786 | <span class="pre">:</span> <span class="pre">-distance(b,a)</span></tt></td> | |
787 | <td>pre: there exists a | |
788 | value <tt class="docutils literal"><span class="pre">n</span></tt> of | |
789 | <tt class="docutils literal"><span class="pre">Distance</span></tt> such that | |
790 | <tt class="docutils literal"><span class="pre">a</span> <span class="pre">+</span> <span class="pre">n</span> <span class="pre">==</span> <span class="pre">b</span></tt>. <tt class="docutils literal"><span class="pre">b</span> | |
791 | <span class="pre">==</span> <span class="pre">a</span> <span class="pre">+</span> <span class="pre">(b</span> <span class="pre">-</span> <span class="pre">a)</span></tt>.</td> | |
792 | </tr> | |
793 | <tr><td><tt class="docutils literal"><span class="pre">a[n]</span></tt></td> | |
794 | <td>convertible to T</td> | |
795 | <td><tt class="docutils literal"><span class="pre">*(a</span> <span class="pre">+</span> <span class="pre">n)</span></tt></td> | |
796 | <td>pre: a is a <a class="reference internal" href="#readable-iterator">Readable | |
797 | Iterator</a></td> | |
798 | </tr> | |
799 | <tr><td><tt class="docutils literal"><span class="pre">a[n]</span> <span class="pre">=</span> <span class="pre">v</span></tt></td> | |
800 | <td>convertible to T</td> | |
801 | <td><tt class="docutils literal"><span class="pre">*(a</span> <span class="pre">+</span> <span class="pre">n)</span> <span class="pre">=</span> <span class="pre">v</span></tt></td> | |
802 | <td>pre: a is a <a class="reference internal" href="#writable-iterator">Writable | |
803 | Iterator</a></td> | |
804 | </tr> | |
805 | <tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre"><</span> <span class="pre">b</span></tt></td> | |
806 | <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> | |
807 | <td><tt class="docutils literal"><span class="pre">b</span> <span class="pre">-</span> <span class="pre">a</span> <span class="pre">></span> <span class="pre">0</span></tt></td> | |
808 | <td><tt class="docutils literal"><span class="pre"><</span></tt> is a total | |
809 | ordering relation</td> | |
810 | </tr> | |
811 | <tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">></span> <span class="pre">b</span></tt></td> | |
812 | <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> | |
813 | <td><tt class="docutils literal"><span class="pre">b</span> <span class="pre"><</span> <span class="pre">a</span></tt></td> | |
814 | <td><tt class="docutils literal"><span class="pre">></span></tt> is a total | |
815 | ordering relation</td> | |
816 | </tr> | |
817 | <tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre">>=</span> <span class="pre">b</span></tt></td> | |
818 | <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> | |
819 | <td><tt class="docutils literal"><span class="pre">!(a</span> <span class="pre"><</span> <span class="pre">b)</span></tt></td> | |
820 | <td> </td> | |
821 | </tr> | |
822 | <tr><td><tt class="docutils literal"><span class="pre">a</span> <span class="pre"><=</span> <span class="pre">b</span></tt></td> | |
823 | <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> | |
824 | <td><tt class="docutils literal"><span class="pre">!(a</span> <span class="pre">></span> <span class="pre">b)</span></tt></td> | |
825 | <td> </td> | |
826 | </tr> | |
827 | <tr><td><tt class="docutils literal"><span class="pre">iterator_traversal<X>::type</span></tt></td> | |
828 | <td>Convertible to | |
829 | <tt class="docutils literal"><span class="pre">random_access_traversal_tag</span></tt></td> | |
830 | <td> </td> | |
831 | <td> </td> | |
832 | </tr> | |
833 | </tbody> | |
834 | </table> | |
835 | <!-- TR1: random_access_traversal_iterator_tag changed to | |
836 | random_access_traversal_tag for consistency --> | |
837 | </div> | |
838 | <div class="section" id="interoperable-iterators-lib-interoperable-iterators"> | |
839 | <h4><a class="toc-backref" href="#id21">Interoperable Iterators [lib.interoperable.iterators]</a></h4> | |
840 | <p>A class or built-in type <tt class="docutils literal"><span class="pre">X</span></tt> that models Single Pass Iterator is | |
841 | <em>interoperable with</em> a class or built-in type <tt class="docutils literal"><span class="pre">Y</span></tt> that also models | |
842 | Single Pass Iterator if the following expressions are valid and | |
843 | respect the stated semantics. In the tables below, <tt class="docutils literal"><span class="pre">x</span></tt> is an object | |
844 | of type <tt class="docutils literal"><span class="pre">X</span></tt>, <tt class="docutils literal"><span class="pre">y</span></tt> is an object of type <tt class="docutils literal"><span class="pre">Y</span></tt>, <tt class="docutils literal"><span class="pre">Distance</span></tt> is | |
845 | <tt class="docutils literal"><span class="pre">iterator_traits<Y>::difference_type</span></tt>, and <tt class="docutils literal"><span class="pre">n</span></tt> represents a | |
846 | constant object of type <tt class="docutils literal"><span class="pre">Distance</span></tt>.</p> | |
847 | <table border="1" class="docutils"> | |
848 | <colgroup> | |
849 | <col width="13%" /> | |
850 | <col width="27%" /> | |
851 | <col width="60%" /> | |
852 | </colgroup> | |
853 | <thead valign="bottom"> | |
854 | <tr><th class="head">Expression</th> | |
855 | <th class="head">Return Type</th> | |
856 | <th class="head">Assertion/Precondition/Postcondition</th> | |
857 | </tr> | |
858 | </thead> | |
859 | <tbody valign="top"> | |
860 | <tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">=</span> <span class="pre">x</span></tt></td> | |
861 | <td><tt class="docutils literal"><span class="pre">Y</span></tt></td> | |
862 | <td>post: <tt class="docutils literal"><span class="pre">y</span> <span class="pre">==</span> <span class="pre">x</span></tt></td> | |
863 | </tr> | |
864 | <tr><td><tt class="docutils literal"><span class="pre">Y(x)</span></tt></td> | |
865 | <td><tt class="docutils literal"><span class="pre">Y</span></tt></td> | |
866 | <td>post: <tt class="docutils literal"><span class="pre">Y(x)</span> <span class="pre">==</span> <span class="pre">x</span></tt></td> | |
867 | </tr> | |
868 | <tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre">==</span> <span class="pre">y</span></tt></td> | |
869 | <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> | |
870 | <td><tt class="docutils literal"><span class="pre">==</span></tt> is an equivalence relation over its domain.</td> | |
871 | </tr> | |
872 | <tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">==</span> <span class="pre">x</span></tt></td> | |
873 | <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> | |
874 | <td><tt class="docutils literal"><span class="pre">==</span></tt> is an equivalence relation over its domain.</td> | |
875 | </tr> | |
876 | <tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre">!=</span> <span class="pre">y</span></tt></td> | |
877 | <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> | |
878 | <td><tt class="docutils literal"><span class="pre">bool(a==b)</span> <span class="pre">!=</span> <span class="pre">bool(a!=b)</span></tt> over its domain.</td> | |
879 | </tr> | |
880 | <tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">!=</span> <span class="pre">x</span></tt></td> | |
881 | <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> | |
882 | <td><tt class="docutils literal"><span class="pre">bool(a==b)</span> <span class="pre">!=</span> <span class="pre">bool(a!=b)</span></tt> over its domain.</td> | |
883 | </tr> | |
884 | </tbody> | |
885 | </table> | |
886 | <p>If <tt class="docutils literal"><span class="pre">X</span></tt> and <tt class="docutils literal"><span class="pre">Y</span></tt> both model Random Access Traversal Iterator then | |
887 | the following additional requirements must be met.</p> | |
888 | <table border="1" class="docutils"> | |
889 | <colgroup> | |
890 | <col width="12%" /> | |
891 | <col width="25%" /> | |
892 | <col width="23%" /> | |
893 | <col width="41%" /> | |
894 | </colgroup> | |
895 | <thead valign="bottom"> | |
896 | <tr><th class="head">Expression</th> | |
897 | <th class="head">Return Type</th> | |
898 | <th class="head">Operational Semantics</th> | |
899 | <th class="head">Assertion/ Precondition</th> | |
900 | </tr> | |
901 | </thead> | |
902 | <tbody valign="top"> | |
903 | <tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre"><</span> <span class="pre">y</span></tt></td> | |
904 | <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> | |
905 | <td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">-</span> <span class="pre">x</span> <span class="pre">></span> <span class="pre">0</span></tt></td> | |
906 | <td><tt class="docutils literal"><span class="pre"><</span></tt> is a total ordering relation</td> | |
907 | </tr> | |
908 | <tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre"><</span> <span class="pre">x</span></tt></td> | |
909 | <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> | |
910 | <td><tt class="docutils literal"><span class="pre">x</span> <span class="pre">-</span> <span class="pre">y</span> <span class="pre">></span> <span class="pre">0</span></tt></td> | |
911 | <td><tt class="docutils literal"><span class="pre"><</span></tt> is a total ordering relation</td> | |
912 | </tr> | |
913 | <tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre">></span> <span class="pre">y</span></tt></td> | |
914 | <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> | |
915 | <td><tt class="docutils literal"><span class="pre">y</span> <span class="pre"><</span> <span class="pre">x</span></tt></td> | |
916 | <td><tt class="docutils literal"><span class="pre">></span></tt> is a total ordering relation</td> | |
917 | </tr> | |
918 | <tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">></span> <span class="pre">x</span></tt></td> | |
919 | <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> | |
920 | <td><tt class="docutils literal"><span class="pre">x</span> <span class="pre"><</span> <span class="pre">y</span></tt></td> | |
921 | <td><tt class="docutils literal"><span class="pre">></span></tt> is a total ordering relation</td> | |
922 | </tr> | |
923 | <tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre">>=</span> <span class="pre">y</span></tt></td> | |
924 | <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> | |
925 | <td><tt class="docutils literal"><span class="pre">!(x</span> <span class="pre"><</span> <span class="pre">y)</span></tt></td> | |
926 | <td> </td> | |
927 | </tr> | |
928 | <tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">>=</span> <span class="pre">x</span></tt></td> | |
929 | <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> | |
930 | <td><tt class="docutils literal"><span class="pre">!(y</span> <span class="pre"><</span> <span class="pre">x)</span></tt></td> | |
931 | <td> </td> | |
932 | </tr> | |
933 | <tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre"><=</span> <span class="pre">y</span></tt></td> | |
934 | <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> | |
935 | <td><tt class="docutils literal"><span class="pre">!(x</span> <span class="pre">></span> <span class="pre">y)</span></tt></td> | |
936 | <td> </td> | |
937 | </tr> | |
938 | <tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre"><=</span> <span class="pre">x</span></tt></td> | |
939 | <td>convertible to <tt class="docutils literal"><span class="pre">bool</span></tt></td> | |
940 | <td><tt class="docutils literal"><span class="pre">!(y</span> <span class="pre">></span> <span class="pre">x)</span></tt></td> | |
941 | <td> </td> | |
942 | </tr> | |
943 | <tr><td><tt class="docutils literal"><span class="pre">y</span> <span class="pre">-</span> <span class="pre">x</span></tt></td> | |
944 | <td><tt class="docutils literal"><span class="pre">Distance</span></tt></td> | |
945 | <td><tt class="docutils literal"><span class="pre">distance(Y(x),y)</span></tt></td> | |
946 | <td>pre: there exists a value <tt class="docutils literal"><span class="pre">n</span></tt> of | |
947 | <tt class="docutils literal"><span class="pre">Distance</span></tt> such that <tt class="docutils literal"><span class="pre">x</span> <span class="pre">+</span> <span class="pre">n</span> <span class="pre">==</span> <span class="pre">y</span></tt>. | |
948 | <tt class="docutils literal"><span class="pre">y</span> <span class="pre">==</span> <span class="pre">x</span> <span class="pre">+</span> <span class="pre">(y</span> <span class="pre">-</span> <span class="pre">x)</span></tt>.</td> | |
949 | </tr> | |
950 | <tr><td><tt class="docutils literal"><span class="pre">x</span> <span class="pre">-</span> <span class="pre">y</span></tt></td> | |
951 | <td><tt class="docutils literal"><span class="pre">Distance</span></tt></td> | |
952 | <td><tt class="docutils literal"><span class="pre">distance(y,Y(x))</span></tt></td> | |
953 | <td>pre: there exists a value <tt class="docutils literal"><span class="pre">n</span></tt> of | |
954 | <tt class="docutils literal"><span class="pre">Distance</span></tt> such that <tt class="docutils literal"><span class="pre">y</span> <span class="pre">+</span> <span class="pre">n</span> <span class="pre">==</span> <span class="pre">x</span></tt>. | |
955 | <tt class="docutils literal"><span class="pre">x</span> <span class="pre">==</span> <span class="pre">y</span> <span class="pre">+</span> <span class="pre">(x</span> <span class="pre">-</span> <span class="pre">y)</span></tt>.</td> | |
956 | </tr> | |
957 | </tbody> | |
958 | </table> | |
959 | </div> | |
960 | </div> | |
961 | </div> | |
962 | <div class="section" id="addition-to-lib-iterator-synopsis"> | |
963 | <h2><a class="toc-backref" href="#id22">Addition to [lib.iterator.synopsis]</a></h2> | |
964 | <pre class="literal-block"> | |
965 | // lib.iterator.traits, traits and tags | |
966 | template <class Iterator> struct is_readable_iterator; | |
967 | template <class Iterator> struct iterator_traversal; | |
968 | ||
969 | struct incrementable_traversal_tag { }; | |
970 | struct single_pass_traversal_tag : incrementable_traversal_tag { }; | |
971 | struct forward_traversal_tag : single_pass_traversal_tag { }; | |
972 | struct bidirectional_traversal_tag : forward_traversal_tag { }; | |
973 | struct random_access_traversal_tag : bidirectional_traversal_tag { }; | |
974 | </pre> | |
975 | </div> | |
976 | <div class="section" id="addition-to-lib-iterator-traits"> | |
977 | <h2><a class="toc-backref" href="#id23">Addition to [lib.iterator.traits]</a></h2> | |
978 | <p>The <tt class="docutils literal"><span class="pre">is_readable_iterator</span></tt> class | |
979 | template satisfies the <a class="reference external" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1519.htm">UnaryTypeTrait</a> requirements.</p> | |
980 | <p>Given an iterator type <tt class="docutils literal"><span class="pre">X</span></tt>, <tt class="docutils literal"><span class="pre">is_readable_iterator<X>::value</span></tt> | |
981 | yields <tt class="docutils literal"><span class="pre">true</span></tt> if, for an object <tt class="docutils literal"><span class="pre">a</span></tt> of type <tt class="docutils literal"><span class="pre">X</span></tt>, <tt class="docutils literal"><span class="pre">*a</span></tt> is | |
982 | convertible to <tt class="docutils literal"><span class="pre">iterator_traits<X>::value_type</span></tt>, and <tt class="docutils literal"><span class="pre">false</span></tt> | |
983 | otherwise.</p> | |
984 | <p><tt class="docutils literal"><span class="pre">iterator_traversal<X>::type</span></tt> is</p> | |
985 | <pre class="literal-block"> | |
986 | <em>category-to-traversal</em>(iterator_traits<X>::iterator_category) | |
987 | </pre> | |
988 | <p>where <em>category-to-traversal</em> is defined as follows</p> | |
989 | <pre class="literal-block" id="category-to-traversal"> | |
990 | <em>category-to-traversal</em>(C) = | |
991 | if (C is convertible to incrementable_traversal_tag) | |
992 | return C; | |
993 | else if (C is convertible to random_access_iterator_tag) | |
994 | return random_access_traversal_tag; | |
995 | else if (C is convertible to bidirectional_iterator_tag) | |
996 | return bidirectional_traversal_tag; | |
997 | else if (C is convertible to forward_iterator_tag) | |
998 | return forward_traversal_tag; | |
999 | else if (C is convertible to input_iterator_tag) | |
1000 | return single_pass_traversal_tag; | |
1001 | else if (C is convertible to output_iterator_tag) | |
1002 | return incrementable_traversal_tag; | |
1003 | else | |
1004 | <em>the program is ill-formed</em> | |
1005 | </pre> | |
1006 | </div> | |
1007 | </div> | |
1008 | <div class="section" id="footnotes"> | |
1009 | <h1><a class="toc-backref" href="#id24">Footnotes</a></h1> | |
1010 | <p>The UnaryTypeTrait concept is defined in <a class="reference external" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1519.htm">n1519</a>; the LWG is | |
1011 | considering adding the requirement that specializations are derived | |
1012 | from their nested <tt class="docutils literal"><span class="pre">::type</span></tt>.</p> | |
1013 | <!-- LocalWords: Abrahams Siek Witt const bool Sutter's WG int UL LI href Lvalue | |
1014 | LocalWords: ReadableIterator WritableIterator SwappableIterator cv pre iter | |
1015 | LocalWords: ConstantLvalueIterator MutableLvalueIterator CopyConstructible TR | |
1016 | LocalWords: ForwardTraversalIterator BidirectionalTraversalIterator lvalue | |
1017 | LocalWords: RandomAccessTraversalIterator dereferenceable Incrementable tmp | |
1018 | LocalWords: incrementable xxx min prev inplace png oldeqnew AccessTag struct | |
1019 | LocalWords: TraversalTag typename lvalues DWA Hmm JGS mis enum --> | |
1020 | </div> | |
1021 | </div> | |
1022 | <div class="footer"> | |
1023 | <hr class="footer" /> | |
1024 | <a class="reference external" href="new-iter-concepts.rst">View document source</a>. | |
1025 | Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source. | |
1026 | ||
1027 | </div> | |
1028 | </body> | |
1029 | </html> |