Does declaring a vector with size offer any improvements over using push_back in C++

Question

Let us say we know the size of a vector we will be needing, (say 'n').

Does using vector<int> Array(n); offer any improvements over using Array.push_back(element) one by one?

Which is recommended and why?

Answer 1

Below is a reference taken from Cplusplus.com :

Internally, vectors use a dynamically allocated array to store their elements. This array may need to be reallocated in order to grow in size when new elements are inserted, which implies allocating a new array and moving all elements to it. This is a relatively expensive task in terms of processing time, and thus, vectors do not reallocate each time an element is added to the container.

Instead, vector containers may allocate some extra storage to accommodate for possible growth, and thus the container may have an actual capacity greater than the storage strictly needed to contain its elements (i.e., its size).

---

Now let's look at the difference between the two types :

1. vector<int>arr :

• When you declare vector<int>arr, the vector size depends on implementation which is usually 0. So, the vector in this case will start at size 0.

• Whenever you try to push_back() , the vector will see if the present capacity is enough to accommodate that element.

• If the capacity is already enough to accommodate the element, it just assigns the new element in the next empty memory space.

• If the current capacity is full, the vector will reallocate the space. Eg. If you have a current capacity of 4 and it's all used up and you try to pushback an element, then the vector will reallocate the space (for say, 8 elements. The new capacity is almost always doubled than the current capacity) and then push the element into the vector.

• If the new space can't be extended at the present memory location itself (maybe because the space adjacent to it is already occupied by some other variables), then the vector is completely shifted from its original location to a new location where we have sufficient amount of needed space. This process involves copying all the elements of vector to the new location which takes up time.

• If a reallocation happens, the reallocation is itself up to linear in the entire size. But the amortized time-complexity of push_back() still remains constant, i.e O(1)

2. vector<int>arr(n) :

• This declaration will initialise the vector with space for n elements pre-allocated, at the start itself.

• whenever you want to add another element you can just assign the next index using [] operator.

• So, say that your n=5 and you have assigned first two index. You can directly use like arr[2]=4 to add a third element. There's no need to use push_back() as you have already allocated the space needed for n elements in your vector.

• You can still use push_back() if you want to add more than n elements. But for the first n elements, the assignment is done directly using [ ] operator as vector has already been sized to hold n elements.

---

Another choice would to use reserve() if you don't want to intialise using vector<int>arr(n). It indicates that the vector is created such that it can store at least the number of the specified elements without having to reallocate memory. In this case, your initial vector size will be zero and you have to use .push_back() to add any new element. But, first reserving a space and then using push_back will save you from the time-consuming process of reallocation and copying of whole array to new memory location.

Conclusion :

So, since we don't always have to keep allocating new space and copying all the elements of vector using the 2nd type, therefore the 2nd type of declaration is much more efficient than the first type of declaration of you know the size of vector at the start itself.

The efficiency will be as follows:

1. vector<int>arr(n); and directly assigning elements at each index using [ ] operator.

2. arr.reserve(n); after vector declaration and adding new elements using .push_back() method.

3. vector<int>arr; and adding new elements using .push_back() method.

Hope this answers your question !

Answer 2

With

vector<int> Array(n);

you create a vector that contains n elements, all memory needed for those elements is allocated immediately.

When you use e.g.

Array.push_back(value);

then the vector needs to be resized, which could mean the memory have to be reallocated and all the contents have to be copied to the new memory.

---

Instead of creating an array with a set size, you could instead preallocate (or reserve) memory:

vector<int> Array;  // An empty vector
Array.reserve(n);   // Reserve memory, but keep the size as zero (it's still empty)
Array.push_back(value);  // No reallocation needed, size is now one

This is useful when you have a vector of objects that can't be default-constructed.

Important concepts to learn: The vector size and its capacity and what the difference between them is.

The capacity is the number of elements the vector have allocated memory for.

The size is the current number of elements in the vector.

It's quite common for the capacity to be different from the size. And it must always be true that capacity >= size.

Answer 3

The optiumum choice for efficiency is to reserve the required number of elements before using push_back or emplace_back. This guarantees that no reallocations will occur. It's also somewhat more flexible.

The alternative of creating the vector at the required size requires you to construct all the elements of the vector ahead of time and then assign to the already constructed objects.

Answer 4

The first one should be better than the second. Why? std::vector is a dynamic size vector. It means that if u wanna push over its limit, it is gonna resize. How this resize is happening? Allocating new memory, copying everything, and deleting the previous one. This means that using push_back() may trigger this allocation if the capacity is not enough. The first one makes the std::vector with the required capacity from the beginning so no moving required when inserting elements

Note that u can make a std::vector of a specific capacity, and then push_back() is not gonna do any additional allocation, which shall be quite efficient