If you don't overallocate the vector then push_back() runs in linear time instead of amortized constant which is generally a worse tradeoff. You can avoid the whole issue by calling reserve() ahead of time, but if you don't know how many elements you're going to have then you're in trouble, but you won't be able to do much better by replacing vector with your own array either.