Abdalah El-Barrad Abdalah El-Barrad - 4 months ago 16
C++ Question

Allocating memory for a vector of vectors

I'm trying to reserve space for a vector of vectors, but it doesn't work and throws the following error:

terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc


Every time I use a large enough number. A minimal version of what I have is below:

#include <vector>
#include <iostream>
using namespace std;


int main(){

int base;
cout << "Enter Base: ";
cin >> base;

int dimension;
cout << "Enter Dimension: ";
cin >> dimension;

int perms = 1;
for(int i=0; i<dimension; i++){
perms *= base;
} // This gets the number of permutations with repetition

int length;
cout << "Enter Length: ";
cin >> length;

float structSize = 1.0;

for(float i=0.0; i<length; i++){
structSize *= perms-i;
structSize /= (i+1.0);
} // This gets the number of combinations

vector< vector< vector<double> > > allStructs;
allStructs.reserve(structSize);

return 0;
}


It should work for large structSizes, but fails at base=3, dimension=4, length=6 which makes structSize=324,540,216. Is it possible for this to work?

Answer

You need to think about your memory use.

It should work for large structSizes, but fails at base=3, dimension=4, length=6 which makes structSize=324,540,216. Is it possible for this to work?

So what you're doing, at an abstract level, is allocating a data structure that contains 324,540,216 instances of a vector<vector<double>> object.

Here's what we know about vector objects:

  • Its size must be at least 16 bytes; it needs to store a pointer, which in a 64-bit architecture, is probably 8 bytes, and it needs to store a size, which will probably also be 8 bytes.
  • Its size is probably going to be significantly bigger, since the moment you instantiate the last vector<double> object, it's going to consume another [at-least-] 16 bytes each time you create one.

So just on the face of it, your allStructs.reserve(structSize) call is allocating 5 Gigabytes. It's probably allocating more than that, since the size of a vector's metadata could very well be larger than 16 bytes.

Comments