Bad Allocation Exception by filling a vector

[blueshark]

Hey Guys,

I am using MSVC++ and here I am using a vector as a container and I am storing 3d Points in it. The Points have a double for each coordinate.

When I store many many points in my vector, sometimes the function push_back throws a bad_alloc exception. The exception is thrown in the cases, that the size of the vector reaches the capacity and, hence the vector has to resize itself. My guess is, that the vector needs a specific amount of memory, which is, as a connected block, not available, although this amount of memory is free.
When I reserve this amount of memory, while I create the vector, this exception is not thrown. This leads me to my guess.

So my question is, is my quess correct and is there any posibility to solve this issue?

Thank you

blueshark

[Denis]

Why don't you want to use reserve?

[blueshark]

In general, I don't know how many points I have to store in the vector.

While I was debugging my code, I used an example, where I know the amount of points. And here I was able to use reserve. In general it is not possible.

Currently my work around is to use a list instead of a vector. It makes some parts harder to code without a random access iterator, but it is possible. This emphasizes that my guess might be correct, but I am still not 100% sure. I haven't even found any other post, comments or reports in the Internet about this issue.

[kbw]

You're right. bad_alloc means out of memeory. As the vector grows it fragments the heap as well as demand more overall when compared to a list.

As a matter of interest, how many points do you have?

Prehaps you could increase the amount of virtual memory on the box.

[blueshark]

Actually I have round about 10 Million Points. A Point is a class, which stores the 3 coordinates as double values and provides some operator functions, like adding points, etc.
So 10 Million Points are 10Mio*3*2 = 60 MB.
This is also one part, which I don't understand. 60 MB does not sound so huge, that my programm will run out of memory, even when I use a vector. But for some reason it works when I use a list instead of a vector.

The initial size for my virtual memory is 1GB and the maximus is 4GB. Even setting the initial VM size to 4GB does not change the behaviour of my code. I am using Windows XP 32Bit. Does it make sense to make the maximum virtual memory larger than 4GB?

[kbw]

sizeof(double) = 8. You have 10M * 3 * 8 = 160M.

A std::list is a double-threaded list, so you have at least an extra 8 bytes per node.

You could just allocate enough space for a 12M points or so and use the block as an array, or reserve space in your vector before you begin.

[jsmith]

Your problem is memory fragmentation due to the way vector resizes itself.
Your vector<> implementation probably does not grow the vector by the right
amount. Growing the vector by a factor of 2 when it needs to be resized is
the worst possible growth factor.

Easiest way to tell if this is occurring is to print out the address of the zeroth element
periodically. You'll see it increase towards 0xFFFFFFFF.

Solutions are (in addition to std::list) to reserve the memory ahead of time (which you
said you can't do) or use std::deque.