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.

Stephane Rolland · Answer 1 · 2011-09-19T14:46:22.917

6

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

STL diagram for choosing containers

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.

edited Sep 19 '11 at 14:46

answered Sep 19 '11 at 12:58

Stephane Rolland

38,876
35
121
169

Where did you get this diagram? I'd love to have a big original size of it on my wall. – datalost Sep 19 '11 at 13:00
1

this one comes from http://i.stack.imgur.com/d5CDK.png... if you do a google search for stl or std containers choice, you should find images alike. – Stephane Rolland Sep 19 '11 at 13:02
1

This diagram looks wrong to me. If you answer "yes" to "insert/erase at front", then you are asked whether you need to merge collections, but not whether you need to find the nth element. If the answer to both questions would be "yes", then the choice between `deque` and `list` should depend on the relative frequency*cost of those two operations. This diagram will have you using `list` in some cases where `deque` would be a factor of `n` faster overall because you do a lot of finding-the-nth-element. – Steve Jessop Sep 19 '11 at 13:07
@Steve: I admit I don't really know the implementations behind of std::deque and std::list... But I keep your remark in mind. – Stephane Rolland Sep 19 '11 at 14:39
@sehe: I edit and add the source you mentionned... and it was also in an old answer from mines :-) [inserting into a vector at the front] [1]: http://stackoverflow.com/questions/4226606/inserting-into-a-vector-at-the-front/4226656#4226656 – Stephane Rolland Sep 19 '11 at 14:40

score 3 · Accepted Answer · answered Sep 19 '11 at 12:56

3

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.

answered Sep 19 '11 at 12:56

sehe

374,641
47
450
633

Alright, lets say im working with structs, and I have a vector of a struct. If I wanted to add an item, id have to create the struct first, and then push it back with push_back? If I had an array, I could just assign items to the array. Does this make the array faster or no? – Josh Sep 19 '11 at 13:17
@Josh: You could resize the vector, and write to the newly created room. That is fully equivalent to the C approach. Now, with C++11 you can have your cake and eat it, because the push_back results in exactly the same semantics using move construction/assignment. Move constructors/assignment operators will normally be auto-generated for your pod types. ([background](http://en.wikipedia.org/wiki/C%2B%2B11#Rvalue_references_and_move_constructors)) – sehe Sep 19 '11 at 13:21
@sehe: C++11 also has `emplace_back`, which is even more exciting than move construction. – Steve Jessop Sep 19 '11 at 14:32

score 2 · Answer 3 · answered Sep 19 '11 at 12:58

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 vector should be the winner in this case, because it doesn't realloc every time[vector guarantees O(1) amortized insert time]. However, it might be similar if your malloc implementation is optimized for this kind of usage.

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

These should be the same, particularly because vector::iterator are usually just pointers into an array or thin wrappers thereof.

score 1 · Answer 4 · answered Sep 19 '11 at 12:54

There is no difference in speed, but vector is massively safer. This is because the functions will just be inlined by your compiler, but vector carries a large number of exception and bounds-checking (if you ask for it) gurarantees that you won't see when using your own raw arrays.

C++ Container performance question

4 Answers4

Linked