Boost.Range

Synopsis and Reference

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*)
Warning: support for null-terminated strings is deprecated and will disappear in the next Boost release (1.34).
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*

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

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 p.first if p is of type std::pair<T> a if a is an array s if s is a string literal boost_range_begin(x) if that expression would invoke a function found by ADL t.begin() otherwise constant time

end(x) range_result_iterator<X>::type p.second if p is of type std::pair<T> a + sz if a is an array of size sz s + std::char_traits<X>::length( s ) if s is a Char* s + sz - 1 if s is a string literal of size sz boost_range_end(x) if that expression would invoke a function found by ADL t.end() otherwise 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 std::distance(p.first,p.second) if p is of type std::pair<T> sz if a is an array of size sz end(s) - s if s is a string literal or a Char* boost_range_size(x) if that expression would invoke a function found by ADL t.size() otherwise 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)

Expression	Return type	Returns	Complexity
`begin(x)`	`range_result_iterator<X>::type`	`p.first` if `p` is of type `std::pair<T> a if a is an array s if s is a string literal boost_range_begin(x) if that expression would invoke a function found by ADL t.begin() otherwise`	constant time
`end(x)`	`range_result_iterator<X>::type`	`p.second` if `p` is of type `std::pair<T> a + sz if a is an array of size sz s + std::char_traits<X>::length( s ) if s is a Char* s + sz - 1 if s is a string literal of size sz boost_range_end(x) if that expression would invoke a function found by ADL t.end() otherwise`	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`	`std::distance(p.first,p.second)` if `p` is of type `std::pair<T> sz if a is an array of size sz end(s) - s if s is a string literal or a Char* boost_range_size(x) if that expression would invoke a function found by ADL t.size() otherwise`	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

Method 1: provide member functions and nested types
Method 2: provide free-standing functions and specialize metafunctions

Method 1: provide member functions and nested types

This procedure assumes that you have control over the types that should be made conformant to a Range concept. If not, see method 2.

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

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

iterator Single Pass Range

const_iterator Single Pass Range

size_type Forward Range

Member type	Related concept
`iterator`	Single Pass Range
`const_iterator`	Single Pass Range
`size_type`	Forward Range

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

Method 2: provide free-standing functions and specialize metafunctions

This procedure assumes that you cannot (or do not wish to) change the types that should be made conformant to a Range concept. If this is not true, see method 1.

The primary templates in this library are implemented such that certain functions are found via argument-dependent-lookup (ADL). Below is given an overview of which free-standing functions a class must specify to be useable as a certain Range concept. Let x be a variable (const or mutable) of the class in question.

Function Related concept
boost_range_begin(x) Single Pass Range

boost_range_end(x) Single Pass Range

boost_range_size(x) Forward Range

Function	Related concept
`boost_range_begin(x)`	Single Pass Range
`boost_range_end(x)`	Single Pass Range
`boost_range_size(x)`	Forward Range

boost_range_begin() and boost_range_end() must be overloaded for both const and mutable reference arguments.

You must also specialize 3 metafunctions for your type X:

Metafunction Related concept
boost::range_iterator Single Pass Range

boost::range_const_iterator Single Pass Range

boost::range_size Forward Range

Metafunction	Related concept
`boost::range_iterator`	Single Pass Range
`boost::range_const_iterator`	Single Pass Range
`boost::range_size`	Forward Range

A complete example is given here:

#include <boost/range.hpp>
#include <iterator>         // for std::iterator_traits, std::distance()

namespace Foo
{
	//
	// Our sample UDT. A 'Pair'
	// will work as a range when the stored
	// elements are iterators.
	//
	template< class T >
	struct Pair
	{
		T first, last;	
	};

} // namespace 'Foo'

namespace boost
{
	//
	// Specialize metafunctions. We must include the range.hpp header.
	// We must open the 'boost' namespace.
	//

	template< class T >
	struct range_iterator< Foo::Pair<T> >
	{
		typedef T type;
	};

	template< class T >
	struct range_const_iterator< Foo::Pair<T> >
	{
		//
		// Remark: this is defined similar to 'range_iterator'
		//         because the 'Pair' type does not distinguish
		//         between an iterator and a const_iterator.
		//
		typedef T type;
	};

	template< class T >
	struct range_size< Foo::Pair<T> >
	{

		typedef std::size_t type;
	};

} // namespace 'boost'

namespace Foo
{
	//
	// The required functions. These should be defined in
	// the same namespace as 'Pair', in this case 
	// in namespace 'Foo'.
	//
	
	template< class T >
	inline T boost_range_begin( Pair<T>& x )
	{ 
		return x.first;
	}

	template< class T >
	inline T boost_range_begin( const Pair<T>& x )
	{ 
		return x.first;
	}

	template< class T >
	inline T boost_range_end( Pair<T>& x )
	{ 
		return x.last;
	}

	template< class T >
	inline T boost_range_end( const Pair<T>& x )
	{ 
		return x.last;
	}

	template< class T >
	inline typename boost::range_size< Pair<T> >::type
	boost_range_size( const Pair<T>& x )
	{
		return std::distance(x.first,x.last);
	}

} // namespace 'Foo'

#include <vector>

int main()
{
	typedef std::vector<int>::iterator  iter;
	std::vector<int>                    vec;
	Foo::Pair<iter>                     pair = { vec.begin(), vec.end() };
	const Foo::Pair<iter>&              cpair = pair; 
	//
	// Notice that we call 'begin' etc with qualification. 
	//
	iter i = boost::begin( pair );
	iter e = boost::end( pair );
	i      = boost::begin( cpair );
	e      = boost::end( cpair );
	boost::range_size< Foo::Pair<iter> >::type s = boost::size( pair );
	s      = boost::size( cpair );
	boost::range_const_reverse_iterator< Foo::Pair<iter> >::type
	ri     = boost::rbegin( cpair ),
	re     = boost::rend( cpair );
}