Introduction and motivation

| Home | Libraries | People | FAQ | More

#### 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_iterator`s. 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:

- `boost::copy( rng, out )`
- `boost::count( rng, pred )`

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:

- `boost::copy_if( rng, pred, out )`
- `boost::count_if( rng, pred )`

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