ansaurus

Question

implicit promotion to avoid overflow in std::partial_sum

Answer 1

+1 A:

According to http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#539, partial_sum has been completely redefined since n3000 (the latest release):

Effects: Let VT be InputIterator's value type. For a nonempty range, initializes an accumulator acc of type VT with *first and performs *result = acc. For every iterator i in [first + 1, last) in order, acc is then modified by acc = acc + *i or acc = binary_op(acc, *i) and is assigned to *(result + (i - first)).

and

The 'widening' behaviour can then be obtained by writing a custom proxy iterator, which is somewhat involved.

I really can't see the advantage of doing things this way. Reading the defect report, I don't see any justification besides

The intent of the algorithms is to perform their calculations using the type of the input iterator.

Arrrgh.

Edit: I went ahead and implemented a widening input iterator. Works as advertised.

template< class Base, class Wider >
struct widen_iter : iterator< input_iterator_tag, Wider > {
    Base b;
    widen_iter( Base const &inb = Base() ) : b( inb ) {}
    Wider operator*() const { return Wider( *b ); }
    Wider const *operator->() const { Wider t( *b ), *ta = &t; return ta; }
    widen_iter &operator++() { ++ b; return *this; }
    widen_iter operator++(int) { widen_iter t = *this; ++ b; return t; }
    bool operator==( widen_iter const &r ) const { return b == r.b; }
    bool operator!=( widen_iter const &r ) const { return b != r.b; }
};
template< class Wider, class Base >
widen_iter< Base, Wider >
widener( Base b ) { return widen_iter< Base, Wider >( b ); }

Would be a lot shorter if there were a generic filter-by-functor input iterator.

Potatoswatter 2010-02-03 04:10:25

Use std::accumulate instead, with the `init` value storing and incrementing the output iterator and using the wider type to store the running total? accumulate guarantees that the additions are performed in order.

Steve Jessop 2010-02-03 11:36:23

+1 Can't see why avoiding overflow should be made harder than achieving overflow. As a solution: write your own partial_sum?

UncleBens 2010-02-03 16:31:35

@Steve: That might be a shorter solution. `init` only has to implement `operator+` and `operator=`. Very specific, though. @Uncle: Yeah, looks like that would also be a more practical solution, although doing it properly (accepting fn ptrs) would require template introspection.

Potatoswatter 2010-02-03 17:58:48

@Potatoswatter: you could write your own `partial_sum_convert` that's identical to the standard one except with an additional template parameter `AccumulatorType`. Make it the first parameter, so that you don't have to specify the iterator types when you call it. Then no introspection needed, just call `partial_sum_convert<uint32_t>(first, last, out, op);`. If the return type of op isn't assignable to AccumulatorType, or the op can't take (AccumulatorType, InputIterator::value_type) as parameters, that's the caller's problem.

Steve Jessop 2010-02-03 18:21:08

... still quite specific, but then it's being done to address a specific difficulty with using partial_sum. If there are other uses for your widening iterator, then that's probably a better solution overall.

Steve Jessop 2010-02-03 18:27:08

@Steve: agreed. There are certainly other uses for a generic filtering input iterator, though. Then all you need is `template< class D, class S > D conv( S const }` and `partial_sum( filterer< conv >( first ), filterer< conv >( last ), result )`, assuming `filterer` is a properly intelligent factory. I don't have Boost installed but it looks like `boost::transform_iterator` implements `filter`.

Potatoswatter 2010-02-03 19:07:46

ansaurus

tags:

views:

answers:

implicit promotion to avoid overflow in std::partial_sum

related questions