CODEWITHSUNDEEP
c++performancevector
Gaurav Pant
Gaurav Pant

Reputation: 952

allocating memory using push_back vs constructing vectors of specific size

Found the following statement in C++ Primer

Because vectors grow efficiently, it is often unnecessary—and can result in poorer performance—to define a vector of a specific size. The exception to this rule is if all the elements actually need the same value. If differing element values are needed, it is usually more efficient to define an empty vector and add elements as the values we need become known at run time.

I have this doubt that if you are reserving memory beforehand then there is no need for reallocation (which is considered a slower process). Then how is using push_back leading to better performance ?

Upvotes: 0

Views: 392

Answers (4)

Marko Bencik
Marko Bencik

Reputation: 396

There are few considerations to make.

Do you use one and the same vector often and I do no mean 5 or 10 times but thousand of times. The reason is you want to reuse the object if possible to avoid unnecessary allocations and deallocations. For this you can use clear

Is it possible that the vector will always have a certain number of elements then you can preallocate the elements with thereserve command.

In general if you have a vector as permanent storage that rarely changes the content you should not bother with those things.

Upvotes: 0

songyuanyao
songyuanyao

Reputation: 172964

I think the author is comparing the following two cases:

int n = ...;
std::vector<...> v(n);
for (auto& x : v) x = some_value_known_at_runtime;

and

int n = ...;
std::vector<...> v;
for (int i = 0; i < n; i++) v.push_back(some_value_known_at_runtime);

The 1st case would construct the vector with n default-constructed elements, then assign them later; which might result in poorer performance.

Of cource, you can use reserve in 2nd case, which could avoid reallocation and make it more effcient; if the count of elements could be known in advance.

int n = ...;
std::vector<...> v;
v.reserve(n);
for (int i = 0; i < n; i++) v.push_back(some_value_known_at_runtime);

Upvotes: 5

SreehariGaddam
SreehariGaddam

Reputation: 499

I see this statement in C++ primer and he said that in the following context.

// read words from the standard input and store them as elements in a vector 
string word;
vector<string> text; // empty vector
while (cin >> word) {
    text.push_back(word); // append word to text 
}

Here vector grows unknown size with different values at each time.

Also he is saying "often unnecessary" not "always". I tested it for known number of times and reserve performed better in all the cases.

See the below Vector implementation snippet will give better understanding.

template<typename T> 
class Vector {
    T∗ elem;  // pointer to first element
    T∗ space; // pointer to first unused (and uninitialized) slot 
    T∗ last;  // pointer to last slot
public: 
    // …
    int size();      // number of elements (space-elem)
    int capacity();  // number of slots available for elements (last-elem)
    // ...
    void reserve(int newsz); // increase capacity() to newsz
    // ...
   void push_back(const T& t); // copy t into Vector
};

template<typename T>
void Vector<T>::push_back(const T& t) { 
    if (capacity()<size()+1)            // make sure we have space for t 
        reserve(size()==0?8:2∗size());  // double the capacity 
    new(space){t};                      // initialize *space to t 
    ++space; 
}

Upvotes: 1

Mauricio Cele Lopez Belon
Mauricio Cele Lopez Belon

Reputation: 1507

It depends on the work you do in the default constructor. If your object do something expensive in default constructor, you program can freeze for a while just in the vector allocation. Instead the push_back would call the copy constructor once per each object and incrementally (or just in time). That could be faster.

However, the reallocation and bulk copy might be costly as well, specially if your object is a composite of many objects and so on, so in that case only a profiling can tell what is best.

On the other hand, if the default constructor does nothing, then avoiding the reallocation wouldl win in most cases.

Upvotes: 1

Related Questions