Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

c++ accumulate with move instead of copy

Tags:

c++

visual-c++

I have the following code

auto adder = [](string& s1, const string& s2)->string&&
   {
      if (!s1.empty())
         s1 += " ";
      s1 += s2;
      return move(s1);
   };

   string test;
   test.reserve(wordArray.size() * 10);
   string words = accumulate(wordArray.begin(), wordArray.end(), 
       move(test), adder);

What I would like here is to avoid string copying. Unfortunately this is not accomplished by the vs2012 implementation of accumulate. Internally accumulate calls another function _Accumulate and the rvalue functionality gets lost in the process.

It I instead call the _Accumulate function like so

string words = _Accumulate(wordArray.begin(), wordArray.end(), 
    move(test), adder);

I get the intended performance gain.

Must the std library be rewritten to take rvalue arguments into consideration?

Is there some other way I may use accumulate to accomplish what I want without cheating too much?

like image 304
Rolf W. Petersen Avatar asked Dec 05 '12 13:12

Rolf W. Petersen


1 Answers

Checking one of the recent post C++11 drafts (N3337.pdf) we can see that the effect of std::accumulate is specified as

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

So, the standard actually forbids implementations that use std::move for the old accumulator value like this:

template <class InputIterator, class T, class BinOp>
T accumulate (InputIterator first, InputIterator last, T init, BinOp binop)
{
  while (first!=last) {
    init = binop(std::move(init), *first);
    ++first;
  }
  return init;
}

which is unfortunate in your case.

Option (1): Implement this move-aware accumulate yourself.

Option (2): Keep using a functor like

struct mutating_string_adder {
  string operator()(string const& a, string const& b) const {return a+b;}
  string operator()(string & a, string const& b)      const {a += b; return std::move(a);}
  string operator()(string && a, string const& b)     const {a += b; return std::move(a);}
};

Note that I did not use rvalue reference return types here. This is intentional since it might avoid dangling reference issues, for example in the case where the last overload is picked and 'a' initialized to refer to a temporary object. All the operator+ overloads for strings also intentionally return by value.

Apart from that you might want to use std::copy in combination with std::stringstream and an output stream iterator.

Addendum: Alternate mutating_string_adder with some partial perfect forwarding:

struct mutating_string_adder {
  template<class T, class U>
  std::string operator()(T && a, U && b) const {
    return std::move(a) + std::forward<U>(b);
  }
};
like image 109
sellibitze Avatar answered Oct 23 '22 20:10

sellibitze