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. It is conceivable that some algorithms are capable of optimization by tightly coupling the filter with the algorithm. The adaptors provide a more general solution with superior separation of orthogonal concerns.

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::size( rng | boost::adaptors::filtered(pred) );

What this means is that many algorithms no longer require nor benefit from an optimized implementation with an _if suffix. Furthermore, it turns out that algorithms with the _copy suffix are often not needed either. Consider 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 many of the _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