C++ "Generic" Programming Conundrum
Posted by Daniel Lyons Sat, 09 Jun 2007 20:01:00 GMT
Looking at C++, you sometimes see cool-looking code like this:
// load the numbers in the input file
copy(istream_iterator<double>(input),
istream_iterator<double>(),
back_inserter(numbers));
// get the sum
double sum = accumulate(numbers.begin(),
numbers.end(),
0.0);
// compute the average
double average = sum / numbers.length();
Of course, this traverses the vector twice, so you might think of a better way to do it would be to do a right fold across the vector, adding to the sum and incrementing the count until the vector is exhausted, and then do the division. You know, take this kind of code (untested):
double sum = 0;
int count = 0;
for (vector<double>::iterator i = numbers.begin();
i != numbers.end();
i++)
{
sum += *i;
count++;
}
double average = sum / count;
In OCaml or Haskell, we’d consider converting it into a right fold along these lines:
let average l =
let acc (sum, count) x = (sum + x, count + 1) in
let (sum, count) = List.fold_right acc l (0,0) in
sum / count
But this is C++, so instead of getting a closure or a fold function, we get accumulate, which takes a start and ending iterator and an initial value. It works just like a fold, but uses operator+ if you pass in an object. So, we can create an averaging functor like this:
class averaging_accumulator :
public binary_function<double,
averaging_accumulator<double>,
averaging_accumulator<double> >
{
public:
int count;
double sum;
// constructor
averaging_accumulator() : sum(0), count(0) {}
// compute the actual average
double average()
{
return sum / count;
}
// implement the binary operation between the two types
averaging_accumulator operator+(double d)
{
sum += d;
count += 1;
return *this;
}
};
So we can now implement an average with something along these lines:
averaging_accumulator acc; double average = accumulate(first, last, acc).average();
Of course, once we have this working we might want to make it work for floats also. So we make it into a template:
template <typename T>
class averaging_accumulator :
public binary_function<T,
averaging_accumulator<T>,
averaging_accumulator<T> >
{
public:
int count;
T sum;
averaging_accumulator() : sum(0), count(0) {}
// compute the actual average
T average()
{
return sum / count;
}
// implement the binary operation between the two types
averaging_accumulator operator+(T d)
{
sum += d;
count += 1;
return *this;
}
};
Another thing we might want is to make a function to compute the average. And naturally we’d want to make it a nice generic function along the lines of the builtins. The best example of that kind of programming I could find led me to write this:
template<typename InputIterator, typename T >
T average(InputIterator first, InputIterator last)
{
averaging_accumulator<T> acc;
return accumulate(first, last, acc).average();
}
Now, what I don’t understand is that I have to call this function like so:
double avg = average<vector<double>::iterator, double> (numbers.begin(), numbers.end());
Why do I have to include the iterator type and result type, when the internal call to accumulate does not? I couldn’t get it to compile any other way. Same thing with the other generic functions copy and transform—you never need to tell them what iterator type they’re receiving. I’d rather be able to call it like this:
double avg = average(numbers.begin(), numbers.end());
If anybody knows how to do this “the right way,” please let me know.
Update: I’ve figured out the way to do this. Replace your average function with this:
template<typename InputIterator>
typename iterator_traits<InputIterator>::value_type
average(InputIterator first, InputIterator last)
{
averaging_accumulator<typename iterator_traits<InputIterator>::value_type> acc;
return accumulate(first, last, acc).average();
}
In short, instead of having a type parameter T, derive it from your iterator’s type using iterator_traits. That class is parameterized by an iterator and provides a number of different type definitions, but the only one you’ll care about is value_type. Due to changes in the C++ standard, you now need a prefix typename before a template expanded type name like that, so your complete type is going to look like typename iterator_traits<InputIterator>::value_type as in the above code. Then, the compiler will be able to figure out the template parameters (but only for functions, not classes). If you have a longer function and you need the value_type more than once, you can make a typedef local to this function.
