resize versus push_back in std::vector : does it avoid an unnecessary copy assignment?

Question

When invoking the method push_back from std::vector, its size is incremented by one, implying in the creation of a new instance, and then the parameter you pass will be copied into this recently created element, right? Example:

myVector.push_back(MyVectorElement());

Well then, if I want to increase the size of the vector with an element simply using its default values, wouldn't it be better to use the resize method instead? I mean like this:

myVector.resize(myVector.size() + 1);

As far as I can see, this would accomplish exactly the same thing but would avoid the totally unnecessary assignment copy of the attributes of the element.

Is this reasoning correct or am I missing something?

Answer 1

When you do push_back() the method checks the underlying storage area to see if space is needed. If space is needed then it will allocate a new contiguous area for all elements and copy the data to the new area.

BUT: The size of the newly allocated space is not just one element bigger. It uses a nifty little algorithm for increasing space (I don't think the algorithm is defined as part of the standard but it usually doubles the allocated space). Thus if you push a large number of elements only a small percentage of them actually cause the underlying space to be re-allocated.

To actually increase the allocate space manually you have two options:

• reserve()

  This increases the underlying storage space without adding elements to the vector. Thus making it less likely that future push_back() calls will require the need to increase the space.

• resize()

  This actually adds/removes elements to the vector to make it the correct size.

• capacity()

  Is the total number of elements that can be stored before the underlying storage needs to be re-allocated. Thus if capacity() > size() a push_back will not cause the vector storage to be reallocated.

Answer 2

At least with GCC, it doesn't matter which you use (Results below). However, if you get to the point where you are having to worry about it, you should be using pointers or (even better) some form of smart pointers.. I would of course recommend the ones in the boost library.

If you wanted to know which was better to use in practice, I would suggest either push_back or reserve as resize will resize the vector every time it is called unless it is the same size as the requested size. push_back and reserve will only resize the vector if needed. This is a good thing as if you want to resize the vector to size+1, it may already be at size+20, so calling resize would not provide any benefit.

Test Code

#include <iostream>
#include <vector>

class Elem{
    public:
        Elem(){
            std::cout << "Construct\n";
        }
        Elem(const Elem& e){
            std::cout << "Copy\n";
        }
        ~Elem(){
            std::cout << "Destruct\n";
        }   
};


int main(int argc, char* argv[]){
    {
        std::cout << "1\n";
        std::vector<Elem> v;
        v.push_back(Elem());
    }

    {
        std::cout << "\n2\n";
        std::vector<Elem> v;
        v.resize(v.size()+1);
    }
}

Test Output

1
Construct
Copy
Destruct
Destruct

2
Construct
Copy
Destruct
Destruct

Answer 3

A c++0x perspective concerning test code of Yacobi's accepted answer:

1. Add a move constructor to the class:

   Elem(Elem&& e) { std::cout << "Move\n"; }
   

   With gcc I get "Move" instead of "Copy" as output for push_back, which is far more efficient in general.

2. Even slightly better with emplace operations (take the same arguments as the constructor):

   v.emplace_back()

Test Output:

1
Construct
Destruct

2
Construct
Copy
Destruct
Destruct

Answer 4

Obviously you're worried about efficiency and performance.

std::vector is actually a very good performer. Use the reserve method to preallocate space if you know roughly how big it might get. Obviously this is at the expense of potentially wasted memory, but it can have quite a performance impact if you're using push_back a lot.

I believe it's implementation dependent as to how much memory is reserved up front for a vector if any at all, or how much is reserved for future use as elements are added. Worst case scenario is what you're stating - only growing by one element at a time.

Try some performance testing in your app by comparing without the reserve and with it.

Answer 5

At EA (Electronic Arts) this was considered such a big problem that they wrote their own version of the STL, EASTL, which among many other things include a push_back(void) in their vector class.

Answer 6

When you call push_back, assuming that no resizing of the underlying storage is needed, the vector class will use the "placement new" operator to copy-construct the new elements in-place. The elements in the vector will not be default-constructed before being copy-constructed.

When you call resize, almost the exact same sequence occurs. vector allocates storage and then copies the default value via placement new into each new location.

The construction looks like this:

::new (p) _T1(_Val);

Where p is the pointer to the vector storage, _T1 is the type being stored in the vector, and _Val is the "default value" parameter (which defaults to _T1()).

In short, resize and push_back do the same things under the covers, and the speed difference would be due to multiple internal allocations, multiple array bounds checks and function call overhead. The time and memory complexity would be the same.

Answer 7

I find myVector.push_back(MyVectorElement()); much more direct and easier to read.

The thing is, resize doesn't just resize the array and default-construct elements on those places; that's just what it defaults to. It actually takes a second parameter which is what each new element will be made a copy of, and this defaults to T(). In essence, your two code samples are exactly the same.

Answer 8

You are right that push_back cannot avoid at least one copy but I think that you are worrying about the wrong things, but resize will not necessarily perform any better either (it copies the value of its second parameter which defaults to a default constructed temporary anyway).

vector is not the right container for objects which are expensive to copy. (Almost) any push_back or resize could potentially cause every current member of the vector to be copied as well as any new member.

Answer 9

I suspect the actual answer is strongly a function of the STL implementation and compiler used, however, the "resize" function has the prototype (ref)

void resize( size_type num, TYPE val = TYPE() );

which implies val is default constructed, and copied into the newly allocated (or possibly previously allocated but unused) space via placement new and the copy-constructor. As such both operations require the same sequence of actions:

1. Call default constructor
2. Allocate space
3. Initialise via a copy constructor

It's probably better to defer to the clearer and more generic (in terms of STL containers) push_back, rather than apply premature optimisation - if a profiler is highlighting a push_back as a hotspot then the most likely cause is the memory allocation which is best resolved through judicious use of reserve.

Answer 10

push_back: you create the object and it gets copied in the vector.
resize: the vector creates the object with the default constructor and copies it in the vector.

Speed difference: You will have to test your implementation of the STL and your compiler, but I think it won't matter.

Answer 11

myVector.resize(myVector.size() + 1);

will call an empty constructor of MyVectorElement. What are you trying to accomplish? In order to reserve space in a vector (and save memory allocation overhead) there's reserve() method. You cannot avoid the constructor.