Boost.Range |
A Range is a concept similar to the STL 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
much fewer requirements than a Container.
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
The operations that can be performed on a Range is dependent on the traversal category of the underlying iterator type. Therefore the range concepts are named to reflect which traversal category their iterators support. See also terminology and style guidelines. for more information about naming of ranges.
The concepts described below specifies associated types as metafunctions and all functions as free-standing functions to allow for a layer of indirection.
X |
A type that is a model of Single Pass Range. |
a |
Object of type X . |
A range X where boost::range_iterator<X>::type
is a model of
Single Pass Iterator
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. |
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. |
Name | Expression | Return type |
---|---|---|
Beginning of range | boost::begin(a) |
boost::range_iterator<X>::type if
a is mutable, boost::range_iterator<const X>::type
otherwise |
End of range | boost::end(a) |
boost::range_iterator<X>::type if
a is mutable, boost::range_iterator<const X>::type
otherwise |
Expression | Semantics | Postcondition |
---|---|---|
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 . |
boost::end(a) |
Returns an iterator pointing one past the last element in the Range. | boost::end(a) is past-the-end. |
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.
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. |
Completeness | An algorithm that iterates through the range [boost::begin(a),boost::end(a))
will pass through every element of a . |
Extending the library for UDTs
Implementation of metafunctions
X |
A type that is a model of Forward Range. |
a |
Object of type X . |
A range X
where boost::range_iterator<X>::type
is a model
of Forward Traversal Iterator
X |
A type that is a model of Bidirectional Range. |
a |
Object of type X . |
boost::range_iterator<X>::type
iterator must meet all of the requirements
of Bidirectional Traversal Iterator.
A range X
where boost::range_iterator<X>::type
is a model
of Random Access Traversal Iterator
. These classes may be
used in conjunction with the Boost Concept
Check 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 T
models the
ForwardRange concept.
function_requires<ForwardRangeConcept<T> >();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.
function_requires<ForwardRangeConcept<T> >(); function_requires< ReadableIteratorConcept< typename range_iterator<T>::type > >();The following range concept checking classes are provided.
SinglePassRangeConcept
checks for Single Pass Range
ForwardRangeConcept
checks for Forward Range
BidirectionalRangeConcept
checks for Bidirectional Range
RandomAccessRangeConcept
checks for Random Access Range
Range Terminology and style guidelines
© Copyright Thorsten Ottosen 2008.
Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at www.boost.org/LICENSE_1_0.txt)