]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <?xml version="1.0"?> |
2 | <concept name="RandomAccessIterator" category="Iterator"><!-- | |
3 | Based on concepts from the SGI Standard Template Library documentation: | |
4 | Copyright (c) 1996-1999 | |
5 | Silicon Graphics Computer Systems, Inc. | |
6 | ||
7 | Copyright (c) 1994 | |
8 | Hewlett-Packard Company | |
9 | --><!-- | |
10 | Copyright 2000-2001 University of Notre Dame du Lac. | |
11 | Copyright 2001-2002 Indiana University. | |
12 | Some concepts based on versions from the MTL draft manual and Boost Graph | |
13 | and Property Map documentation: | |
14 | Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000 | |
15 | --> | |
16 | <param name="Iter" role="iterator-type"/> | |
17 | ||
18 | <use-header name="iterator"/> | |
19 | ||
20 | <models-sentence>The iterator type <arg num="1"/> must be a model of <self/>.</models-sentence> | |
21 | ||
22 | <description> | |
23 | <para>A random access iterator is an iterator that can read through | |
24 | a sequence of values. It can move in either direction through the | |
25 | sequence (by any amount in constant time), and can be either mutable | |
26 | (data pointed to by it can be changed) or not mutable.</para> | |
27 | ||
28 | <para>An iterator represents a position in a sequence. Therefore, | |
29 | the iterator can point into the sequence (returning a value when | |
30 | dereferenced and being incrementable), or be off-the-end (and not | |
31 | dereferenceable or incrementable).</para> | |
32 | </description> | |
33 | ||
34 | <associated-type name="value_type"> | |
35 | <get-member-type name="value_type"> | |
36 | <apply-template name="std::iterator_traits"> | |
37 | <type name="Iter"/> | |
38 | </apply-template> | |
39 | </get-member-type> | |
40 | <description><simpara>The value type of the iterator</simpara></description> | |
41 | </associated-type> | |
42 | ||
43 | <refines const="no" concept="BidirectionalIterator"/> | |
44 | <refines const="no" concept="LessThanComparable"/> | |
45 | ||
46 | <notation variables="i j"> | |
47 | <sample-value> | |
48 | <type name="Iter"/> | |
49 | </sample-value> | |
50 | </notation> | |
51 | ||
52 | <associated-type name="category"> | |
53 | <get-member-type name="iterator_category"> | |
54 | <apply-template name="std::iterator_traits"> | |
55 | <type name="Iter"/> | |
56 | </apply-template> | |
57 | </get-member-type> | |
58 | <description><simpara>The category of the iterator</simpara></description> | |
59 | </associated-type> | |
60 | ||
61 | <associated-type name="difference_type"> | |
62 | <get-member-type name="difference_type"> | |
63 | <apply-template name="std::iterator_traits"> | |
64 | <type name="Iter"/> | |
65 | </apply-template> | |
66 | </get-member-type> | |
67 | <description><simpara>The difference type of the iterator (measure of the number | |
68 | of steps between two iterators)</simpara></description> | |
69 | </associated-type> | |
70 | ||
71 | <notation variables="x"> | |
72 | <sample-value> | |
73 | <type name="value_type"/> | |
74 | </sample-value> | |
75 | </notation> | |
76 | ||
77 | <notation variables="n"> | |
78 | <sample-value> | |
79 | <type name="difference_type"/> | |
80 | </sample-value> | |
81 | </notation> | |
82 | ||
83 | <notation variables="int_off"> | |
84 | <sample-value> | |
85 | <type name="int"/> | |
86 | </sample-value> | |
87 | </notation> | |
88 | ||
89 | <valid-type-expression name="Category tag"> | |
90 | <description/> | |
91 | <type name="category"/> | |
92 | <return-type> | |
93 | <derived-from testable="yes"> | |
94 | <type name="std::random_access_iterator_tag"/> | |
95 | </derived-from> | |
96 | </return-type> | |
97 | </valid-type-expression> | |
98 | ||
99 | <valid-expression name="Motion"> | |
100 | <add-assign> | |
101 | <sample-value><reference-to><type name="Iter"/></reference-to></sample-value> | |
102 | <sample-value><type name="difference_type"/></sample-value> | |
103 | </add-assign> | |
104 | <return-type> | |
105 | <require-same-type testable="yes"> | |
106 | <reference-to><type name="Iter"/></reference-to> | |
107 | </require-same-type> | |
108 | </return-type> | |
109 | <semantics>Equivalent to applying <code>i++</code> <code>n</code> times | |
110 | if <code>n</code> is positive, applying <code>i--</code> | |
111 | <code>-n</code> times if <code>n</code> is negative, and to a null | |
112 | operation if <code>n</code> is zero.</semantics> | |
113 | </valid-expression> | |
114 | ||
115 | <valid-expression name="Motion (with integer offset)"> | |
116 | <add-assign> | |
117 | <sample-value><reference-to><type name="Iter"/></reference-to></sample-value> | |
118 | <sample-value><type name="int"/></sample-value> | |
119 | </add-assign> | |
120 | <return-type> | |
121 | <require-same-type testable="yes"> | |
122 | <reference-to><type name="Iter"/></reference-to> | |
123 | </require-same-type> | |
124 | </return-type> | |
125 | <semantics>Equivalent to applying <code>i++</code> <code>n</code> times | |
126 | if <code>n</code> is positive, applying <code>i--</code> | |
127 | <code>-n</code> times if <code>n</code> is negative, and to a null | |
128 | operation if <code>n</code> is zero.</semantics> | |
129 | </valid-expression> | |
130 | ||
131 | <valid-expression name="Subtractive motion"> | |
132 | <subtract-assign> | |
133 | <sample-value><reference-to><type name="Iter"/></reference-to></sample-value> | |
134 | <sample-value><type name="difference_type"/></sample-value> | |
135 | </subtract-assign> | |
136 | <return-type> | |
137 | <require-same-type testable="yes"> | |
138 | <reference-to><type name="Iter"/></reference-to> | |
139 | </require-same-type> | |
140 | </return-type> | |
141 | <semantics>Equivalent to <code>i+=(-n)</code></semantics> | |
142 | </valid-expression> | |
143 | ||
144 | <valid-expression name="Subtractive motion (with integer offset)"> | |
145 | <subtract-assign> | |
146 | <sample-value><reference-to><type name="Iter"/></reference-to></sample-value> | |
147 | <sample-value><type name="int"/></sample-value> | |
148 | </subtract-assign> | |
149 | <return-type> | |
150 | <require-same-type testable="yes"> | |
151 | <reference-to><type name="Iter"/></reference-to> | |
152 | </require-same-type> | |
153 | </return-type> | |
154 | <semantics>Equivalent to <code>i+=(-n)</code></semantics> | |
155 | </valid-expression> | |
156 | ||
157 | <valid-expression name="Addition"> | |
158 | <add> | |
159 | <sample-value><type name="Iter"/></sample-value> | |
160 | <sample-value><type name="difference_type"/></sample-value> | |
161 | </add> | |
162 | <return-type> | |
163 | <require-same-type testable="yes"><type name="Iter"/></require-same-type> | |
164 | </return-type> | |
165 | <semantics>Equivalent to <code>{Iter j = i; j += n; return j;}</code></semantics> | |
166 | </valid-expression> | |
167 | ||
168 | <valid-expression name="Addition with integer"> | |
169 | <add> | |
170 | <sample-value><type name="Iter"/></sample-value> | |
171 | <sample-value><type name="int"/></sample-value> | |
172 | </add> | |
173 | <return-type> | |
174 | <require-same-type testable="yes"><type name="Iter"/></require-same-type> | |
175 | </return-type> | |
176 | <semantics>Equivalent to <code>{Iter j = i; j += n; return j;}</code></semantics> | |
177 | </valid-expression> | |
178 | ||
179 | <valid-expression name="Addition (count first)"> | |
180 | <add> | |
181 | <sample-value><type name="difference_type"/></sample-value> | |
182 | <sample-value><type name="Iter"/></sample-value> | |
183 | </add> | |
184 | <return-type> | |
185 | <require-same-type testable="yes"><type name="Iter"/></require-same-type> | |
186 | </return-type> | |
187 | <semantics>Equivalent to <code>i + n</code></semantics> | |
188 | </valid-expression> | |
189 | ||
190 | <valid-expression name="Addition with integer (count first)"> | |
191 | <add> | |
192 | <sample-value><type name="int"/></sample-value> | |
193 | <sample-value><type name="Iter"/></sample-value> | |
194 | </add> | |
195 | <return-type> | |
196 | <require-same-type testable="yes"><type name="Iter"/></require-same-type> | |
197 | </return-type> | |
198 | <semantics>Equivalent to <code>i + n</code></semantics> | |
199 | </valid-expression> | |
200 | ||
201 | <valid-expression name="Subtraction"> | |
202 | <subtract> | |
203 | <sample-value><type name="Iter"/></sample-value> | |
204 | <sample-value><type name="difference_type"/></sample-value> | |
205 | </subtract> | |
206 | <return-type> | |
207 | <require-same-type testable="yes"><type name="Iter"/></require-same-type> | |
208 | </return-type> | |
209 | <semantics>Equivalent to <code>i + (-n)</code></semantics> | |
210 | </valid-expression> | |
211 | ||
212 | <valid-expression name="Subtraction with integer"> | |
213 | <subtract> | |
214 | <sample-value><type name="Iter"/></sample-value> | |
215 | <sample-value><type name="int"/></sample-value> | |
216 | </subtract> | |
217 | <return-type> | |
218 | <require-same-type testable="yes"><type name="Iter"/></require-same-type> | |
219 | </return-type> | |
220 | <semantics>Equivalent to <code>i + (-n)</code></semantics> | |
221 | </valid-expression> | |
222 | ||
223 | <valid-expression name="Distance"> | |
224 | <subtract> | |
225 | <sample-value><type name="Iter"/></sample-value> | |
226 | <sample-value><type name="Iter"/></sample-value> | |
227 | </subtract> | |
228 | <return-type> | |
229 | <require-same-type testable="yes"><type name="difference_type"/></require-same-type> | |
230 | </return-type> | |
231 | <semantics>The number of times <code>i</code> must be incremented (or | |
232 | decremented if the result is negative) to reach <code>j</code>. Not | |
233 | defined if <code>j</code> is not reachable from | |
234 | <code>i</code>.</semantics> | |
235 | </valid-expression> | |
236 | ||
237 | <valid-expression name="Element access"> | |
238 | <subscript> | |
239 | <sample-value><type name="Iter"/></sample-value> | |
240 | <sample-value><type name="difference_type"/></sample-value> | |
241 | </subscript> | |
242 | <return-type> | |
243 | <require-same-type testable="yes"> | |
244 | <const-if-not-mutable> | |
245 | <reference-to> | |
246 | <type name="value_type"/> | |
247 | </reference-to> | |
248 | </const-if-not-mutable> | |
249 | </require-same-type> | |
250 | </return-type> | |
251 | <semantics>Equivalent to <code>*(i + n)</code></semantics> | |
252 | </valid-expression> | |
253 | ||
254 | <valid-expression name="Element access with integer index"> | |
255 | <subscript> | |
256 | <sample-value><type name="Iter"/></sample-value> | |
257 | <sample-value><type name="int"/></sample-value> | |
258 | </subscript> | |
259 | <return-type> | |
260 | <require-same-type testable="yes"> | |
261 | <const-if-not-mutable> | |
262 | <reference-to> | |
263 | <type name="value_type"/> | |
264 | </reference-to> | |
265 | </const-if-not-mutable> | |
266 | </require-same-type> | |
267 | </return-type> | |
268 | <semantics>Equivalent to <code>*(i + n)</code></semantics> | |
269 | </valid-expression> | |
270 | ||
271 | <complexity> | |
272 | All iterator operations must take amortized constant time. | |
273 | </complexity> | |
274 | ||
275 | <example-model> | |
276 | <pointer-to> | |
277 | <type name="T"/> | |
278 | </pointer-to> | |
279 | </example-model> | |
280 | ||
281 | <example-model> | |
282 | <get-member-type name="iterator"> | |
283 | <apply-template name="std::vector"> | |
284 | <type name="T"/> | |
285 | </apply-template> | |
286 | </get-member-type> | |
287 | </example-model> | |
288 | ||
289 | <example-model> | |
290 | <get-member-type name="const_iterator"> | |
291 | <apply-template name="std::vector"> | |
292 | <type name="T"/> | |
293 | </apply-template> | |
294 | </get-member-type> | |
295 | </example-model> | |
296 | ||
297 | <example-model> | |
298 | <get-member-type name="iterator"> | |
299 | <apply-template name="std::deque"> | |
300 | <type name="T"/> | |
301 | </apply-template> | |
302 | </get-member-type> | |
303 | </example-model> | |
304 | ||
305 | <example-model> | |
306 | <get-member-type name="const_iterator"> | |
307 | <apply-template name="std::deque"> | |
308 | <type name="T"/> | |
309 | </apply-template> | |
310 | </get-member-type> | |
311 | </example-model> | |
312 | ||
313 | </concept> |