Avoid making copies with vectors of vectors

Question

I want to be able to have a vector of vectors of some type such as:

vector<vector<MyStruct> > vecOfVec;

I then create a vector of MyStruct, and populate it.

vector<MyStruct> someStructs;
// Populate it with data

Then finally add someStructs to vecOfVec;

vecOfVec.push_back(someStructs);

What I want to do is avoid having the copy constructor calls when pushing the vector. I know this can be accomplished by using a vector of pointers, but I'd like to avoid that if possible.

One strategy I've thought of seems to work, but I don't know if I'm over-engineering this problem.

// Push back an empty vector
vecOfVec.push_back(vector<MyStruct>());

// Swap the empty with the filled vector (constant time)
vecOfVec.back().swap(someStructs);

This seems like it would add my vector without having to do any copies, but this seems like something a compiler would already be doing during optimization.

Do you think this is a good strategy?

Edit: Simplified my swap statement due to some suggestions.

Answer 1

The swap trick is as good as it gets with C++03. In C++0x, you'll be able to use the vector's move constructor via std::move to achieve the same thing in a more obvious way.

Another option is to not create a separate vector<MyStruct>, but instead have the code that creates it accept it a a vector<MyStruct>& argument, and operate on it. Then, you add a new empty element to your outer vector<vector<MyStruct>>, and pass a reference to the code that will fill it.

Answer 2

You can either do something like vect.push_back(vector<MyStruct>()); and do vect.back().push_back(MyStruct()); or use smart pointers and have a vector of smart pointers to vector<MyStruct>

Answer 3

I know this can be accomplished by using a vector of pointers, but I'd like to avoid that if possible.

Why?

That would be the most intuitive/readable/maintainable solution and would be much better than any weird hacks anyone comes up with (such as the swap you show).

Answer 4

I think the swap idea is already fine, but can be written much easier:

vecOfVec.push_back(vector<MyStruct>());
vecOfVec.back().swap(someStructs);

Answer 5

Tim,

There's a common pattern to solve this. This is called smart pointers, and the best one to use is boost::shared_ptr.

Then, never pass vector by value or store it. Instead, store boost::shared_ptr >. You don't need to care about allocations/deallocations (when the containing vector is destroyed, so will be the others, just as in your code), and you can access the inner members almost the same way. The copy is, however, avoided by means of the smart pointer object's reference counting mechanism.

Let me show you how.

using boost::shared_ptr;
vector<shared_ptr<vector<MyStruct> > vecOfVecs;
shared_ptr<vector<MyStruct> > someStructs(new vector<MyStruct>);
// fill in the vector MyStructs
MyStructs->push_back(some struct.... as you usually do).  
//...
vecOfVecs.push_back(someStructs); // Look! No copy!

If you do not already use boost::shared_ptr, I recommend downloading it from boost.org rather than implementing your own. It is really irreplaceable tool, soon to be in the C++ standard library.