C++ STL: Container Recreation or Reuse after clearing?

Question

In programming we face various situations where we are required to make use of intermediate STL containers as the following example depicts:

while(true)
{
    set < int > tempSet;

    for (int i = 0; i < n; i ++)
    {
        if (m.size() == min && m.size() <= max)
        {
            tempSet.insert(i);
        }
    }
    //Some condition testing code
}

Or

set < int > tempSet;

while(true)
{
    for (int i = 0; i < n; i ++)
    {
        if (m.size() == min && m.size() <= max)
        {
            tempSet.insert(i);
        }
    }
    tempSet.clear();

    //Some condition testing code
}

Which approach is better in terms of time and space complexity considering the present state of C++ compliers?

Answer 1

The second may be slightly better time-wise, but the difference will be extremely minimal -- the code still has to go through and release each of the items in the set, regardless of whether it's re-creating it or clearing it.

(Space-wise they'll be identical.)

Answer 2

As a general rule, there is a memory allocation cost associated with loading data into a container. It is far better to avoid paying that cost many times, by reusing a container. If you actually know how many items, or can make a good guess, you should preallocate space in the container up front.

It is particularly noticeable if you are inserting objects into the container, because you can end up paying lots of extra construction/destruction costs, as the container realizes that it is too small, reallocates memory, and copy constructs new objects into the new memory based on the existing objects.

Always preallocate and reuse. It saves time and memory.

Answer 3

If this is a question of set/map/list, it won't make any difference. If it is a question of vector/hash_set/hash_map/string, the second will either be faster or the same speed. Of course, this difference in speed will only be noticeable if you are doing a very large number of operations (10,000 ints pushed into a vector 10,000 times was about twice as fast - 3 seconds and some change vs. 7 seconds.).

If you are doing something like storing a struct/class in your data structure instead of a pointer to one, this difference will be even greater because on each resize, you have to copy all of the elements.

Again, in almost every case, it won't matter - and in the cases where it does matter, it will show up if you are optimizing, and you care about every bit of performance.

Answer 4

I say the first one is more bug-proof. You're not going to have to remember to clear it (it'll just go out of scope and be done). :-)

Performance-wise there isn't much of a difference, but you should nevertheless measure both cases and see for yourself.

Answer 5

There is very little difference, although your second one avoids calling the constructor and destructor multiple times. On the other hand your first one is one line shorter and guarantees that the container is not visible outside the scope of the loop.

Answer 6

The first version is correct. It is simpler in almost every way. Easier to write, easier to read, easier to understand, easier to maintain, etc....

The second version may be faster, but then again it may not. You would need to show that it had a significant advantage before using it. In most non-trivial cases I would guess that there would not be a measurable performance difference between the two.

Sometimes in embedded programming it is useful to avoid putting things on the stack; in that case the second version would be correct.

Use the first version by default; use the second only if you can give a good reason for doing so (if the reason is performance, then you should have evidence that the benefit is significant).

Answer 7

There will be very little performance difference between the two. You should make your decision based on code readability and robustness.

I think the first example is more readable and safer - what happens in six months time when you add a condition to the loop, perhaps with a continue in there somewhere - in the second example, it will bypass the clear() and you will have a bug.

Answer 8

You are putting your set on the stack, therefor allocation cost is almost zero!

Answer 9

I think you can preallocate a certain number of elements for STL containers, thus having a constant memory allocation cost if you know how many elements will be in the container.