Boost.Range

Range concepts

Overview

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

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 range_iterator<X>::type is a model of Single Pass Iterator

Associated types

Value type range_value<X>::type The type of the object stored in a Range.
Iterator type 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 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.

See also

Container

Forward Range

Notation

X A type that is a model of Forward Range.
a Object of type X.

Description

A range X where range_iterator<X>::type is a model of Forward Traversal Iterator

Refinement of

Single Pass Range

Associated types

Distance type 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 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).

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 range_iterator<X>::type iterator must meet all of the requirements of Bidirectional Traversal Iterator.

Refinement of

Forward Range

Associated types

Reverse Iterator type 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 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.

Random Access Range

Description

A range X where range_iterator<X>::type is a model of Random Access Traversal Iterator

Refinement of

Bidirectional Range

Copyright © 2000 Jeremy Siek
Copyright © 2004 Thorsten Ottosen.