Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

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.


PrevUpHomeNext