Jaká je složitost operace push_back u std::vector?

Průměrně je amortizace O(1).

V nejhorším případě O(N), kde N je aktuální velikost vektoru. To se stává při přerozdělení paměti, když aktuální kapacita vektoru nestačí pro nový prvek. V takovém případě se vytvoří nový buffer větší kapacity, prvky se do něj zkopírují a starý buffer se uvolní.