高效积累

Question

假设我有字符串向量,我想通过std :: accumulate连接它们.

如果我使用以下代码:

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

我可以肯定会有临时对象构造.

在这个答案中,他们说std :: accumulate的效果是这样指定的:

通过初始化累加器acc初始值init计算其结果,然后按顺序对[= first,last]范围内的每个迭代器i用acc = acc +*i或acc = binary_op(acc,*i)修改它.

所以我想知道这样做的正确方法是什么,以避免不必要的临时对象构造.

一个想法是以这种方式改变lambda:

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

在这种情况下,我认为我强制有效串联字符串并帮助编译器(我知道我不应该)省略不必要的副本,因为这应该等同于(伪代码):

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

因此

accum = & accum;

另一个想法是使用

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

但这可能会导致类似于:

accum = std::move(& accum);

这看起来很可疑.

写这个的正确方法是什么,以尽量减少不必要的临时对象创建的风险？我不仅对std :: string感兴趣,我很乐意有一个解决方案,这可能适用于任何具有复制和移动构造函数/赋值的对象.

Answer 1

我会将其分解为两个操作,首先std::accumulate获取需要创建的字符串的总长度,然后std::for_each使用更新本地字符串的lambda:

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; });

对此的常见替代方法是使用表达式模板,但这不适合答案.基本上,您创建一个映射操作的数据结构,但不执行它们.最终评估表达式时,它可以预先收集所需的信息,并使用它来保留空间并执行复制.使用表达式模板的代码更好,但更复杂.

Answer 2

在std::accumulate没有任何冗余副本的情况下有效使用并不明显。
除了被重新分配和传入和传出 lambda 之外，累积值可能会被实现在内部复制。
另请注意，std::accumulate()它本身采用初始值by-value，调用 copy-ctor ，从而忽略reserve()对副本源所做的任何s （如其他一些答案中所建议的那样）。

我发现连接字符串的最有效方法如下：

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;
});

结果将在res.
此实现没有冗余副本、移动或重新分配。

Answer 3

尝试以下操作

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

在这呼唤之前也许有一种呼唤的意义

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 );