Boost.Range Range Implementation

#
Boost.Range

## Single Pass Range, Forward Range and Bidirectional Range Implementation

- Overview
- Synopsis
- Semantics
- Extending the library

### Overview

Four types of objects are currently supported by the library:

- standard-like containers
- `std::pair<iterator,iterator>`
- null terminated strings (this includes `char[]`,`wchar_t[]`, `char*`, and `wchar_t*`)
- built-in arrays

Even though the behavior of the primary templates are exactly such that standard containers will be supported by default, the requirements are much lower than the standard container requirements. For example, the utility class `iterator_range` implements the minimal interface required to make the class a Forward Range.

Please also see Range concepts for more details.

### Synopsis

    namespace boost
    {
        //
        // Single Pass Range metafunctions
        //

        template< class T >
        struct range_value;

        template< class T >
        struct range_iterator;

        template< class T >
        struct range_const_iterator;

        //
        // Forward Range metafunctions
        //

        template< class T >
        struct range_difference;

        template< class T >
        struct range_size;

        //
        // Bidirectional Range metafunctions
        //

        template< class T >
        struct range_reverse_iterator;

        template< class T >
        struct range_const_reverse_iterator;

        //
        // Special metafunctions
        //

        template< class T >
        struct range_result_iterator;

        template< class T >
        struct range_reverse_result_iterator;

        //
        // Single Pass Range functions
        //

        template< class T >
        typename range_iterator<T>::type
        begin( T& c );

        template< class T >
        typename range_const_iterator<T>::type
        begin( const T& c );

        template< class T >
        typename range_iterator<T>::type
        end( T& c );

        template< class T >
        typename range_const_iterator<T>::type
        end( const T& c );

        template< class T >
        bool
        empty( const T& c );

        //
        // Forward Range functions
        //

        template< class T >
        typename range_size<T>::type
        size( const T& c );

        //
        // Bidirectional Range functions
        //

        template< class T >
        typename range_reverse_iterator<T>::type
        rbegin( T& c );

        template< class T >
        typename range_const_reverse_iterator<T>::type
        rbegin( const T& c );

        template< class T >
        typename range_reverse_iterator<T>::type
        rend( T& c );

        template< class T >
        typename range_const_reverse_iterator<T>::type
        rend( const T& c );

        //
        // Special const Range functions
        //

        template< class T >
        typename range_const_iterator<T>::type
        const_begin( const T& r );

        template< class T >
        typename range_const_iterator<T>::type
        const_end( const T& r );

        template< class T >
        typename range_const_reverse_iterator<T>::type
        const_rbegin( const T& r );

        template< class T >
        typename range_const_reverse_iterator<T>::type
        const_rend( const T& r );

    } // namespace 'boost'

### Semantics

#### notation

Type | Object | Describes
--- | --- | ---
`X` | `x` | any type
`T` | `t` | denotes behavior of the primary templates
`P` | `p` | denotes `std::pair<iterator,iterator>`
`A[sz]` | `a` | denotes an array of type `A` of size `sz`
`Char*` | `s` | denotes either `char*` or `wchar_t*`

Please notice in tables below that when four lines appear in a cell, the first line will describe the primary template, the second line pairs of iterators, the third line arrays and the last line null-terminated strings.

#### Metafunctions

Expression | Return type | Complexity
--- | --- | ---
`range_value<X>::type` | `T::value_type` `boost::iterator_value<P::first_type>::type` `A` `Char` | compile time
`range_iterator<X>::type` | `T::iterator` `P::first_type` `A*` `Char*` | compile time
`range_const_iterator<X>::type` | `T::const_iterator` `P::first_type` `const A*` `const Char*` | compile time
`range_difference<X>::type` | `T::difference_type` `boost_iterator_difference<P::first_type>::type` `std::ptrdiff_t` `std::ptrdiff_t` | compile time
`range_size<X>::type` | `T::size_type` `std::size_t` `std::size_t` `std::size_t` | compile time
`range_result_iterator<X>::type` | `range_const_iterator<X>::type` if `X` is `const` `range_iterator<X>::type` otherwise | compile time
`range_reverse_iterator<X>::type` | `boost::reverse_iterator< typename range_iterator<T>::type >` | compile time
`range_const_reverse_iterator<X>::type` | `boost::reverse_iterator< typename range_const_iterator<T>::type >` | compile time
`range_reverse_result_iterator<X>::type` | `boost::reverse_iterator< typename range_result_iterator<T>::type >` | compile time

The special metafunctions `range_result_iterator` and `range_reverse_result_iterator` are not part of any Range concept, but they are very useful when implementing certain Range classes like `sub_range` because of their ability to select iterators based on constness.

#### Functions

Expression | Return type | Returns | Complexity
--- | --- | --- | ---
`begin(x)` | `range_result_iterator<X>::type` | `t.begin()` `p.first` `a` `s` | constant time

`end(x)`

`range_result_iterator<X>::type`

`t.end()`
`p.second`
`a + sz`
`s + std::char_traits<X>::length( s )` if `X` is `Char*`
`s + sz - 1` if `X` is `Char[sz]`

linear if `X` is `Char*`
constant time otherwise

`empty(x)` | `bool` | `begin(x) == end( x )` | linear if `X` is `Char*` constant time otherwise
`size(x)` | `range_size<X>::type` | `t.size()` `std::distance(p.first,p.second)` `sz` `end(s) - s` | linear if `X` is `Char*` or if `std::distance()` is linear constant time otherwise
`rbegin(x)` | `range_reverse_result_iterator<X>::type` | `range_reverse_result_iterator<X>::type( end(x) )` | same as `end(x)`
`rend(x)` | `range_reverse_result_iterator<X>::type` | `range_reverse_result_iterator<X>::type( begin(x) )` | same as `begin(x)`
`const_begin(x)` | `range_const_iterator<X>::type` | `range_const_iterator<X>::type( begin(x) )` | same as `begin(x)`
`const_end(x)` | `range_const_iterator<X>::type` | `range_const_iterator<X>::type( end(x) )` | same as `end(x)`
`const_rbegin(x)` | `range_const_reverse_iterator<X>::type` | `range_const_reverse_iterator<X>::type( rbegin(x) )` | same as `rbegin(x)`
`const_rend(x)` | `range_const_reverse_iterator<X>::type` | `range_const_reverse_iterator<X>::type( rend(x) )` | same as `rend(x)`

The special `const` functions are not part of any Range concept, but are very useful when you want to document clearly that your code is read-only.

### Extending the library

The primary templates in this library are implemented such that standard containers will work automatically and so will `boost::array`. Below is given an overview of which member functions and member types a class must specify to be useable as a certain Range concept.

Member function | Related concept
--- | ---
`begin()` | Single Pass Range
`end()` | Single Pass Range
`size()` | Forward Range

Notice that `rbegin()` and `rend()` member functions are not needed even though the container can support bidirectional iteration.

The required member types are:

Member type | Related concept
--- | ---
`value_type` | Single Pass Range
`iterator` | Single Pass Range
`const_iterator` | Single Pass Range
`difference_type` | Forward Range
`size_type` | Forward Range

Again one should notice that member types `reverse_iterator` and `const_reverse_iterator` are not needed.

(C) Copyright Thorsten Ottosen 2003-2004