8

假设我有字符串向量，我想通过 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 的效果是这样指定的：

通过使用初始值 init 初始化累加器 acc 来计算其结果，然后按顺序使用 acc = acc + *i 或 acc = binary_op(acc, *i) 为范围 [first,last) 中的每个迭代器 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 感兴趣，我很高兴有一个解决方案，它可能适用于任何实现了复制和移动构造函数/分配的对象。

4

4 回答 4

11

我会将其分为两个操作，首先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; });

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

于 2013-10-29T16:48:25.123 回答
5

在没有任何冗余副本的情况下有效使用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.
此实现没有冗余副本、移动或重新分配。

于 2016-09-14T15:23:16.797 回答
4

尝试以下

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 );
于 2013-10-29T16:47:13.083 回答
1

这有点棘手，因为涉及到两个操作，加法和赋值。为了避免复制，您必须同时修改加法中的字符串，并 确保分配是空操作。这是棘手的第二部分。

我有时所做的是创建一个自定义的“累加器”，大致如下：

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

调用 , 和返回值的时候会有几个副本accumulate，但是在实际积累的时候，什么都没有。只需调用：

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

（如果你真的关心性能，你可以在 的构造函数中添加一个容量参数Accu，以便它可以reserve对成员字符串执行 a 。如果我这样做了，我可能也会手写复制构造函数，以确保复制对象中的字符串具有所需的容量。）

于 2013-10-29T18:26:19.520 回答