Wie ist die Komplexität der Operation push_back bei std::vector?

Im Durchschnitt ist die Amortisierung O(1).

Im schlimmsten Fall O(N), wobei N die aktuelle Größe des Vektors ist. Dies tritt bei der Speicherneuzuordnung auf, wenn die aktuelle Kapazität des Vektors für ein neues Element nicht ausreicht. Dabei wird ein neuer Puffer mit größerer Kapazität erstellt, die Elemente werden dorthin kopiert, und der alte Puffer wird freigegeben.