Re: [boost] Proposed algorithm library: reduce, combine, filter, guard

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(), 
                           combiner("|"));
(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
georgeh_at_[hidden]