C++ std::string append vs push_back()

C++ std::string append vs push_back()

提问by Memento Mori

This really is a question just for my own interest I haven't been able to determine through the documentation.

这确实只是为了我自己的兴趣而无法通过文档确定的问题。

I see on http://www.cplusplus.com/reference/string/string/that append has complexity:

我在http://www.cplusplus.com/reference/string/string/ 上看到 append 具有复杂性：

"Unspecified, but generally up to linear in the new string length."

“未指定，但通常在新的字符串长度中达到线性。”

while push_back() has complexity:

而 push_back() 具有复杂性：

"Unspecified; Generally amortized constant, but up to linear in the new string length."

“未指定；通常摊销常数，但在新字符串长度中最多为线性。”

As a toy example, suppose I wanted to append the characters "foo" to a string. Would

作为一个玩具示例，假设我想将字符“foo”附加到字符串中。将

myString.push_back('f');
myString.push_back('o');
myString.push_back('o');

and

和

myString.append("foo");

amount to exactly the same thing? Or is there any difference? You might figure that append would be more efficient because the compiler would know how much memory is required to extend the string the specified number of characters, while push_back may need to secure memory each call?

完全一样吗？或者有什么区别？您可能认为 append 会更有效，因为编译器会知道将字符串扩展到指定数量的字符需要多少内存，而 push_back 可能需要在每次调用时保护内存？

回答by Billy ONeal

In C++03 (for which most of "cplusplus.com"'s documentation is written), the complexities were unspecified because library implementers were allowed to do Copy-On-Write or "rope-style" internal representations for strings. For instance, a COW implementation might require copying the entire string if a character is modified and there is sharing going on.

在 C++03 中（“cplusplus.com”的大部分文档都是为此编写的），复杂性未指定，因为库实现者被允许对字符串进行 Copy-On-Write 或“绳索式”内部表示。例如，如果一个字符被修改并且正在进行共享，则 COW 实现可能需要复制整个字符串。

In C++11, COW and rope implementations are banned. You should expect constant amortized time per character added or linear amortized time in the number of characters added for appending to a string at the end. Implementers may still do relatively crazy things with strings (in comparison to, say std::vector), but most implementations are going to be limited to things like the "small string optimization".

在 C++11 中，禁止使用 COW 和绳索实现。您应该期望添加的每个字符的固定摊销时间或添加到字符串末尾的字符数的线性摊销时间。实现者可能仍然会用字符串做相对疯狂的事情（相比而言，比如std::vector），但大多数实现将仅限于诸如“小字符串优化”之类的事情。

In comparing push_backand append, push_backdeprives the underlying implementation of potentially useful length information which it might use to preallocate space. On the other hand, appendrequires that an implementation walk over the input twice in order to find that length, so the performance gain or loss is going to depend on a number of unknowable factors such as the length of the string before you attempt the append. That said, the difference is probably extremely Extremely EXTREMELY small. Go with appendfor this -- it is far more readable.

在比较push_back和 时append，push_back剥夺了潜在有用的长度信息的底层实现，这些信息可能用于预分配空间。另一方面，append要求实现遍历输入两次才能找到该长度，因此性能增益或损失将取决于许多不可知的因素，例如在尝试追加之前字符串的长度。也就是说，差异可能非常非常非常小。去append了这一点-它是更具可读性。

回答by user2583872

I had the same doubt, so I made a small test to check this (g++ 4.8.5 with C++11 profile on Linux, Intel, 64 bit under VmWare Fusion).

我也有同样的疑问，所以我做了一个小测试来检查这个（g++ 4.8.5 with C++11 profile on Linux, Intel, 64 bit under VmWare Fusion）。

And the result is interesting:

结果很有趣：

push :19
append :21
++++ :34

Could be possible this is because of the string length (big), but the operator + is very expensive compared with the push_back and the append.

这可能是因为字符串长度（大），但与 push_back 和 append 相比，运算符 + 非常昂贵。

Also it is interesting that when the operator only receives a character (not a string), it behaves very similar to the push_back.

同样有趣的是，当操作符只接收一个字符（不是字符串）时，它的行为与 push_back 非常相似。

For not to depend on pre-allocated variables, each cycle is defined in a different scope.

为了不依赖于预先分配的变量，每个循环都定义在不同的范围内。

Note : the vCounter simply uses gettimeofday to compare the differences.

注意：vCounter 只是使用 gettimeofday 来比较差异。

TimeCounter vCounter;

{
    string vTest;

    vCounter.start();
    for (int vIdx=0;vIdx<1000000;vIdx++) {
        vTest.push_back('a');
        vTest.push_back('b');
        vTest.push_back('c');
    }
    vCounter.stop();
    cout << "push :" << vCounter.elapsed() << endl;
}

{
    string vTest;

    vCounter.start();
    for (int vIdx=0;vIdx<1000000;vIdx++) {
        vTest.append("abc");
    }
    vCounter.stop();
    cout << "append :" << vCounter.elapsed() << endl;
}

{
    string vTest;

    vCounter.start();
    for (int vIdx=0;vIdx<1000000;vIdx++) {
        vTest += 'a';
        vTest += 'b';
        vTest += 'c';
    }
    vCounter.stop();
    cout << "++++ :" << vCounter.elapsed() << endl;
}

回答by Spectral

Add one more opinion here.

在这里再添加一个意见。

I personally consider it better to use push_back()when adding characters one by one from another string. For instance:

我个人认为push_back()在从另一个字符串一个一个地添加字符时使用会更好。例如：

string FilterAlpha(const string& s) {
  string new_s;
  for (auto& it: s) {
    if (isalpha(it)) new_s.push_back(it);
  }
  return new_s;
}

If using append()here, I would replace push_back(it)with append(1,it), which is not that readable to me.

如果append()在这里使用，我将替换push_back(it)为append(1,it)，这对我来说不是那么可读。

回答by jogojapan

Yes, I would also expect append()to perform better for the reasons you gave, and in a situation where you need to append a string, using append()(or operator+=) is certainly preferable (not least also because the code is much more readable).

是的，我也希望append()由于您给出的原因而表现得更好，并且在您需要附加字符串的情况下，使用append()(or operator+=) 当然更可取（尤其是因为代码更具可读性）。

But what the Standard specifies is the complexity of the operation. And that is generally linear even for append(), because ultimately each character of the string being appended (and possible all characters, if reallocation occurs) needs to be copied (this is true even if memcpyor similar are used).

但标准规定的是操作的复杂性。即使对于append()，这通常也是线性的，因为最终被附加的字符串的每个字符（以及可能的所有字符，如果发生重新分配）都需要复制（即使使用memcpy或类似的也是如此）。