CODEWITHSUNDEEP
c++vectordynamic-memory-allocation
Dohyun
Dohyun

Reputation: 642

resize and reserve in vector

Main question

Does resize for vector affect performance even if its capacity is bigger than its size?

For example, I want to make a code for pseudo code like following

const size_t size_a = 2;
const size_t i_max = 3;
vector<int> a(size_a) = random_vector;
vector<int> b;

for (size_t i=0; i<i_max; i++){
    patch_a_at_the_end_of_b;
}

So, b changes its size every loop but it will monotonically increase and I know the final size of b.

Firstly, I make a function concat(a,b) such that patch a to the end of b.

void concat(const vector<int> a, vector<int> &b){
    const size_t size_b = b.size();
    b.resize(size_b+a.size());
    for(size_t i=0; i<a.size(); i++)
        b[size_b + i] = a[i];
}

Note that we resize vector every time when b is called by concat.

Then, I add b.reserve in front of for loop in main function.

const size_t size_a = 2;
const size_t i_max = 3;
vector<int> a(size_a) = random_vector;
vector<int> b;
b.reserve(size_a*i_max);

for (size_t i=0; i<i_max; i++){
    concat(a,b);
}

Upvotes: 2

Views: 1463

Answers (1)

Peter
Peter

Reputation: 36597

The specification of std::vectors operations probably provide most of the answer to this question.

Firstly, resize() is specified as being void resize(size_type n, value_type val = value_type()), with requirements;

  • If n is less than the current size, the additional elements then the additional elements are removed and destroyed (i.e. if elements have a destructor, the destructor is invoked).
  • If n is greater than the current container size, the content is expanded by inserting at the end as many elements as needed to reach the size of n. If val is specified, the new elements are initialized as copies of val, otherwise, they are value-initialized.
  • If n is also greater (emphasis mine) than the current container capacity, an automatic reallocation of the allocated storage space takes place.

Note that nothing whatsoever is said about reducing the container capacity if its size is reduced.

Now, reserve(size_type n) is specified as requesting that the vector capacity be n or more elements, with requirements

  • If n is greater than the current vector capacity, the function causes the container to reallocate its storage increasing its capacity to n (or greater).
  • In all other cases, the function call does not cause a reallocation and the vector capacity is not affected.
  • This function has no effect on the vector size and cannot alter its elements.

The second point here may be interpreted as saying that reserve() cannot be used to reduce capacity.

Note: I'm paraphrasing in the above, but it is essentially a summary of what the standard requires of resize() and reserve().

Putting those points together: The only circumstance in which resize() (or any other operation that increases the size of the vector) is required to increase capacity of the vector is if the new size exceeds the current capacity.

Beyond that, what happens is a quality of implementation concern. However, one logical manner of implementation would be;

  • resize() (and other operations that increase size of the vector) never increases capacity unless the new size exceeds current capacity
  • reserve() never reduces capacity

In such an implementation, calling reserve() before doing operations that increase size of the vector would give a performance advantage (eliminating need for actual reallocation unless the size ever grows to exceed the capacity specified using reserve()).

Things would potentially be different if an implementation used a different approach, such as reducing capacity of a container at any stage (e.g. if a call of resize() reduces the size, it also reduces the capacity). This might be done in an attempt to minimise total memory usage of the container (i.e. not keeping additional capacity allocated for as long as the vector itself exists). This would give a performance hit if the size of the vector oscillates in size (e.g. increases in some circumstances, decreases in others).

Upvotes: 3

Related Questions