CODEWITHSUNDEEP
c++c++11
Nick
Nick

Reputation: 1629

Avoid the reallocation of a vector when its dimension has to be incremented

I have a

vector< pair<vector<double> , int>> samples;

This vector will contain a number of elements. For efficiency rason I initialize it in this way:

vector< pair<vector<double> , int>> samples(1000000);

I know the size in advance (not a compile-time) that I get from another container. The problem is that I have to decrease of 1 element the dimension of vector. Indeed, this case isn't a problem because resize with smaller dimension than the initial no do reallocation.I can do

samples.resize(999999);

The problem is that in some cases rather than decrease the dimension of 1 element I have to increment the dimension of an element. If I do

samples.resize(1000001);

there is the risk of do reallocation that I want avoid for efficiency rasons. I ask if is a possible solution to my problem do like this:

vector< pair<vector<double> , int> samples;
samples.reserve(1000001);
samples.resize(1000000);
.
. Elaboration that fill samples 
.
samples.resize(1000001); //here I don't want reallocation

or if there are better solutions? Thanks in advance!

(I'm using C++11 compiler)

Upvotes: 1

Views: 1298

Answers (3)

ovanes
ovanes

Reputation: 5673

Just wrote a sample program to demonstrate, that resize is not going to reallocate space if capacity of the vector is sufficient:

#include <iostream>
#include <vector>
#include <utility>
#include <cassert>

using namespace std;

int main() 
{
  vector<pair<vector<double>, int>> samples;
  samples.reserve(10001);

  auto data = samples.data();

  assert(10001==samples.capacity());

  samples.resize(10000);
  assert(10001 == samples.capacity());
  assert(data == samples.data());

  samples.resize(10001); //here I don't want reallocation
  assert(10001==samples.capacity());
  assert(data == samples.data());  
}

This demo is based on assumption that std::vector guarantees contiguous memory and if data pointer does not change, than no realloc took place. This is also evident, by capacity() result to remain 10001 after every call to resize().

cppreference on vectors:

The storage of the vector is handled automatically, being expanded and contracted as needed. Vectors usually occupy more space than static arrays, because more memory is allocated to handle future growth. This way a vector does not need to reallocate each time an element is inserted, but only when the additional memory is exhausted. The total amount of allocated memory can be queried using capacity() function.

cppreference on reserve:

Correctly using reserve() can prevent unnecessary reallocations, but inappropriate uses of reserve() (for instance, calling it before every push_back() call) may actually increase the number of reallocations (by causing the capacity to grow linearly rather than exponentially) and result in increased computational complexity and decreased performance.

cppreference also sates to resize:

Complexity

Linear in the difference between the current size and count. Additional complexity possible due to reallocation if capacity is less than count

Upvotes: 5

Ian.Zhang
Ian.Zhang

Reputation: 171

As I recall when resize less than capacity, There will not be reallocation. So, your code will work without reallocation.

cppreference.com
Vector capacity is never reduced when resizing to smaller size because that would invalidate all iterators, rather than only the ones that would be invalidated by the equivalent sequence of pop_back() calls.

Upvotes: 1

eerorika
eerorika

Reputation: 238351

I ask if is a possible solution to my problem do like this:

samples.reserve(1000001);
samples.resize(1000000);

Yes, this is the solution.

or if there are better solutions?

Not that I know of.

Upvotes: 1

Related Questions