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

Question

To naprawdę jest pytanie tylko dla mojego własnego interesu, którego nie udało mi się ustalić za pomocą dokumentacji.

widzę na http://www.cplusplus.com/reference/string/string/ że dołączy ma złożoność „Nieokreślony, ale ogólnie do liniowy w nowej długości łańcucha”

podczas push_back() ma złożoność:

„nieokreślony; Generalnie amortyzuje stała, ale do liniowy w nowej długości strun.”

Jako przykład zabawny, przypuśćmy, że chcę dołączyć znaki "foo" do ciągu znaków. Czy

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

i

myString.append("foo"); 

wynoszą dokładnie to samo? Czy jest jakaś różnica? Można uznać, że ten dodatek byłby bardziej wydajny, ponieważ kompilator wiedziałby, ile pamięci jest wymagane do rozszerzenia ciągu znaków o określoną liczbę znaków, podczas gdy funkcja push_back może potrzebować zabezpieczyć pamięć każdego wywołania?

Answer 1

W C++ 03 (dla której napisano większość dokumentacji "cplusplus.com"), złożoności były nieokreślone, ponieważ realizatorzy bibliotek mogli wykonywać kopie na piśmie lub reprezentacje wewnętrzne w stylu "liny" na struny. Na przykład implementacja COW może wymagać skopiowania całego ciągu znaków, jeśli modyfikowana jest postać i odbywa się udostępnianie.

W C++ 11, COW i implementacje lin są zbanowane. Powinieneś oczekiwać stałego zamortyzowanego czasu na każdy dodany znak lub liniowy czas amortyzacji liczby znaków dodawanych do dodania do ciągu na końcu. Realizatorzy mogą nadal robić względnie szalone rzeczy za pomocą łańcuchów (w porównaniu do, powiedzmy std::vector), ale większość implementacji będzie ograniczona do takich rzeczy jak "optymalizacja małych napisów".

Porównanie push_back i append, push_back pozbawia podstawową realizację potencjalnie użytecznych informacji o długości, które może wykorzystać do wstępnego przydzielenia przestrzeni. Z drugiej strony, append wymaga, aby implementacja przechodziła przez wejście dwukrotnie w celu znalezienia tej długości, więc wzrost lub strata wydajności będzie zależeć od wielu niepoznawalnych czynników, takich jak długość łańcucha przed próbą dołączenia . Powiedział, że różnica jest prawdopodobnie bardzo ekstremalnie bardzo mała. Idź za to z append - jest znacznie bardziej czytelny.

Answer 2

Tak, ja też oczekiwać append() wykonać lepiej ze względów dałeś, a także w sytuacji, gdy trzeba dołączyć ciąg, używając append() (lub operator+=) jest z pewnością korzystne (nie mniej ważne również dlatego, że kod jest znacznie bardziej czytelny).

Ale to, co Standard określa, to złożoność operacji. I to jest ogólnie liniowe nawet dla append(), ponieważ ostatecznie każdy znak dołączanego ciągu (i możliwe wszystkie znaki, jeśli nastąpi realokacja) musi być skopiowany (jest to prawdą, nawet jeśli używane są memcpy lub podobne).

Answer 3

Dodaj jeszcze jedną opinię tutaj.

Osobiście uważam, że lepiej jest używać push_back() podczas dodawania znaków jeden po drugim z innego ciągu. Na przykład:

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

przypadku korzystania append() tutaj, chciałbym wymienić push_back(it) z append(1,it), który nie jest czytelny dla mnie.

Answer 4

Miałem takie same wątpliwości, więc zrobiłem mały test, aby to sprawdzić (g ++ 4.8.5 z profilem C++ 11 na Linux, Intel, 64 bit pod VmWare Fusion).

a wynik jest interesujący:

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

Czy możliwe jest to ze względu na długość łańcucha (duży), ale operator + jest bardzo drogie w porównaniu z push_back i dopisywania.

Co ciekawe, gdy operator otrzymuje tylko znak (nie ciąg), zachowuje się bardzo podobnie do funkcji push_back.

Aby nie zależało od wcześniej przydzielonych zmiennych, każdy cykl jest zdefiniowany w innym zakresie.

Uwaga: vCounter po prostu używa gettimeofday w celu porównania różnic.

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