Boost logo

Boost :

From: George A. Heintzelman (georgeh_at_[hidden])
Date: 2001-08-09 14:50:32

> Using STL algorithms...
> I am unable to deduce a way of combining or reducing sequence
> containers into a single result or filtering arbitrary iterators with
> a predicate. So I have created these...
> REDUCE: applies a binary operator where the first argument is the
> current intermediate result and the second is each value in the
> sequence. The result of each function application becomes the new
> result.
> Example:
> vector<int> nums; //contains { 1, 2, 3 }
> int result = reduce(nums.begin(), nums.end(), plus<int>(), 0);
> //result = 6

This is just accumulate. (in the <numeric> header). In the case of
plus<int>() you don't even need the functor as it is the default.

> COMBINE: applies the plus operator to the elements in a sequence with
> a separator. Mostly useful for containers of strings -- but not
> limited to that.
> Example:
> string sep("|");
> vector<string> strs; //contains { "a", "b", "c" }
> string result = combine(strs.begin(), strs.end(), sep)
> //result = "a|b|c"

This is just accumulate with a more complicated functor:

struct combiner { // better name?
  combiner(const string &separator): mSep(separator);
  string operator()(const string &a, const string &b) {
        return a + separator + b;

string result = accumulate(strs.begin()+1, strs.end, strs.front(),
(the more complicated expression since we don't want the "|" if there
is only one element);

Now, what I WOULD like is an accumulate-like algorithm which takes
functors which take the first argument as a non-const reference, and
actually modify the first object. It needs to copy on the way in and
the way out, but not intermediate temporaries. This would avoid a bunch
of maybe needless copying, especially for string functions:

struct combiner {
  combiner(const string &separator): mSep(separator);
  string & operator()(string &a, const string &b) {
        a += separator;
        a += b;
        return a;

> FILTER: a wrapper for an iterator that applies a predicate functor.
> The resulting iterator only stops at objects that pass the predicate.
> vector<int> nums; //contains { 1, 15, 2, 10, 3 }
> int result = reduce(filter(nums.begin(),
> bind2nd(less_than<int>(),10)),
> nums.end(), plus<int>(), 0);

This syntax looks dangerous. How does filter() know what the end()
iterator should be? Isn't it possible that it will decide that
*nums.end() doesn't pass, and return (nums.end()+1), leading to
undefined behavior?

This is addressed by the filter iterator adaptor (boost/iterator_adaptor
s.hpp), which has the unfortunate fact of needing end() specified twice
(when used) for this reason; and in a more sparing syntax (but more
complex internals) by the View Template Library.

George Heintzelman

Boost list run by bdawes at, gregod at, cpdaniel at, john at