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

Question

这真的是我自己感兴趣的问题，我无法从文档中确定。我在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可能需要每次调用都保证内存。

- Memento Mori

---

除了显而易见的（前者是三个函数调用，后者只有一个），前者可能会导致三次重新分配。个人而言，我更愿意使用 myString += "foo";，因为我认为它更加“自然”，尽管它与 append 调用相同。 - Some programmer dude

尽管很遗憾他们没有说明append的典型情况，只是最坏情况。 - Benjamin Lindley

@JoachimPileborg: push_back 必须是摊销常数时间，因此我所知道的每个实现都有三个分配的可能性为零。大多数从一些合理的大小（大于1或2）开始，并以几何方式增加底层缓冲区（每次大小增加1.5或2倍）。 - Billy ONeal

Answer 1

在C++03标准下（"cplusplus.com"的文档大多数是基于此编写的），复杂性未指定，因为库实现者可以针对字符串执行Copy-On-Write或“rope-style”内部表示。例如，COW实现可能需要复制整个字符串，如果修改一个字符并且存在共享，则会这样做。

在C++11中，禁止使用COW和rope实现。您应该期望每个字符的添加具有常数攒偿时间，或者在将字符附加到字符串结尾时，字符数量具有线性攒偿时间。实现者仍然可以相对于std :: vector等执行相对疯狂的字符串操作，但大多数实现将受到“小字符串优化”等限制。

在比较push_back和append时，push_back会剥夺底层实现潜在有用的长度信息，这些信息可能被用于预分配空间。另一方面，append需要实现两次遍历输入才能找到该长度，因此性能的增益或损失将取决于许多不可知的因素，例如在尝试追加之前字符串的长度。尽管如此，差异可能极其微小。对于这个问题，请使用append -- 它更易读。

- Billy ONeal

---

然而，如果你只想添加一个字符，没有append(char)的重载。这种情况下可以使用push_back()。 - rustyx

你知道C++11/14/17标准是否对字符串的push_back/append/insert复杂度要求进行了加强吗？如果没有，你确定大多数现有的实现都是如此友好吗？（我模糊地记得过去曾遇到过这方面的问题，但也许那只是某些CoW实现的后果。） - Nemo

@Nemo：我不确定你想要什么“收紧”。据我所知，它们一直是摊销常数时间。目前是N4606 23.2.3 [sequence.reqmts] /16 http://eel.is/c++draft/sequence.reqmts#16。 - Billy ONeal

@Nemo：push_back的定义与append完全相同：http://eel.is/c++draft/string::append#24 - Billy ONeal

@Nemo 我认为如果用户和实现者清楚地知道他们需要做什么，那么规范就很好。没有比O(n)的append实现更糟糕的了。等效于可以更快，但通常只是一个常数因子。当比较n个O(1)摊销push_back调用与1个O(n)附加调用时，唯一的答案是进行性能分析。 - Billy ONeal

Answer 2

我有同样的疑问，所以我进行了一个小测试来检查这个问题（在Linux、Intel、64位下使用带有C++11配置文件的g++ 4.8.5，在VmWare Fusion下）。

结果很有趣：

push ：19
append ：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;
}

- user2583872

Answer 3

在此再提出一个观点。

我个人认为，当从另一个字符串逐个添加字符时，最好使用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()，我将用append(1, it)替换push_back(it)，但对我来说这不太易读。

- user2558887

Answer 4

是的，我也希望append()能够更好地执行你所提到的原因，在需要附加字符串的情况下，使用append()（或operator+=）肯定是更可取的选择（最重要的是代码更易读）。

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

- jogojapan

---

需要复制追加字符串的每个字符。如果底层内存块无需调整大小，则不需要复制字符串的现有内容。 - Billy ONeal