Abdalah El-Barrad - 1 year ago 62

C++ Question

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 Source

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.