![](../../../boost.png) |
Boost.Range |
Range concepts
Overview
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
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
-
own the elements that can be accessed through it,
-
have copy semantics,
Because of the second requirement, a Range object must be passed by
(const or non-const) reference in generic code.
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 its
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.
Single Pass Range
Notation
X |
A type that is a model of Single Pass Range. |
a |
Object of type X . |
Description
A range X where boost::range_iterator<X>::type
is a model of
Single Pass Iterator
Associated types
Value type |
boost::range_value<X>::type |
The type of the object stored in a Range.
|
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_const_iterator<X>::type |
A type of iterator that may be used to examine, but not to
modify, a Range's elements. |
Valid expressions
The following expressions must be valid.
Name |
Expression |
Return type |
Beginning of range |
boost::begin(a) |
boost::range_iterator<X>::type if
a is mutable, boost::range_const_iterator<X>::type
otherwise |
End of range |
boost::end(a) |
boost::range_iterator<X>::type if
a is mutable, boost::range_const_iterator<X>::type
otherwise |
Is range empty? |
boost::empty(a) |
Convertible to bool |
Expression semantics
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::size(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::empty(a) |
Equivalent to boost::begin(a) == boost::end(a) . (But possibly
faster.) |
- |
Complexity guarantees
All three functions are at most amortized linear time. For most practical
purposes, one can expect boost::begin(a)
, boost::end(a)
and boost::empty(a)
to be amortized constant time.
Invariants
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 . |
See also
Container
implementation of
metafunctions
implementation of
functions
Forward Range
Notation
X |
A type that is a model of Forward Range. |
a |
Object of type X . |
Description
A range X
where boost::range_iterator<X>::type
is a model
of Forward Traversal Iterator
Refinement of
Single Pass
Range
Associated types
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. |
Size type |
boost::range_size<X>::type |
An unsigned integral type that can represent any nonnegative
value of the Range's distance type. |
Valid expressions
Name |
Expression |
Return type |
Size of range |
boost::size(a) |
boost::range_size<X>::type |
Expression semantics
Expression |
Semantics |
Postcondition |
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 |
Complexity guarantees
boost::size(a)
is at most amortized linear time.
Invariants
Range size |
boost::size(a) is equal to the distance from boost::begin(a)
to boost::end(a) . |
See also
implementation of
metafunctions
implementation of
functions
Bidirectional Range
Notation
X |
A type that is a model of Bidirectional Range. |
a |
Object of type X . |
Description
This 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.
Refinement of
Forward Range
Associated types
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. |
Const reverse iterator type |
boost::range_const_reverse_iterator<X>::type |
A type of reverse iterator that may be used to examine, but not
to modify, a Range's elements. |
Valid expressions
Name |
Expression |
Return type |
Semantics |
Beginning of range |
boost::rbegin(a) |
boost::range_reverse_iterator<X>::type if
a is mutable, boost::range_const_reverse_iterator<X>::type
otherwise. |
Equivalent to
boost::range_reverse_iterator<X>::type(boost::end(a)) . |
End of range |
boost::rend(a) |
boost::range_reverse_iterator<X>::type if
a is mutable, boost::range_const_reverse_iterator<X>::type
otherwise. |
Equivalent to
boost::range_reverse_iterator<X>::type(boost::begin(a)) . |
Complexity guarantees
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.
Invariants
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. |
Completeness |
An algorithm that iterates through the range [boost::rbegin(a),boost::rend(a))
will pass through every element of a . |
See also
implementation of metafunctions
implementation of
functions
Random Access Range
Description
A range X
where boost::range_iterator<X>::type
is a model
of Random Access Traversal Iterator
Refinement of
Bidirectional Range
Copyright © 2000 |
Jeremy Siek
|
Copyright © 2004 |
Thorsten Ottosen.
|