
Boost.Range 
Range concepts
Overview
A Range is a concept similar to the STL Container concept. A
Range provides iterators for accessing a halfopen 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 Containerlike 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 nonconst) 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 freestanding 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 pasttheend.
It is pasttheend 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 pasttheend. 
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
Concept Checking
Each of the range concepts has a corresponding concept checking
class in the file boost/range/concepts.hpp. 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.
See also
Range Terminology and style guidelines
Iterator Concepts
Boost Concept Check library
Copyright © 2000 
Jeremy Siek

Copyright © 2004 
Thorsten Ottosen. Use, modification and distribution is subject to the Boost Software License, Version 1.0.
