C++ 11 std::vector push_back method calls copy/dest so many times?

Question

I am currently optimising my code and I have a question regarding the std::vector

I have a class MyClass which I have rewritten the copy/move constructor and their corresponding operators.

MyClass(const std::string& id, int x);
MyClass(const MyClass& other);
MyClass(MyClass&& other);
~MyClass();
MyClass& operator=(const MyClass& other);
MyClass& opratror*(MyClass&& other);

I created a vector and tried the following

std::vector<MyClass> vec;
MyClass a("A", 1);
vec.push_back(a);    //#1
vec.emplace_back("B", 2);    //#2
vec.push_back(MyClass("C", 3));    //#3

in #1 the copy constructor is called (which I know vector store by values so it copies a) in #2 it saves a copy constructor call only calls the constructor in #3 it calls the constructor and move constructor

But what I found is that, at #2, #3 where the vector is not empty, every push back / emplace / emplace_back triggers the copy/destroy of existing items.

in #2, it copies "A" and destroyed the existing "A" in #3, it does the same to "A" and "B"

it seems the vector resorts all the items whenever the array changes. Does it mean that using a class vector could make things inefficient? Is that the best solution to use a vector storing pointers so that there's not copies / destructors calls during resorting, only pointer copying?

Thanks

Are you running an optimized build, or a "debug", unoptimized build? What compiler options did you use to build the code? — PaulMcKenzie
A vector will make copies when it has to reallocate its internal storage, which should happen less often as it gets bigger. How big did you let it go before you reached your conclusion? — Mark Ransom
Thanks everyone. I got the points! I think I need to study the STL more precisely. — Charles

Sam Varshavchik Sam Varshavchik · Accepted Answer · 2018-12-26T03:12:09

Not resorts, but reallocates. A vector is required, by contract, to store its values contiguously, like a plain array. The only way to guarantee contiguous storage is to allocate one chunk of memory. Once you got it, you're done. You can't make it bigger. All you can do is allocate a larger chunk and copy everything over and then delete the older smaller block of memory. That's what you're seeing.

A vector typically reserves some additional extra space, to accomodate new elements that might get added (so that this copying doesn't happen with every push_back), but when the vector is small, initially, only a little bit of extra space gets reserved for future growth, and this reallocation still happens quite often. But as the vector grows in size, more and more extra space gets reserved, and the reallocation happens less often.

If you know in advance how much values you are going to push_back(), you can use reserve() up front to preallocate the additional space up front, and minimize the reallocation.

If you know you're going to add ten more values to the vector:

vec.reserve(vec.size()+10);

If the vector already has at least ten more values it can accept without reallocating, then this does nothing. Otherwise the vector gets reallocated with enough extra space for at least ten additional values. The next ten push_backs are guaranteed not to cause reallocation.

C++ 11 std::vector push_back method calls copy/dest so many times?

2 Answers