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

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

Answer 1

在C++ 03中(大多数"cplusplus.com"的文档都是编写的),复杂性未被指定,因为允许库实现者对字符串进行Copy-On-Write或"rope-style"内部表示.例如,如果修改了一个字符并且正在进行共享,则COW实现可能需要复制整个字符串.

在C++ 11中,禁止COW和绳索实现.您应该期望每个字符添加的常量摊销时间或线性摊销时间在添加到最后添加到字符串的字符数中.实施者仍然可以用字符串做相对疯狂的事情(比如说,比较而言std::vector),但大多数实现都将局限于"小字符串优化"之类的东西.

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

Answer 2

我也有同样的疑问，所以我做了一个小测试来检查这个（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;
}