A Range is a concept similar to the STL Container concept. A
Range provides iterators for accessing a closed-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.
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
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
begin(a)
range_iterator<X>::type if
a is mutable, range_const_iterator<X>::type
otherwise
End of range
end(a)
range_iterator<X>::type if
a is mutable, range_const_iterator<X>::type
otherwise
Is range empty?
empty(a)
Convertible to bool
Expression semantics
Expression
Semantics
Postcondition
begin(a)
Returns an iterator pointing to the first element in the Range.
begin(a) is either dereferenceable or past-the-end.
It is past-the-end if and only if size(a) == 0.
end(a)
Returns an iterator pointing one past the last element in the
Range.
end(a) is past-the-end.
empty(a)
Equivalent to begin(a) == end(a). (But possibly
faster.)
 -Â
Complexity guarantees
All three functions are at most amortized linear time. For most practical
purposes, one can expect begin(a), end(a) and empty(a)
to be amortized constant time.
Invariants
Valid range
For any Range a, [begin(a),end(a)) is
a valid range, that is, end(a) is reachable from begin(a)
in a finite number of increments.
Completeness
An algorithm that iterates through the range [begin(a),end(a))
will pass through every element of a.
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
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
size(a)
range_size<X>::type
Expression semantics
Expression
Semantics
Postcondition
size(a)
Returns the size of the Range, that is, its number
of elements. Note size(a) == 0u is equivalent to
empty(a).
size(a) >= 0
Complexity guarantees
size(a) is at most amortized linear time.
Invariants
Range size
size(a) is equal to the distance from begin(a)
to end(a).
This concept provides access to iterators that traverse in
both directions (forward and reverse). The
range_iterator<X>::type iterator must meet all of the requirements
of Bidirectional Traversal Iterator.
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
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
rbegin(a)
range_reverse_iterator<X>::type if
a is mutable, range_const_reverse_iterator<X>::type
otherwise.
Equivalent to
range_reverse_iterator<X>::type(end(a)).
End of range
rend(a)
range_reverse_iterator<X>::type if
a is mutable, range_const_reverse_iterator<X>::type
otherwise.
Equivalent to
range_reverse_iterator<X>::type(begin(a)).
Complexity guarantees
rbegin(a) has the same complexity as end(a) and rend(a)
has the same complexity as begin(a) from Forward Range.
Invariants
Valid reverse range
For any Bidirectional Range a, [rbegin(a),rend(a))
is a valid range, that is, rend(a) is reachable from rbegin(a)
in a finite number of increments.
Completeness
An algorithm that iterates through the range [rbegin(a),rend(a))
will pass through every element of a.
Boost
C++ Libraries