*This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of Resolved status.*

`std::move`

in `std::accumulate`

and other algorithms**Section:** 27.10 [numeric.ops] **Status:** Resolved
**Submitter:** Chris Jefferson **Opened:** 2011-01-01 **Last modified:** 2020-09-06

**Priority: **3

**View all other** issues in [numeric.ops].

**View all issues with** Resolved status.

**Discussion:**

The C++0x draft says `std::accumulate`

uses: `acc = binary_op(acc, *i)`

.

Eelis van der Weegen has pointed out, on the libstdc++ mailing list, that using
`acc = binary_op(std::move(acc), *i)`

can lead to massive improvements (particularly,
it means accumulating strings is linear rather than quadratic).

Consider the simple case, accumulating a bunch of strings of length 1 (the same argument holds for other length buffers).
For strings `s`

and `t`

, `s+t`

takes time `length(s)+length(t)`

, as you have to copy
both `s`

and `t`

into a new buffer.

So in accumulating `n`

strings, step `i`

adds a string of length `i-1`

to a string of length
1, so takes time `i`

.

Therefore the total time taken is: `1+2+3+...+n`

= O(`n`

)
^{2}

`std::move(s)+t`

, for a "good" implementation, is amortized time `length(t)`

, like `vector`

,
just copy `t`

onto the end of the buffer. So the total time taken is:

`1+1+1+...+1`

(`n`

times) = O(`n`

). This is the same as `push_back`

on a `vector`

.

I'm trying to decide if this implementation might already be allowed. I suspect it might not
be (although I can't imagine any sensible code it would break). There are other algorithms
which could benefit similarly (`inner_product`

, `partial_sum`

and
`adjacent_difference`

are the most obvious).

Is there any general wording for "you can use rvalues of temporaries"?

The reflector discussion starting with message c++std-lib-29763 came to the conclusion that above example is not covered by the "as-if" rules and that enabling this behaviour would seem quite useful.

*[
2011 Bloomington
]*

Moved to NAD Future. This would be a larger change than we would consider for a simple TC.

*[2017-02 in Kona, LEWG responds]*

Like the goal.

What is broken by adding std::move() on the non-binary-op version?

A different overload might be selected, and that would be a breakage. Is it breakage that we should care about?

We need to encourage value semantics.

Need a paper. What guidance do we give?

Use std::reduce() (uses generalized sum) instead of accumulate which doesn’t suffer it.

Inner_product and adjacent_difference also. adjacent_difference solves it half-way for “val” object, but misses the opportunity for passing acc as `std::move(acc)`

.

*[2017-06-02 Issues Telecon]*

Ville to encourage Eelis to write a paper on the algorithms in <numeric>, not just for accumulate.

Howard pointed out that this has already been done for the algorithms in <algorithm>

Status to Open; Priority 3

*[2017-11-11, Albuquerque]*

This was resolved by the adoption of P0616r0.

**Proposed resolution:**