Effective accumulation

Question

Suppose I have a row vector, and I want to combine them through std :: accumulate.

If I use the following code:

std::vector<std::string> foo{"foo","bar"}; string res=""; res=std::accumulate(foo.begin(),foo.end(),res, [](string &rs,string &arg){ return rs+arg; }); 

I am sure there will be a temporary construction of the object.

In this answer, they say that the effect of std :: accumulate is specified this way:

Computes its result by initializing the battery acc with the initial value init, and then changing it with acc = acc + * i or acc = binary_op (acc, * i) for each iterator i in the range [first, last] in order.

So, I am wondering how to do this in order to avoid the unnecessary construction of temporary objects.

One idea was to change lambda like this:

 [](string &rs,string &arg){ rs+=arg; return rs; } 

In this case, I thought I could force the string concatenation and help the compiler (I know that I shouldn't ) omit the unnecessary copy, as this should be equivalent (pseudo-code):

 accum = [](& accum,& arg){ ...; return accum; } 

and therefore

 accum = & accum; 

Another idea was to use

 accum = [](& accum,& arg){ ...; return std::move(accum); } 

But this will probably lead to something like:

 accum = std::move(& accum); 

Which looks very suspicious to me.

What is the correct way to write this in order to minimize the risk of unnecessarily creating temporary objects? I am not only interested in std :: string, I would be happy to get a solution that will probably work for any object that has copy and move constructors / assignments.

Answer 1

Try to execute

 res=std::accumulate(foo.begin(),foo.end(),res, [](string &rs, const string &arg) -> string & { return rs+=arg; }); 

Before this call, there may be a call to call

 std::string::size_type n = std::accumulate( foo.begin(), foo.end(), std::string::size_type( 0 ), [] ( std::string_size_type n, const std::string &s ) { return ( n += s.size() ); } ); res.reserve( n ); 

Answer 2

I would break it down into two operations, first std::accumulate , to get the total length of the string to be created, and then std::for_each with a lambda that updates the local string:

 std::string::size_type total = std::accumulate(foo.begin(), foo.end(), 0u, [](std::string::size_type c, std::string const& s) { return c+s.size() }); std::string result; result.reserve(total); std::for_each(foo.begin(), foo.end(), [&](std::string const& s) { result += s; }); 

A common alternative to this is to use expression patterns, but this does not match the answers. Basically, you create a data structure that displays operations but does not execute them. When the expression is finally evaluated, it can collect the information they need and use it to reserve space and copy. Code that uses an expression pattern is nicer, but more complex.

Answer 3

Using std::accumulate effectively without any redundant copies is not obvious.
In addition to being reassigned and transferred to and because of lambda, the accumulated value can be copied internally through implementation.
Also note that std::accumulate() itself assumes the initial value by value, calling copy-ctor and thus ignoring any reserve() executed to the copy source (as suggested in some other answers).

The most efficient way I've found to concatenate strings is as follows:

 std::vector<std::string> str_vec{"foo","bar"}; // get reserve size: auto sz = std::accumulate(str_vec.cbegin(), str_vec.cend(), std::string::size_type(0), [](int sz, auto const& str) { return sz + str.size() + 1; }); std::string res; res.reserve(sz); std::accumulate(str_vec.cbegin(), str_vec.cend(), std::ref(res), // use a ref wrapper to keep same object with capacity [](std::string& a, std::string const& b) -> std::string& // must specify return type because cannot return `std::reference_wrapper<std::string>`. { // can't use `auto&` args for the same reason a += b; return a; }); 

The result will be in res .
This implementation does not have redundant copies, moves, or redistributions.

Answer 4

This is a bit complicated, as there are two operations, adding and assigning. To avoid copying, you need to both change the line in the add-on, and make sure that the assignment is not an operator. This is the second part, which is difficult.

What I did at different times was to create a custom “battery” along the lines:

 class Accu { std::string myCollector; enum DummyToSuppressAsgn { dummy }; public: Accu( std::string const& startingValue = std::string() ) : myCollector( startingValue ) { } // Default copy ctor and copy asgn are OK. // On the other hand, we need the following special operators Accu& operator=( DummyToSuppressAsgn ) { // Don't do anything... return *this; } DummyToSuppressAsgn operator+( std::string const& other ) { myCollector += other; return dummy; } // And to get the final results... operator std::string() const { return myCollector; } }; 

When calling accumulate will be several copies, and the return value, but during the actual accumulation, is nothing. Just cry out:

 std::string results = std::accumulate( foo.begin(), foo.end(), Accu() ); 

(If you really care about performance, you can add the capacity argument to the Accu constructor so that it can execute reserve in the member string. If I did this, I would probably manually write the copy constructor to make sure the row in the copied object had the required capacity.)