Introduction and motivation

| Home | Libraries | People | FAQ | More

#### Introduction and motivation

In its most simple form a Range Algorithm (or range-based algorithm) is simply an iterator-based algorithm where the two iterator arguments have been replaced by one range argument. For example, we may write

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

    std::vector<int> vec = ...;
    boost::sort(vec);

instead of

    std::sort(vec.begin(), vec.end());

However, the return type of range algorithms is almost always different from that of existing iterator-based algorithms.

One group of algorithms, like `boost::sort()`, will simply return the same range so that we can continue to pass the range around and/or further modify it. Because of this we may write

    boost:unique(boost::sort(vec));

to first sort the range and then run `unique()` on the sorted range.

Algorithms like `boost::unique()` fall into another group of algorithms that return (potentially) narrowed views of the original range. By default `boost::unique(rng)` returns the range `[boost::begin(rng), found)` where `found` denotes the iterator returned by `std::unique(boost::begin(rng), boost::end(rng))`

Therefore exactly the unique values can be copied by writing

    boost::copy(boost::unique(boost::sort(vec)),
                std::ostream_iterator<int>(std::cout));

Algorithms like `boost::unique` usually return the range: `[boost::begin(rng), found)`. However, this behaviour may be changed by supplying a `range_return_value` as a template parameter to the algorithm:

Expression | Return
--- | ---
`boost::unique<boost::return_found>(rng)` | returns a single iterator like `std::unique`
`boost::unique<boost::return_begin_found>(rng)` | returns the range `[boost::begin(rng), found)` (this is the default)
`boost::unique<boost::return_begin_next>(rng)` | returns the range `[boost::begin(rng), boost::next(found))`
`boost::unique<boost::return_found_end>(rng)` | returns the range `[found, boost::end(rng))`
`boost::unique<boost::return_next_end>(rng)` | returns the range `[boost::next(found),boost::end(rng))`
`boost::unique<boost::return_begin_end>(rng)` | returns the entire original range.

This functionality has the following advantages:

1. it allows for seamless functional-style programming where you do not need to use named local variables to store intermediate results
2. it is very safe because the algorithm can verify out-of-bounds conditions and handle tricky conditions that lead to empty ranges

For example, consider how easy we may erase the duplicates in a sorted container:

    std::vector<int> vec = ...;
    boost::erase(vec, boost::unique<boost::return_found_end>(boost::sort(vec)));

Notice the use of `boost::return_found_end`. What if we wanted to erase all the duplicates except one of them? In old-fashioned STL-programming we might write

    // assume 'vec' is already sorted
    std::vector<int>::iterator i = std::unique(vec.begin(), vec.end());

    // remember this check or you get into problems
    if (i != vec.end())
        ++i;

    vec.erase(i, vec.end());

The same task may be accomplished simply with

    boost::erase(vec, boost::unique<boost::return_next_end>(vec));

and there is no need to worry about generating an invalid range. Furthermore, if the container is complex, calling `vec.end()` several times will be more expensive than using a range algorithm.