Planet

navi

home

PPS

about

screenshots

download

development

forum

Context Navigation

source: downloads/boost_1_34_1/libs/range/doc/range.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 17 years ago
updated boost from 1_33_1 to 1_34_1
File size: 19.3 KB

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats: