1[/ 2 Copyright 2010 Neil Groves 3 Distributed under the Boost Software License, Version 1.0. 4 (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 5/] 6[section:concepts Range Concepts] 7 8[section Overview] 9 10A Range is a [*/concept/] similar to the STL [@http://www.sgi.com/tech/stl/Container.html Container] concept. A Range provides iterators for accessing a half-open range `[first,one_past_last)` of elements and provides information about the number of elements in the Range. However, a Range has fewer requirements than a Container. 11 12The 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 13 14* own the elements that can be accessed through it, 15* have copy semantics, 16 17Because of the second requirement, a Range object must be passed by (const or non-const) reference in generic code. 18 19The operations that can be performed on a Range is dependent on the [@boost:/libs/iterator/doc/new-iter-concepts.html#iterator-traversal-concepts-lib-iterator-traversal traversal category] of the underlying iterator type. Therefore the range concepts are named to reflect which traversal category its iterators support. See also terminology and style guidelines. for more information about naming of ranges. 20 21The concepts described below specifies associated types as [@boost:/libs/mpl/doc/refmanual/metafunction.html metafunctions] and all functions as free-standing functions to allow for a layer of indirection. 22 23[endsect] 24 25 26[section Single Pass Range] 27 28[heading Notation] 29 30[table 31 [] 32 [[`X`] [A type that is a model of __single_pass_range__.]] 33 [[`a`] [Object of type X.]] 34] 35 36[heading Description] 37 38A range `X` where `boost::range_iterator<X>::type` is a model of __single_pass_iterator__. 39 40[heading Associated types] 41 42[table 43 [] 44 [[Iterator type ] [`boost::range_iterator<X>::type` ] [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.]] 45 [[Const iterator type] [`boost::range_iterator<const X>::type`] [A type of iterator that may be used to examine, but not to modify, a Range's elements.]] 46] 47 48[heading Valid expressions] 49 50The following expressions must be valid. 51 52[table 53 [[Name ] [Expression ] [Return type ]] 54 [[Beginning of range] [`boost::begin(a)`] [`boost::range_iterator<X>::type` if `a` is mutable, `boost::range_iterator<const X>::type` otherwise]] 55 [[End of range ] [`boost::end(a)` ] [`boost::range_iterator<X>::type` if `a` is mutable, `boost::range_iterator<const X>::type` otherwise]] 56] 57 58[heading Expression semantics] 59 60[table 61 [[Expression ] [Semantics ] [Postcondition]] 62 [[`boost::begin(a)`] [Returns an iterator pointing to the first element in the Range. ] [`boost::begin(a)` is either dereferenceable or past-the-end. It is past-the-end if and only if `boost::distance(a) == 0`.]] 63 [[`boost::end(a)` ] [Returns an iterator pointing one past the last element in the Range. ] [`boost::end(a)` is past-the-end.]] 64] 65 66[heading Complexity guarantees] 67 68`boost::end(a)` is at most amortized linear time, `boost::begin(a)` is amortized constant time. For most practical purposes, one can expect both to be amortized constant time. 69 70[heading Invariants] 71 72[table 73 [] 74 [[Valid range ] [For any Range `a`, `[boost::begin(a),boost::end(a))` is a valid range, that is, `boost::end(a)` is reachable from `boost::begin(a)` in a finite number of increments.]] 75 76 [[Completeness] [An algorithm that iterates through the range `[boost::begin(a),boost::end(a))` will pass through every element of `a`.]] 77] 78 79[heading See also] 80 81__extending_for_udts__ 82 83__implementation_of_metafunctions__ 84 85__implementation_of_functions__ 86 87__container__ 88 89[endsect] 90 91 92[section Forward Range] 93 94[heading Notation] 95 96[table 97 [] 98 [[`X`] [A type that is a model of __forward_range__.]] 99 [[`a`] [Object of type X.]] 100] 101 102[heading Description] 103 104A range `X` where `boost::range_iterator<X>::type` is a model of __forward_traversal_iterator__. 105 106[heading Refinement of] 107 108__single_pass_range__ 109 110[heading Associated types] 111 112[table 113 [] 114 [[Distance type] [`boost::range_difference<X>::type`] [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.]] 115 [[Size type ] [`boost::range_size<X>::type` ] [An unsigned integral type that can represent any nonnegative value of the Range's distance type.]] 116] 117 118[heading See also] 119 120__implementation_of_metafunctions__ 121 122__implementation_of_functions__ 123 124[endsect] 125 126 127[section Bidirectional Range] 128 129[heading Notation] 130 131[table 132 [] 133 [[`X`] [A type that is a model of __bidirectional_range__.]] 134 [[`a`] [Object of type X.]] 135] 136 137[heading Description] 138 139This concept provides access to iterators that traverse in both directions (forward and reverse). The `boost::range_iterator<X>::type` iterator must meet all of the requirements of __bidirectional_traversal_iterator__. 140 141[heading Refinement of] 142 143__forward_range__ 144 145[heading Associated types] 146 147[table 148 [] 149 [[Reverse Iterator type ] [`boost::range_reverse_iterator<X>::type` ] [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.]] 150 151 [[Const reverse iterator type] [`boost::range_reverse_iterator<const X>::type`] [A type of reverse iterator that may be used to examine, but not to modify, a Range's elements.]] 152] 153 154[heading Valid expressions] 155 156[table 157 [[Name ] [Expression ] [Return type] [Semantics]] 158 [[Beginning of range] [`boost::rbegin(a)`] [`boost::range_reverse_iterator<X>::type` if `a` is mutable `boost::range_reverse_iterator<const X>::type` otherwise.] [Equivalent to `boost::range_reverse_iterator<X>::type(boost::end(a))`.]] 159 160 [[End of range ] [`boost::rend(a)` ] [`boost::range_reverse_iterator<X>::type` if `a` is mutable, `boost::range_reverse_iterator<const X>::type` otherwise.] [Equivalent to `boost::range_reverse_iterator<X>::type(boost::begin(a))`.]] 161] 162 163[heading Complexity guarantees] 164 165`boost::rbegin(a)` has the same complexity as `boost::end(a)` and `boost::rend(a)` has the same complexity as `boost::begin(a)` from __forward_range__. 166 167[heading Invariants] 168 169[table 170 [] 171 [[Valid reverse range] [For any Bidirectional Range a, `[boost::rbegin(a),boost::rend(a))` is a valid range, that is, `boost::rend(a)` is reachable from `boost::rbegin(a)` in a finite number of increments.]] 172 173 [[Completeness ] [An algorithm that iterates through the range `[boost::rbegin(a),boost::rend(a))` will pass through every element of `a`.]] 174] 175 176[heading See also] 177 178__implementation_of_metafunctions__ 179 180__implementation_of_functions__ 181 182[endsect] 183 184 185[section Random Access Range] 186 187[heading Description] 188 189A range `X` where `boost::range_iterator<X>::type` is a model of __random_access_traversal_iterator__. 190 191[heading Refinement of] 192 193__bidirectional_range__ 194 195[heading Valid expressions] 196 197[table 198 [[Name ] [Expression ] [Return type ]] 199 [[Size of range] [`boost::size(a)`] [`boost::range_size<X>::type`]] 200] 201 202[heading Expression semantics] 203 204[table 205 [[Expression ] [Semantics] [Postcondition]] 206 [[`boost::size(a)`] [Returns the size of the Range, that is, its number of elements. Note `boost::size(a) == 0u` is equivalent to `boost::empty(a)`.] [`boost::size(a) >= 0`]] 207] 208 209[heading Complexity guarantees] 210 211`boost::size(a)` completes in amortized constant time. 212 213[heading Invariants] 214 215[table 216 [] 217 [[Range size] [`boost::size(a)` is equal to the `boost::end(a)` - `boost::begin(a)`.]] 218] 219 220[endsect] 221 222 223[section Concept Checking] 224 225Each of the range concepts has a corresponding concept checking class in the file [@boost:/boost/range/concepts.hpp `<boost/range/concepts.hpp>`]. These classes may be used in conjunction with the __concept_check__ to ensure 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 `T` models the __forward_range__ concept. 226 227`` 228BOOST_CONCEPT_ASSERT(( ForwardRangeConcept<T> )); 229`` 230 231An 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. 232 233`` 234BOOST_CONCEPT_ASSERT(( ForwardRangeConcept<T> )); 235BOOST_CONCEPT_ASSERT(( ReadableIteratorConcept<typename range_iterator<T>::type> )); 236`` 237 238The following range concept checking classes are provided. 239 240* Class SinglePassRangeConcept checks for __single_pass_range__ 241* Class ForwardRangeConcept checks for __forward_range__ 242* Class BidirectionalRangeConcept checks for __bidirectional_range__ 243* Class RandomAccessRangeConcept checks for __random_access_range__ 244 245[heading See also] 246 247[link range.style_guide Range Terminology and style guidelines] 248 249__iterator_concepts__ 250 251__concept_check__ 252 253[endsect] 254[endsect] 255 256