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
|
<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>
<li>
<a href="#concept_checking">Concept Checking</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 half-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
<i>much</i> 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 their
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/refmanual/metafunction.html">metafunctions</a> and all
functions as free-standing functions to allow for a layer of indirection. </p>
<!--<p><i>Notice that these metafunctions must be defined in namespace </i>
<code>boost</code></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>boost::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">Iterator type</TD>
<TD VAlign="top"><code>boost::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>boost::range_iterator<const 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>boost::begin(a)</code></TD>
<TD VAlign="top"><code>boost::range_iterator<X>::type</code> if
<code>a</code> is mutable, <code>boost::range_iterator<const X>::type</code>
otherwise</TD> </TR>
<TR>
<TD VAlign="top">End of range</TD>
<TD VAlign="top"><code>boost::end(a)</code></TD>
<TD VAlign="top"><code>boost::range_iterator<X>::type</code> if
<code>a</code> is mutable, <code>boost::range_iterator<const X>::type</code>
otherwise</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>boost::begin(a)</code></TD>
<TD VAlign="top">Returns an iterator pointing to the first element in the Range.</TD>
<TD VAlign="top"><code>boost::begin(a)</code> is either dereferenceable or past-the-end.
It is past-the-end if and only if <code>boost::distance(a) == 0</code>.</TD>
</TR>
<TR>
<TD VAlign="top"><code>boost::end(a)</code></TD>
<TD VAlign="top">Returns an iterator pointing one past the last element in the
Range.</TD>
<TD VAlign="top"><code>boost::end(a)</code> is past-the-end.</TD>
</TR>
</table>
<h3>Complexity guarantees</h3>
<code>boost::end(a)</code> is at most amortized linear time, <code>boost::begin(a)</code> is
amortized constant time. For most practical
purposes, one can expect both 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>[boost::begin(a),boost::end(a))</code> is
a valid range, that is, <code>boost::end(a)</code> is reachable from <code>boost::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>[boost::begin(a),boost::end(a))</code>
will pass through every element of <code>a</code>.</TD>
</tr>
</table>
<h3>See also</h3>
<p><a
href="boost_range.html#minimal_interface">Extending the library for UDTs </a></p>
<p> <a href="boost_range.html#boost::rang_difference">Implementation of
metafunctions </a></p>
<p> <a href="boost_range.html#begin">Implementation of
functions </a></p>
<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>boost::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>
</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>boost::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>
</p>
<hr>
<a name=random_access_range><h2>Random Access Range</h2> <h3>Description</h3>
<p>
A range <code>X</code> where <code>boost::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>
<a name=concept_checking><h2>Concept Checking</h2>
Each of the range concepts has a corresponding concept checking
class in the file <code><boost/range/concepts.hpp></codE>. These classes may be
used in conjunction with the <a
href="../../concept_check/concept_check.htm">Boost Concept
Check</a> library to insure that the type of a template parameter
is compatible with a range concept. If not, a meaningful compile
time error is generated. Checks are provided for the range
concepts related to iterator traversal categories. For example,
the following line checks that the type <code>T</code> models the
<a href="#forward_range">ForwardRange</a> concept.
<pre>
function_requires<ForwardRangeConcept<T> >();
</pre>
An additional concept check is required for the value access
property of the range based on the range's iterator type. For
example to check for a ForwardReadableRange, the following code is
required.
<pre>
function_requires<ForwardRangeConcept<T> >();
function_requires<
ReadableIteratorConcept<
typename range_iterator<T>::type
>
>();
</pre>
The following range concept checking classes are provided.
<ul>
<li>
Class <code>SinglePassRangeConcept</code> checks for <a
href="#single_pass_range">Single Pass Range</a>
<li>
Class <code>ForwardRangeConcept</code> checks for <a
href="#forward_range">Forward Range</a>
<li>
Class <code>BidirectionalRangeConcept</code> checks for <a
href="#bidirectional_range">Bidirectional Range</a>
<li>
Class <code>RandomAccessRangeConcept</code> checks for <a
href="#random_access_range">Random Access Range</a>
</ul>
<h3>See also</h3>
<p> <a href="style.html">Range Terminology and style guidelines</a></p>
<p> <a href="../../iterator/doc/iterator_concepts.html">Iterator Concepts</a></p>
<p> <a href="../../concept_check/concept_check.htm">Boost Concept Check library</a></p>
<hr>
<p>
© <a name="Copyright" id="Copyright">Copyright</a> Thorsten Ottosen 2008.
</p>
<p>
Distributed under the Boost Software License, Version 1.0. (See
accompanying file LICENSE_1_0.txt or copy
at <a href=
"http://www.boost.org/LICENSE_1_0.txt">www.boost.org/LICENSE_1_0.txt</a>)
</p>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
</BODY>
</HTML>
|
