## Boost.Range |

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,

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.

`X` |
A type that is a model of Single Pass Range. |

`a` |
Object of type `X` . |

A range X where `range_iterator<X>::type`

is a model of
Single Pass Iterator

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. |

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

`begin(a)`

, `end(a)`

and `empty(a)`

to be amortized constant time.
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` . |

`X` |
A type that is a model of Forward Range. |

`a` |
Object of type `X` . |

A range `X`

where `range_iterator<X>::type`

is a model
of Forward Traversal Iterator

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. |

Name | Expression | Return type |
---|---|---|

Size of range | `size(a)` |
`range_size<X>::type` |

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` |

`size(a)`

is at most amortized linear time.

Range size | `size(a)` is equal to the distance from `begin(a)`
to `end(a)` . |

`X` |
A type that is a model of Bidirectional Range. |

`a` |
Object of type `X` . |

`range_iterator<X>::type`

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

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))` . |

`rbegin(a)`

has the same complexity as `end(a)`

and `rend(a)`

has the same complexity as `begin(a)`

from Forward Range.

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` . |

A range `X`

where `range_iterator<X>::type`

is a model
of Random Access Traversal Iterator

Copyright © 2000 | Jeremy Siek |

Copyright © 2004 | Thorsten Ottosen. |