Boost_1_39_0/libs/range/doc/range.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
   2 <HTML>
   3 <!--
   4   -- Copyright (c) Jeremy Siek 2000
   5   --
   6   -- Permission to use, copy, modify, distribute and sell this software
   7   -- and its documentation for any purpose is hereby granted without fee,
   8   -- provided that the above copyright notice appears in all copies and
   9   -- that both that copyright notice and this permission notice appear
  10   -- in supporting documentation.  Silicon Graphics makes no
  11   -- representations about the suitability of this software for any
  12   -- purpose.  It is provided "as is" without express or implied warranty.
  13   -->
  14 <Head>
  15     <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
  16     <Title>Range Concepts</Title>
  17     <link rel="stylesheet" href="style.css" type="text/css">
  18 </HEAD>
  19
  20     <table border="0" >
  21         <tr>
  22             <td ><img src="../../../boost.png" border="0" ></td>
  23             <td ><h1 align="center">Boost.Range </h1></td>
  24         </tr>
  25     </table>
  26
  27     <h2>Range concepts </h2>
  28
  29     <ul>
  30         <li>
  31             <a href="#overview">Overview</a>
  32         <li>
  33             <a href="#single_pass_range">Single Pass Range</a>
  34         <li>
  35             <a href="#forward_range">Forward Range</a>
  36         <li>
  37             <a href="#bidirectional_range">Bidirectional Range</a>
  38         <li>
  39             <a href="#random_access_range">Random Access Range</a>
  40         <li>
  41             <a href="#concept_checking">Concept Checking</a>
  42     </ul>
  43
  44     <a name="overview"></a>
  45     <hr>
  46     <h3>Overview</h3>
  47
  48     <p>
  49     A Range is a <i>concept</i> similar to the STL <a
  50                href="http://www.sgi.com/Technology/STL/Container.html">Container</a> concept. A
  51                Range provides iterators for accessing a half-open range
  52 <code>[first,one_past_last)</code> of elements and provides
  53                information about the number of elements in the Range.  However, a Range has
  54                <i>much</i> fewer requirements than a Container.
  55               </p>
  56               <p>
  57                The motivation for the Range concept is
  58                that there are many useful Container-like types that do not meet the full
  59                requirements of Container, and many algorithms that can be written with this
  60                reduced set of requirements. In particular, a Range does not necessarily
  61
  62     <ul>
  63         <li>
  64             own the elements that can be accessed through it,
  65         <li>
  66             have copy semantics,
  67             <!--
  68         <li>
  69             require that the associated reference type is a real C++ reference.
  70             -->
  71     </ul>
  72
  73
  74     Because of the second requirement, a Range object must be passed by
  75    (const or non-const) reference in generic code.
  76
  77     </p>
  78     <p>
  79     The operations that can be performed on a Range is dependent on the
  80     <a href="../../iterator/doc/new-iter-concepts.html#iterator-traversal-concepts-lib-iterator-traversal">traversal
  81 category</a> of the underlying iterator type. Therefore
  82     the range concepts are named to reflect which traversal category their
  83     iterators support. See also <a href="style.html">terminology and style
  84     guidelines.</a> for more information about naming of ranges.</p>
  85
  86     <p> The concepts described below specifies associated types as
  87 <a href="../../mpl/doc/refmanual/metafunction.html">metafunctions</a> and all
  88 functions as free-standing functions to allow for a layer of indirection. </p>
  89
  90 <!--<p><i>Notice that these metafunctions must be defined in namespace </i>
  91 <code>boost</code></p>-->
  92
  93     <hr>
  94     <a name="single_pass_range"></a>
  95     <H2>Single Pass Range</H2>
  96
  97     <h3>Notation</h3>
  98     <Table>
  99         <TR>
 100             <TD VAlign="top"><code>X</code></TD>
 101             <TD VAlign="top">A type that is a model of Single Pass Range.</TD>
 102         </TR>
 103         <TR>
 104             <TD VAlign="top"><code>a</code></TD>
 105             <TD VAlign="top">Object of type <code>X</code>.</TD>
 106         </TR>
 107     </table>
 108
 109
 110     <h3>Description</h3>
 111     <p>
 112     A range X where <code>boost::range_iterator&lt;X>::type</code> is a model of <a
 113 href="../../iterator/doc/new-iter-concepts.html#single-pass-iterators-lib-single-pass-iterators">
 114 Single Pass Iterator</a>
 115
 116     </p>
 117
 118
 119     <h3>Associated types</h3>
 120
 121     <table border="1" cellpadding="5">
 122
 123         <TR>
 124             <TD VAlign="top">Iterator type</TD>
 125             <TD VAlign="top"><code>boost::range_iterator&lt;X>::type</code></TD>
 126             <TD VAlign="top">The type of iterator used to iterate through a Range's elements.
 127             The iterator's value type is expected to be the Range's value type.  A
 128             conversion from the iterator type to the const iterator type must exist.
 129         </TR>
 130         <TR>
 131             <TD VAlign="top">Const iterator type</TD>
 132             <TD VAlign="top"><code>boost::range_iterator&lt;const X>::type</code></TD>
 133             <TD VAlign="top">A type of iterator that may be used to examine, but not to
 134             modify, a Range's elements.</TD>
 135         </TR>
 136         <!--
 137         <TR>
 138             <TD VAlign="top">Reference type</TD>
 139             <TD VAlign="top"><code>reference_of&lt;X>::type</code></TD>
 140             <TD VAlign="top">A type that behaves like a reference to the Range's value type. <a href="#1">[1]</a></TD>
 141         </TR>
 142             -->
 143     </table>
 144
 145
 146     <h3>Valid expressions</h3>
 147
 148     The following expressions must be valid.
 149     <p>
 150
 151     <Table border="1" cellpadding="5">
 152         <TR>
 153             <TH>Name</TH>
 154             <TH>Expression</TH>
 155             <TH>Return type</TH>
 156         </TR>
 157         <TR>
 158             <TD VAlign="top">Beginning of range</TD>
 159             <TD VAlign="top"><code>boost::begin(a)</code></TD>
 160             <TD VAlign="top"><code>boost::range_iterator&lt;X>::type</code> if
 161 <code>a</code> is mutable, <code>boost::range_iterator&lt;const X>::type</code>
 162 otherwise</TD> </TR>
 163         <TR>
 164             <TD VAlign="top">End of range</TD>
 165             <TD VAlign="top"><code>boost::end(a)</code></TD>
 166             <TD VAlign="top"><code>boost::range_iterator&lt;X>::type</code> if
 167 <code>a</code> is mutable, <code>boost::range_iterator&lt;const X>::type</code>
 168 otherwise</TD>
 169         </TR>
 170
 171     </table>
 172     <h3>Expression semantics</h3>
 173
 174     <Table border>
 175         <TR>
 176             <TH>Expression</TH>
 177             <TH>Semantics</TH>
 178             <TH>Postcondition</TH>
 179         </TR>
 180         <TR>
 181             <TD VAlign="top"><code>boost::begin(a)</code></TD>
 182             <TD VAlign="top">Returns an iterator pointing to the first element in the Range.</TD>
 183             <TD VAlign="top"><code>boost::begin(a)</code> is either dereferenceable or past-the-end.
 184             It is past-the-end if and only if <code>boost::distance(a) == 0</code>.</TD>
 185         </TR>
 186         <TR>
 187             <TD VAlign="top"><code>boost::end(a)</code></TD>
 188             <TD VAlign="top">Returns an iterator pointing one past the last element in the
 189             Range.</TD>
 190             <TD VAlign="top"><code>boost::end(a)</code> is past-the-end.</TD>
 191         </TR>
 192
 193     </table>
 194
 195     <h3>Complexity guarantees</h3>
 196
 197     <code>boost::end(a)</code> is at most amortized linear time, <code>boost::begin(a)</code> is
 198                                          amortized constant time. For most practical
 199         purposes, one can expect both to be amortized constant time.
 200
 201     <h3>Invariants</h3>
 202     <Table border>
 203         <TR>
 204             <TD VAlign="top">Valid range</TD>
 205             <TD VAlign="top">For any Range <code>a</code>, <code>[boost::begin(a),boost::end(a))</code> is
 206             a valid range, that is, <code>boost::end(a)</code> is reachable from <code>boost::begin(a)</code>
 207             in a finite number of increments.</TD>
 208         </TR>
 209         <TR>
 210             <TD VAlign="top">Completeness</TD>
 211             <TD VAlign="top">An algorithm that iterates through the range <code>[boost::begin(a),boost::end(a))</code>
 212             will pass through every element of <code>a</code>.</TD>
 213         </tr>
 214     </table>
 215
 216
 217     <h3>See also</h3>
 218                                                                      <p><a
 219                                                                      href="boost_range.html#minimal_interface">Extending the library for UDTs </a></p>
 220             <p> <a href="boost_range.html#boost::rang_difference">Implementation of
 221                    metafunctions </a></p>
 222
 223             <p> <a href="boost_range.html#begin">Implementation of
 224                    functions </a></p>
 225                         <p>
 226             <A href="http://www.sgi.com/Technology/STL/Container.html">Container</A>
 227             </p>
 228
 229
 230     <hr>
 231     <a name=forward_range></a><h2>Forward Range</h2>
 232
 233     <h3>Notation</h3>
 234     <Table>
 235         <TR>
 236             <TD VAlign="top"><code>X</code></TD>
 237             <TD VAlign="top">A type that is a model of Forward Range.</TD>
 238         </TR>
 239         <TR>
 240             <TD VAlign="top"><code>a</code></TD>
 241             <TD VAlign="top">Object of type <code>X</code>.</TD>
 242         </TR>
 243     </table>
 244
 245     <h3>Description</h3>
 246     <p>
 247     A range <code>X</code> where <code>boost::range_iterator&lt;X>::type</code> is a model
 248 of <a
 249 href="../../iterator/doc/new-iter-concepts.html#forward-traversal-iterators-lib-forward-traversal-iterators">Forward Traversal Iterator</a>
 250     </p>
 251
 252     <h3>Refinement of</h3> <a href="#single_pass_range">Single Pass
 253 Range</a>
 254
 255   </p>
 256
 257     <hr>
 258
 259     <a name="bidirectional_range"></a><h2>Bidirectional Range</h2>
 260
 261     <h3>Notation</h3>
 262     <Table>
 263         <TR>
 264             <TD VAlign="top"><code>X</code></TD>
 265             <TD VAlign="top">A type that is a model of Bidirectional Range.</TD>
 266         </TR>
 267         <TR>
 268             <TD VAlign="top"><code>a</code></TD>
 269             <TD VAlign="top">Object of type <code>X</code>.</TD>
 270         </TR>
 271     </table>
 272
 273     <h3>Description</h3> This concept provides access to iterators that traverse in
 274     both directions (forward and reverse). The
 275 <code>boost::range_iterator&lt;X>::type</code> iterator must meet all of the requirements
 276 of <a
 277 href="../../iterator/doc/new-iter-concepts.html#bidirectional-traversal-iterator
 278 s-lib-bidirectional-traversal-iterators">Bidirectional Traversal Iterator.</a>
 279
 280     <h3>Refinement of</h3> <a href="#forward_range">Forward Range</a>
 281
 282
 283 </p>
 284
 285     <hr>
 286
 287     <a name=random_access_range></a><h2>Random Access Range</h2>
 288     <h3>Description</h3>
 289     <p>
 290     A range <code>X</code> where <code>boost::range_iterator&lt;X>::type</code> is a model
 291 of <a
 292
 293 href="../../iterator/doc/new-iter-concepts.html#random-access-traversal-iterators
 294 -lib-random-access-traversal-iterators">Random Access Traversal Iterator</a>
 295     </p>
 296
 297     <h3>Refinement of</h3>
 298     <p>
 299     <a href="#bidirectional_range">Bidirectional Range</a>
 300     </p>
 301
 302     <hr>
 303
 304     <a name=concept_checking></a><h2>Concept Checking</h2>
 305
 306     Each of the range concepts has a corresponding concept checking
 307     class in the file <code>&lt;boost/range/concepts.hpp&gt;</code>. These classes may be
 308     used in conjunction with the <a
 309     href="../../concept_check/concept_check.htm">Boost Concept
 310     Check</a> library to insure that the type of a template parameter
 311     is compatible with a range concept. If not, a meaningful compile
 312     time error is generated. Checks are provided for the range
 313     concepts related to iterator traversal categories. For example,
 314     the following line checks that the type <code>T</code> models the
 315     <a href="#forward_range">ForwardRange</a> concept.
 316
 317     <pre>
 318     function_requires&lt;ForwardRangeConcept&lt;T&gt; &gt;();
 319     </pre>
 320
 321     An additional concept check is required for the value access
 322     property of the range based on the range's iterator type. For
 323     example to check for a ForwardReadableRange, the following code is
 324     required.
 325
 326     <pre>
 327     function_requires&lt;ForwardRangeConcept&lt;T&gt; &gt;();
 328     function_requires&lt;
 329         ReadableIteratorConcept&lt;
 330             typename range_iterator&lt;T&gt;::type
 331         &gt;
 332     &gt;();
 333     </pre>
 334
 335     The following range concept checking classes are provided.
 336     <ul>
 337         <li>
 338             Class <code>SinglePassRangeConcept</code> checks for <a
 339             href="#single_pass_range">Single Pass Range</a>
 340         <li>
 341             Class <code>ForwardRangeConcept</code> checks for <a
 342             href="#forward_range">Forward Range</a>
 343         <li>
 344             Class <code>BidirectionalRangeConcept</code> checks for <a
 345             href="#bidirectional_range">Bidirectional Range</a>
 346         <li>
 347             Class <code>RandomAccessRangeConcept</code> checks for <a
 348             href="#random_access_range">Random Access Range</a>
 349     </ul>
 350
 351     <h3>See also</h3>
 352     <p> <a href="style.html">Range Terminology and style guidelines</a></p>
 353     <p> <a href="../../iterator/doc/iterator_concepts.html">Iterator Concepts</a></p>
 354     <p> <a href="../../concept_check/concept_check.htm">Boost Concept Check library</a></p>
 355
 356     <hr>
 357     <p>
 358       &copy; <a name="Copyright" id="Copyright">Copyright</a> Thorsten Ottosen 2008.
 359     </p>
 360
 361     <p>
 362       Distributed under the Boost Software License, Version 1.0. (See
 363       accompanying file LICENSE_1_0.txt or copy
 364       at <a href=
 365       "http://www.boost.org/LICENSE_1_0.txt">www.boost.org/LICENSE_1_0.txt</a>)
 366     </p>
 367     <br>
 368     <br>
 369     <br>
 370     <br>
 371     <br>
 372     <br>
 373     <br>
 374     <br>
 375     <br>
 376     <br>
 377
 378     </BODY>
 379 </HTML>