| # Boost.Range

## Range concepts

- Overview
- Single Pass Range
- Forward Range
- Bidirectional Range
- Random Access Range
- Concept Checking

### 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 much 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 their 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

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_iterator<const 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_iterator<const X>::type` otherwise
End of range | `boost::end(a)` | `boost::range_iterator<X>::type` if `a` is mutable, `boost::range_iterator<const X>::type` otherwise

### 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::distance(a) == 0`.
`boost::end(a)` | Returns an iterator pointing one past the last element in the Range. | `boost::end(a)` is past-the-end.

### Complexity guarantees

`boost::end(a)` is at most amortized linear time, `boost::begin(a)` is amortized constant time. For most practical purposes, one can expect both 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

Extending the library for UDTs

Implementation of metafunctions

Implementation of functions

Container

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

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

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

- Class `SinglePassRangeConcept` checks for Single Pass Range
- Class `ForwardRangeConcept` checks for Forward Range
- Class `BidirectionalRangeConcept` checks for Bidirectional Range
- Class `RandomAccessRangeConcept` checks for Random Access Range

### See also

Range Terminology and style guidelines

Iterator Concepts

Boost Concept Check library

© Copyright Thorsten Ottosen 2008.

Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at www.boost.org/LICENSE_1_0.txt)