1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
|
<HTML>
<!--
-- Copyright (c) Jeremy Siek 2000
--
-- Permission to use, copy, modify, distribute and sell this software
-- and its documentation for any purpose is hereby granted without fee,
-- provided that the above copyright notice appears in all copies and
-- that both that copyright notice and this permission notice appear
-- in supporting documentation. Silicon Graphics makes no
-- representations about the suitability of this software for any
-- purpose. It is provided "as is" without express or implied warranty.
-->
<Head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<Title>Range Concepts</Title>
<link rel="stylesheet" href="style.css" type="text/css">
</HEAD>
<table border="0" >
<tr>
<td ><img src="../../../boost.png" border="0" ></td>
<td ><h1 align="center">Boost.Range </h1></td>
</tr>
</table>
<h2>Range concepts </h2>
<ul>
<li>
<a href="#overview">Overview</a>
<li>
<a href="#single_pass_range">Single Pass Range</a>
<li>
<a href="#forward_range">Forward Range</a>
<li>
<a href="#bidirectional_range">Bidirectional Range</a>
<li>
<a href="#random_access_range">Random Access Range</a>
</ul>
<a name="overview"></a>
<hr>
<h3>Overview</h3>
<p>
A Range is a <i>concept</i> similar to the STL <a
href="http://www.sgi.com/Technology/STL/Container.html">Container</a> concept. A
Range provides iterators for accessing a closed-open range
<code>[first,one_past_last)</code> of elements and provides
information about the number of elements in the Range. However, a Range has
fewer requirements than a Container.
</p>
<p>
The motivation for the Range concept is
that there are many useful Container-like types that do not meet the full
requirements of Container, and many algorithms that can be written with this
reduced set of requirements. In particular, a Range does not necessarily
<ul>
<li>
own the elements that can be accessed through it,
<li>
have copy semantics,
<!--
<li>
require that the associated reference type is a real C++ reference.
-->
</ul>
Because of the second requirement, a Range object must be passed by
(const or non-const) reference in generic code.
</p>
<p>
The operations that can be performed on a Range is dependent on the
<a href="../../iterator/doc/new-iter-concepts.html#iterator-traversal-concepts-lib-iterator-traversal">traversal
category</a> of the underlying iterator type. Therefore
the range concepts are named to reflect which traversal category its
iterators support. See also <a href="style.html">terminology and style guidelines.</a>
for more information about naming of ranges.</p>
<p> The concepts described below specifies associated types as
<a href="../../mpl/doc/index.html#metafunctions">metafunctions</a> and all
functions as free-standing functions to allow for a layer of indirection. </p>
<hr>
<a name="single_pass_range">
<H2>Single Pass Range</H2>
<h3>Notation</h3>
<Table>
<TR>
<TD VAlign="top"><code>X</code></TD>
<TD VAlign="top">A type that is a model of Single Pass Range.</TD>
</TR>
<TR>
<TD VAlign="top"><code>a</code></TD>
<TD VAlign="top">Object of type <code>X</code>.</TD>
</TR>
</table>
<h3>Description</h3>
<p>
A range X where <code>range_iterator<X>::type</code> is a model of <a
href="../../iterator/doc/new-iter-concepts.html#single-pass-iterators-lib-single-pass-iterators">
Single Pass Iterator</a>
</p>
<h3>Associated types</h3>
<table border="1" cellpadding="5">
<TR>
<TD VAlign="top">Value type</TD>
<TD VAlign="top"><code>range_value<X>::type</code></TD>
<TD VAlign="top">The type of the object stored in a Range.
</TR>
<TR>
<TD VAlign="top">Iterator type</TD>
<TD VAlign="top"><code>range_iterator<X>::type</code></TD>
<TD VAlign="top">The type of iterator used to iterate through a Range's elements.
The iterator's value type is expected to be the Range's value type. A
conversion from the iterator type to the const iterator type must exist.
</TR>
<TR>
<TD VAlign="top">Const iterator type</TD>
<TD VAlign="top"><code>range_const_iterator<X>::type</code></TD>
<TD VAlign="top">A type of iterator that may be used to examine, but not to
modify, a Range's elements.</TD>
</TR>
<!--
<TR>
<TD VAlign="top">Reference type</TD>
<TD VAlign="top"><code>reference_of<X>::type</code></TD>
<TD VAlign="top">A type that behaves like a reference to the Range's value type. <a href="#1">[1]</a></TD>
</TR>
-->
</table>
<h3>Valid expressions</h3>
The following expressions must be valid.
<p>
<Table border="1" cellpadding="5">
<TR>
<TH>Name</TH>
<TH>Expression</TH>
<TH>Return type</TH>
</TR>
<TR>
<TD VAlign="top">Beginning of range</TD>
<TD VAlign="top"><code>begin(a)</code></TD>
<TD VAlign="top"><code>range_iterator<X>::type</code> if
<code>a</code> is mutable, <code>range_const_iterator<X>::type</code>
otherwise</TD> </TR>
<TR>
<TD VAlign="top">End of range</TD>
<TD VAlign="top"><code>end(a)</code></TD>
<TD VAlign="top"><code>range_iterator<X>::type</code> if
<code>a</code> is mutable, <code>range_const_iterator<X>::type</code>
otherwise</TD>
</TR>
<tr>
<TD VAlign="top">Is range empty?</TD>
<TD VAlign="top"><code>empty(a)</code></TD>
<TD VAlign="top">Convertible to <code>bool</code></TD>
</TR>
</table>
<h3>Expression semantics</h3>
<Table border>
<TR>
<TH>Expression</TH>
<TH>Semantics</TH>
<TH>Postcondition</TH>
</TR>
<TR>
<TD VAlign="top"><code>begin(a)</code></TD>
<TD VAlign="top">Returns an iterator pointing to the first element in the Range.</TD>
<TD VAlign="top"><code>begin(a)</code> is either dereferenceable or past-the-end.
It is past-the-end if and only if <code>size(a) == 0</code>.</TD>
</TR>
<TR>
<TD VAlign="top"><code>end(a)</code></TD>
<TD VAlign="top">Returns an iterator pointing one past the last element in the
Range.</TD>
<TD VAlign="top"><code>end(a)</code> is past-the-end.</TD>
</TR>
<TR>
<TD VAlign="top"><code>empty(a)</code></TD>
<TD VAlign="top">Equivalent to <code>begin(a) == end(a)</code>. (But possibly
faster.)</TD>
<TD VAlign="top"> - </TD>
</TR>
</table>
<h3>Complexity guarantees</h3>
All three functions are at most amortized linear time. For most practical
purposes, one can expect <code>begin(a)</code>, <code>end(a)</code> and <code>empty(a)</code>
to be amortized constant time.
<h3>Invariants</h3>
<Table border>
<TR>
<TD VAlign="top">Valid range</TD>
<TD VAlign="top">For any Range <code>a</code>, <code>[begin(a),end(a))</code> is
a valid range, that is, <code>end(a)</code> is reachable from <code>begin(a)</code>
in a finite number of increments.</TD>
</TR>
<TR>
<TD VAlign="top">Completeness</TD>
<TD VAlign="top">An algorithm that iterates through the range <code>[begin(a),end(a))</code>
will pass through every element of <code>a</code>.</TD>
</tr>
</table>
<h3>See also</h3>
<p>
<A href="http://www.sgi.com/Technology/STL/Container.html">Container</A>
</p>
<hr>
<a name=forward_range><h2>Forward Range</h2>
<h3>Notation</h3>
<Table>
<TR>
<TD VAlign="top"><code>X</code></TD>
<TD VAlign="top">A type that is a model of Forward Range.</TD>
</TR>
<TR>
<TD VAlign="top"><code>a</code></TD>
<TD VAlign="top">Object of type <code>X</code>.</TD>
</TR>
</table>
<h3>Description</h3>
<p>
A range <code>X</code> where <code>range_iterator<X>::type</code> is a model
of <a
href="../../iterator/doc/new-iter-concepts.html#forward-traversal-iterators-lib-forward-traversal-iterators">Forward Traversal Iterator</a>
</p>
<h3>Refinement of</h3> <a href="#single_pass_range">Single Pass
Range</a>
<h3>Associated types</h3>
<table cellpadding="5" border="1">
<TR>
<TD VAlign="top">Distance type</TD>
<TD VAlign="top"><code>range_difference<X>::type</code></TD>
<TD VAlign="top">A signed integral type used to represent the distance between
two of the Range's iterators. This type must be the same as the iterator's
distance type.</TD>
</TR>
<TR>
<TD VAlign="top">Size type</TD>
<TD VAlign="top"><code>range_size<X>::type</code></TD>
<TD VAlign="top">An unsigned integral type that can represent any nonnegative
value of the Range's distance type.</TD>
</tr>
</table>
<h3>Valid expressions</h3>
<table border="1" cellpadding="5">
<tr>
<th>Name</th>
<th>Expression</th>
<th>Return type</th>
</tr>
<TR>
<TD VAlign="top">Size of range</TD>
<TD VAlign="top"><code>size(a)</code></TD>
<TD VAlign="top"><code>range_size<X>::type</code></TD>
</TR>
</table>
<h3>Expression semantics </h3>
<table border="1" cellpadding="5">
<TR>
<TH>Expression</TH>
<TH>Semantics</TH>
<TH>Postcondition</TH>
</TR>
<tr>
<TD VAlign="top"><code>size(a)</code></TD>
<TD VAlign="top">Returns the size of the Range, that is, its number
of elements. Note <code>size(a) == 0u</code> is equivalent to
<code>empty(a).</code></TD>
<TD VAlign="top"><code>size(a) >= 0</TD>
</TR>
</table>
<h3>Complexity guarantees</h3>
<p><code>size(a)</code> is at most amortized linear time.</p>
<h3>Invariants</h3>
<p>
<Table border="1" cellpadding="5">
<TR>
<TD VAlign="top">Range size</TD>
<TD VAlign="top"><code>size(a)</code> is equal to the distance from <code>begin(a)</code>
to <code>end(a)</code>.</TD> </table>
</p>
<hr>
<a name=bidirectional_range><h2>Bidirectional Range</h2>
<h3>Notation</h3>
<Table>
<TR>
<TD VAlign="top"><code>X</code></TD>
<TD VAlign="top">A type that is a model of Bidirectional Range.</TD>
</TR>
<TR>
<TD VAlign="top"><code>a</code></TD>
<TD VAlign="top">Object of type <code>X</code>.</TD>
</TR>
</table>
<h3>Description</h3> This concept provides access to iterators that traverse in
both directions (forward and reverse). The
<code>range_iterator<X>::type</code> iterator must meet all of the requirements
of <a
href="../../iterator/doc/new-iter-concepts.html#bidirectional-traversal-iterator
s-lib-bidirectional-traversal-iterators">Bidirectional Traversal Iterator.</a>
<h3>Refinement of</h3> <a href="#forward_range">Forward Range</a>
<h3>Associated types</h3>
<Table border>
<TR>
<TD VAlign="top">Reverse Iterator type</TD>
<TD VAlign="top"><code>range_reverse_iterator<X>::type</code></TD>
<TD VAlign="top">The type of iterator used to iterate through a Range's elements
in reverse order. The iterator's value type is expected to be the Range's value
type. A conversion from the reverse iterator type to the const reverse iterator
type must exist. </TD>
</TR>
<TR>
<TD VAlign="top">Const reverse iterator type</TD>
<TD
VAlign="top"><code>range_const_reverse_iterator<X>::type</code></TD>
<TD VAlign="top">A type of reverse iterator that may be used to examine, but not
to modify, a Range's elements.</TD>
</TR>
</table>
<h3>Valid expressions</h3>
<Table border>
<TR>
<TH>Name</TH>
<TH>Expression</TH>
<TH>Return type</TH>
<TH>Semantics</TH>
</TR>
<TR>
<TD VAlign="top">Beginning of range</TD>
<TD VAlign="top"><code>rbegin(a)</code></TD>
<TD VAlign="top"><code>range_reverse_iterator<X>::type</code> if
<code>a</code> is mutable, <code>range_const_reverse_iterator<X>::type</code>
otherwise.</TD>
<TD VAlign="top">Equivalent to
<code>range_reverse_iterator<X>::type(end(a))</code>.</TD> </TR>
<TR>
<TD VAlign="top">End of range</TD>
<TD VAlign="top"><code>rend(a)</code></TD>
<TD VAlign="top"><code>range_reverse_iterator<X>::type</code> if
<code>a</code> is mutable, <code>range_const_reverse_iterator<X>::type</code>
otherwise.</TD>
<TD VAlign="top">Equivalent to
<code>range_reverse_iterator<X>::type(begin(a))</code>.</TD> </tr>
</table>
<h3>Complexity guarantees</h3>
<code>rbegin(a)</code> has the same complexity as <code>end(a)</code> and <code>rend(a)</code>
has the same complexity as <code>begin(a)</code> from <a
href="#forward_range">Forward Range</a>.
<h3>Invariants</h3>
<p>
<Table border="1" cellpadding="5">
<TR>
<TD VAlign="top">Valid reverse range</TD>
<TD VAlign="top">For any Bidirectional Range <code>a</code>, <code>[rbegin(a),rend(a))</code>
is a valid range, that is, <code>rend(a)</code> is reachable from <code>rbegin(a)</code>
in a finite number of increments.</TD>
</TR>
<TR>
<TD VAlign="top">Completeness</TD>
<TD VAlign="top">An algorithm that iterates through the range <code>[rbegin(a),rend(a))</code>
will pass through every element of <code>a</code>.</TD>
</tr>
</table>
</p>
<hr>
<a name=random_access_range><h2>Random Access Range</h2> <h3>Description</h3>
<p>
A range <code>X</code> where <code>range_iterator<X>::type</code> is a model
of <a
href="../../iterator/doc/new-iter-concepts.html#random-access-traversal-iterators
-lib-random-access-traversal-iterators">Random Access Traversal Iterator</a>
</p>
<h3>Refinement of</h3>
<p>
<a href="#bidirectional_range">Bidirectional Range</a>
</p>
<hr>
<!--
<h3>Notes</h3>
<P>
<A name="1">[1]</A>
The reference type does not have to be a real C++ reference. The requirements of
the reference type is that it <i>behaves</i> like a real reference. Hence the
reference type must be convertible to the value_type and assignment through
<br>
<br>
<HR>
<br>
-->
<TABLE>
<TR valign="top">
<TD nowrap>Copyright © 2000</TD>
<TD><A HREF=http://www.boost.org/people/jeremy_siek.htm>Jeremy Siek</A>
</TR>
<tr >
<TD nowrap>Copyright © 2004</TD>
<TD>Thorsten Ottosen.
</TABLE>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
</BODY>
</HTML>
|
