C++ Container performance question

Question

What would have better performance, a stl vector, or a dynamic array that's just realloc'd everytime I want to add something to it?

Would using vectors::iterator be faster then using a for loop on an array?

And if someone could explain why, that would be great.

Answer 1

Premature optimization is evil. The standard C++ way of doing things is to use the standard library containers as much as possible. If you want to use the best containers fitting your needs: here is the diagram

source: Original Image by Jameson Williams

One day you will maybe need to heavily optimize and use a dynamic array, but it should be rare.... one day you will also need collection that are multi-thread safe... and so on... but in general std containers are the way to go.

Answer 2

What would have better performance, a stl vector, or a dynamic array that's just realloc'd everytime I want to add something to it?

Stl vectors have insertion in amortized constant time (because reallocation is not done all the time and reservations occur by factor 1.5 (minimum)).

Therefore according to your description, vectors will be massively faster than reallocating all the time

Would using vectors::iterator be faster then using a for loop on an array?

In the general case: exactly identical. However certain STL implementations generate checks in debug mode that can considerably slow down the use of container iterators.

(note most implementations implement vector/string iterators as a typedef to value_type*)

And if someone could explain why, that would be great.