Clean vector every loop iteration. What is the most memory efficient way?

Question

I have a question about the std::vector.

I have a very memory intensive algorithm where I forsee that predicting vector sizes and reserving enough memory for the vectors in advance will help me a lot with reducing memory usage.

Which of the following is better:

for ( ... ) {
  std::vector<Type> my_vector;
  my_vector.reserve(stuff_count);
  // Do stuff , and append stuff to my_vector.
}

Or this:

std::vector my_vector;
for ( ... ) {
  my_vector.clear();
  my_vector.reserve(stuff_count);
  // Do stuff , and append stuff to my_vector.
}

Please tell me which is best, or if there is an even better way of doing stuff.

Thank you very much in advance!

Answer 1

With the first variant you reallocate the vector's buffer on each iteration – that's usually quite costly. With the second variant you only reallocate occasionally. The second variant is better since speed is a priority for you.

It's unclear from you question where the number of elements is know from. Maybe you even can quickly calculate the maximum number of elements for all iterations, set this to be the buffer size and have no reallocation.

Answer 2

I forsee that predicting vector sizes and reserving enough memory for the vectors in advance will help me a lot with reducing memory usage.

Try and act like an engineer not a fortune teller. Create a test, and measure the difference.

Answer 3

The second one could be slightly faster, but I find the first one cleaner.

Answer 4

As the differences in the code are trivial, why not test both approaches and see which works best for your particular application?

Answer 5

It depends a little on how Type needs to be constructed/destructed, I would say. If it is a POD that does not require destruction, you can skip the clear(), which calls all the destructors in a loop, and use it as a static array instead:

std::vector<Type> my_vector(size);
for (...)
{
  int index = 0;
  // Do stuff
  my_vector[index] = some_value;
}

(Caveat: code untested)

Answer 6

...reserving enough memory for the vectors in advance will help me a lot with reducing memory usage

err... what?! That makes no sense at all. Reserving memory doesn't help with reducing memory usage in any way. It prevents the need for constant reallocation which makes things faster, but as far as usage goes you get no benefit.

Answer 7

The second one will use the maximum memory of all uses of it through the loop, i.e., the maximum size of types of stuff_count. std::vector::clear() does not necessarily free memory. I.e., if you call std::vector::capacity() before and after std::vector::clear() a standard conforming implementation could return the same value.

At best, you'll reduce the number of times you allocate memory with the above scheme. But you certainly won't be reducing the memory footprint at any point. If you want to shrink to the reserved amount of memory, you should use the vector swap idiom:

std::vector<type>().swap(my_vector);
my_vector.reserve(stuff_count); 

Or your first solution, since the overall effect will be the same.

Answer 8

If you need to do a lot of appends use std::deque instead of std::vector and just use "push_back".

Answer 9

how about?

std::vector<DataType> my_vector;
my_vector.resize(sizeof(yourData));
memcpy(reinterpret_cast<char*>(&my_vector), &yourData, sizeof(yourData));