35

这确实是一个仅出于我自己利益的问题，我无法通过文档确定。

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

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

而 push_back() 具有复杂性：

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

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

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

和

myString.append("foo");

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

4

4 回答 4

46

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

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

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

于 2013-02-26T05:46:53.920 回答
5

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

结果很有趣：

推：19
附加：21
++++:34

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

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

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

注意：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;
}
于 2016-03-06T00:15:09.190 回答
4

在这里再添加一个意见。

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

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

于 2014-08-30T01:24:42.253 回答
0

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

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

于 2013-02-26T05:45:28.583 回答