Vector <vector <largeObject>> vs. vector <vector <largeObject> *> in C ++

Question

Obviously, this will depend on the compiler you use, but I'm curious about performance issues when doing vector<vector<largeObject>> vs. vector<vector<largeObject>*> , especially in C ++. In particular:

let's say you have a full vector vector and you want to start inserting elements into the first inner vector. How it will be stored in memory if the external vector simply stores pointers, as provided for the storage of the entire internal vector. Will the entire external vector be moved to get more space, or will the internal vector be moved (assuming that the space has not been previously allocated), causing problems with the external vector?

thanks

Answer 1

A vector is internally a pointer, so a vector pointer is kind of redundant.

A vector of pointers or smart pointers is commonly used when polymorphic content is required.

In C ++ 03, it can be expensive to insert more vectors or (erase existing) your main vector, but C ++ 0x even solves this problem with move semantics.

It is better to switch to more suitable containers later after profiling with real data, rather than trying to make it extremely dynamic from the very beginning.

Answer 2

My first question is: "Why are you using nested vectors?" If you don't need the dimensions of a “2D array” that can be serrated, you can use the same vector and canonical 2D indexing in a 1D array (x + width * y).

However, since the vector copies T-instances around when resized, etc., the vector of pointers to large objects is likely to be less expensive because the copies will be smaller (copying the pointer compared to the "large object"). The downside is that you have to manage the distribution of large objects yourself, but something like boost shared_ptr may help (or the standard version if you have 0x support but not auto_ptr). The "large object" here can be anything, including nested vectors or pointers to a vector, as in your original example, if necessary.

EDIT: you can also use reserve () to preallocate space in a vector, which prevents a lot of copying if you can make guarantees about the number of things you are going to insert into the vector.

Answer 3

I think that in your case there will not be much difference in performance. This is just a matter of when you want to spend time creating objects.

Several times it is better to use vector<vector<BigObject*>>

Answer 4

The answer with performance questions is always: a performance test or profile.

Also consider alternatives:

 vector< vector< LargeObject* > >, 

or

 vector< vector< shared_ptr<LargeObject> > > 

What works best will depend on the operations you perform:

• Lots of designs / demolitions
• Copies - Can they be optimized to use vector :: swap ()?
• Are you deleting elements from the middle of the vector?

Do you want to manage manual memory management? If the answer is no, stick with a vector> until a performance problem is demonstrated.

To protect yourself from having to change too much code for performance reasons later on, you can / should encapsulate a 2D array into a class.