c++ - library - std:: string insert

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

Question

Esta es realmente una pregunta que, por mi propio interés, no he podido determinar a través de la documentación.

Veo en http://www.cplusplus.com/reference/string/string/ que el apéndice tiene complejidad:

"Sin especificar, pero generalmente hasta lineal en la nueva longitud de la cadena".

mientras que push_back () tiene complejidad:

"Sin especificar; Generalmente, la amortización es constante, pero hasta lineal en la nueva longitud de la cadena".

Como ejemplo de juguete, supongamos que quisiera agregar los caracteres "foo" a una cuerda. haría

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

y

myString.append("foo");

¿Es exactamente lo mismo? ¿O hay alguna diferencia? Podría imaginar que la adición sería más eficiente porque el compilador sabría cuánta memoria se requiere para extender la cadena el número especificado de caracteres, mientras que push_back necesita asegurar la memoria en cada llamada.

Answer 1

Añade una opinión más aquí.

Personalmente, considero que es mejor usar push_back() al agregar caracteres uno por uno desde otra cadena. Por ejemplo:

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

Si utilizara append() aquí, reemplazaría push_back(it) por append(1,it) , que no es tan legible para mí.

Answer 2

En C ++ 03 (para la cual está escrita la mayor parte de la documentación de "cplusplus.com"), las complejidades no se especificaron porque los implementadores de bibliotecas podían realizar representaciones internas de Copia en escritura o "estilo cuerda" para las cadenas. Por ejemplo, una implementación de COW puede requerir copiar la cadena completa si se modifica un carácter y se está compartiendo.

En C ++ 11, las implementaciones de cable y cuerda están prohibidas. Debe esperar un tiempo amortizado constante por carácter agregado o un tiempo amortizado lineal en la cantidad de caracteres agregados para agregar a una cadena al final. Los implementadores aún pueden hacer cosas relativamente locas con cadenas (en comparación con, digamos std::vector ), pero la mayoría de las implementaciones se limitarán a cosas como la "optimización de cadena pequeña".

Al comparar push_back y append , push_back priva a la implementación subyacente de información de longitud potencialmente útil que podría usar para preasignar espacio. Por otro lado, el append requiere que una implementación recorra la entrada dos veces para encontrar esa longitud, por lo que la ganancia o pérdida de rendimiento dependerá de una cantidad de factores desconocidos, como la longitud de la cadena antes de intentar el apéndice. . Dicho esto, la diferencia es probablemente extremadamente extremadamente EXTREMADAMENTE pequeña. Ir con append para esto - es mucho más legible.

Answer 3

Sí, también esperaría que append() desempeñe mejor por las razones que proporcionó, y en una situación en la que necesita agregar una cadena, es preferible usar append() (u operator+= ) (no solo porque el código es mucho más legible).

Pero lo que el Estándar especifica es la complejidad de la operación. Y eso es generalmente lineal incluso para append() , porque en última instancia, cada carácter de la cadena que se agrega (y posiblemente todos los caracteres, si se produce una reasignación) debe copiarse (esto es cierto incluso si se usa memcpy o similar).

Answer 4

Tenía la misma duda, así que hice una pequeña prueba para verificar esto (g ++ 4.8.5 con perfil de C ++ 11 en Linux, Intel, 64 bits bajo VmWare Fusion).

Y el resultado es interesante:

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

Podría ser posible esto se debe a la longitud de la cadena (grande), pero el operador + es muy caro en comparación con el push_back y el apéndice.

También es interesante que cuando el operador solo recibe un carácter (no una cadena), se comporta de forma muy similar al push_back.

Para no depender de variables asignadas previamente, cada ciclo se define en un ámbito diferente.

Nota: el vCounter simplemente usa gettimeofday para comparar las diferencias.

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