Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

Introduction and motivation

A Range Adaptor is a class that wraps an existing Range to provide a new Range with different behaviour. Since the behaviour of Ranges is determined by their associated iterators, a Range Adaptor simply wraps the underlying iterators with new special iterators. In this example

#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <iostream>
#include <vector>

std::vector<int> vec;
boost::copy( vec | boost::adaptors::reversed,
             std::ostream_iterator<int>(std::cout) );

the iterators from vec are wrapped reverse_iterators. The type of the underlying Range Adapter is not documented because you do not need to know it. All that is relevant is that the expression

vec | boost::adaptors::reversed

returns a Range Adaptor where the iterator type is now the iterator type of the range vec wrapped in reverse_iterator. The expression boost::adaptors::reversed is called an Adaptor Generator.

There are two ways of constructing a range adaptor. The first is by using operator|(). This is my preferred technique, however while discussing range adaptors with others it became clear that some users of the library strongly prefer a more familiar function syntax, so equivalent functions of the present tense form have been added as an alternative syntax. The equivalent to rng | reversed is adaptors::reverse(rng) for example.

Why do I prefer the operator| syntax? The answer is readability:

std::vector<int> vec;
boost::copy( boost::adaptors::reverse(vec),
             std::ostream_iterator<int>(std::cout) );

This might not look so bad, but when we apply several adaptors, it becomes much worse. Just compare

std::vector<int> vec;
boost::copy( boost::adaptors::unique( boost::adaptors::reverse( vec ) ),
             std::ostream_iterator<int>(std::cout) );

to

std::vector<int> vec;
boost::copy( vec | boost::adaptors::reversed
                 | boost::adaptors::uniqued,
             std::ostream_iterator<int>(std::cout) );

Furthermore, some of the adaptor generators take arguments themselves and these arguments are expressed with function call notation too. In those situations, you will really appreciate the succinctness of operator|().

Composition of Adaptors

Range Adaptors are a powerful complement to Range algorithms. The reason is that adaptors are orthogonal to algorithms. For example, consider these Range algorithms:

What should we do if we only want to copy an element a if it satisfies some predicate, say pred(a)? And what if we only want to count the elements that satisfy the same predicate? The naive answer would be to use these algorithms:

These algorithms are only defined to maintain a one to one relationship with the standard library algorithms. This approach of adding algorithm suffers a combinatorial explosion. Inevitably many algorithms are missing _if variants and there is redundant development overhead for each new algorithm. The Adaptor Generator is the design solution to this problem.

Range Adaptor alternative to copy_if algorithm

boost::copy_if( rng, pred, out );

can be expressed as

boost::copy( rng | boost::adaptors::filtered(pred), out );

Range Adaptor alternative to count_if algorithm

boost::count_if( rng, pred );

can be expressed as

boost::count( rng | boost::adaptors::filtered(pred), out );

What this means is that no algorithm with the _if suffix is needed. Furthermore, it turns out that algorithms with the _copy suffix are not needed either. Consider the somewhat misdesigned replace_copy_if() which may be used as

std::vector<int> vec;
boost::replace_copy_if( rng, std::back_inserter(vec), pred, new_value );

With adaptors and algorithms we can express this as

std::vector<int> vec;
boost::push_back(vec, rng | boost::adaptors::replaced_if(pred, new_value));

The latter code has several benefits:

1. it is more efficient because we avoid extra allocations as might happen with std::back_inserter

2. it is flexible as we can subsequently apply even more adaptors, for example:

boost::push_back(vec, rng | boost::adaptors::replaced_if(pred, new_value)
                          | boost::adaptors::reversed);

3. it is safer because there is no use of an unbounded output iterator.

In this manner, the composition of Range Adaptors has the following consequences:

1. we no longer need _if, _copy, _copy_if and _n variants of algorithms.

2. we can generate a multitude of new algorithms on the fly, for example, above we generated reverse_replace_copy_if()

In other words:

Range Adaptors are to algorithms what algorithms are to containers


PrevUpHomeNext