Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

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
RevLine 
[29]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
80category</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
87functions 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&lt;X>::type</code> is a model of <a
112href="../../iterator/doc/new-iter-concepts.html#single-pass-iterators-lib-single-pass-iterators">
113Single 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&lt;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&lt;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&lt;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&lt;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&lt;X>::type</code> if
164<code>a</code> is mutable, <code>boost::range_const_iterator&lt;X>::type</code>
165otherwise</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&lt;X>::type</code> if
170<code>a</code> is mutable, <code>boost::range_const_iterator&lt;X>::type</code>
171otherwise</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">&nbsp;-&nbsp;</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&lt;X>::type</code> is a model
257of <a 
258href="../../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
262Range</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&lt;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&lt;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&lt;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
308of 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) &gt;= 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&lt;X>::type</code> iterator must meet all of the requirements
353of <a
354href="../../iterator/doc/new-iter-concepts.html#bidirectional-traversal-iterator
355s-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&lt;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 
373VAlign="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&lt;X>::type</code> if
393<code>a</code> is mutable, <code>boost::range_const_reverse_iterator&lt;X>::type</code>
394otherwise.</TD>
395            <TD VAlign="top">Equivalent to
396<code>boost::range_reverse_iterator&lt;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&lt;X>::type</code> if
401<code>a</code> is mutable, <code>boost::range_const_reverse_iterator&lt;X>::type</code>
402otherwise.</TD>
403            <TD VAlign="top">Equivalent to
404<code>boost::range_reverse_iterator&lt;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&lt;X>::type</code> is a model
442of <a
443     
444href="../../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&lt;ForwardRangeConcept&lt;T&gt; &gt;();
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&lt;ForwardRangeConcept&lt;T&gt; &gt;();
479    function_requires&lt;
480        ReadableIteratorConcept&lt;
481            typename range_iterator&lt;T&gt;::type
482        &gt;
483    &gt;();
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.