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

Это действительно вопрос только для моих собственных интересов, которые я не смог определить в документации.

Я вижу на http://www.cplusplus.com/reference/string/string/, что append имеет сложность:

"Unspecified, но обычно до линейной длины новой строки."

в то время как push_back() имеет сложность:

"Unspecified: обычно амортизируется константа, но до линейной длины новой строки".

В качестве примера игрушек предположим, что я хотел добавить символы "foo" в строку. Будет ли

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

myString.append("foo");

составляет ровно одно и то же? Или есть какая-то разница? Вы могли бы подумать, что добавление будет более эффективным, потому что компилятор будет знать, сколько памяти требуется для расширения строки указанным количеством символов, а push_back может потребоваться защитить память каждого вызова?

Ответ 1

В С++ 03 (для которого написана большая часть документации "cplusplus.com" ), сложности были неуказаны, потому что разработчикам библиотек было разрешено выполнять операции "Copy-On-Write" или "внутренние стили" для строк. Например, реализация COW может потребовать копирования всей строки, если символ изменен и происходит совместное использование.

В С++ 11 запрещены реализации COW и rope. Вы должны ожидать, что постоянное амортизированное время на добавленный символ или линейное амортизированное время в количестве символов, добавленных для добавления к строке в конце. Разработчики могут по-прежнему делать относительно сумасшедшие вещи со строками (по сравнению с, скажем, std::vector), но большинство реализаций будут ограничены такими вещами, как "оптимизация небольших строк".

При сравнении push_back и append, push_back лишает основную реализацию потенциально полезной информации длины, которую он может использовать для предварительного распределения пространства. С другой стороны, append требует, чтобы реализация дважды проходила по вводу, чтобы найти эту длину, поэтому усиление или потеря производительности будет зависеть от ряда непознаваемых факторов, таких как длина строки, прежде чем вы попытаетесь добавьте. Тем не менее, разница, вероятно, чрезвычайно Чрезвычайно мала. Пойдите с append для этого - это более читаемо.

Ответ 2

Добавьте еще одно мнение.

Я лично считаю, что лучше использовать 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), что не является для меня доступным.

Ответ 3

У меня было такое же сомнение, поэтому я сделал небольшой тест, чтобы проверить это (g++ 4.8.5 с профилем С++ 11 в Linux, Intel, 64 бит под VmWare Fusion).

И результат интересен:

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

Возможно, это связано с длиной строки (большой), но оператор + очень дорог по сравнению с push_back и добавлением.

Также интересно, что когда оператор получает только символ (а не строку), он ведет себя очень похоже на 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;
}

Ответ 4

Да, я также ожидал бы, что append() будет работать лучше по причинам, которые вы дали, и в ситуации, когда вам нужно добавить строку, использование append() (или operator+=), безусловно, предпочтительнее (не в последнюю очередь также потому что код гораздо читабельнее).

Но то, что указывает стандарт, это сложность операции. И это обычно линейно даже для append(), потому что в конечном итоге каждый символ добавляемой строки (и, возможно, все символы, если происходит перераспределение) необходимо скопировать (это верно, даже если используются memcpy или аналогичные).