Time complexity of map functions: erase V/S clear

[prasadi]

Hi All,

Have look at the following code snippets.

map<string,Object*> amap; // delcartion of map

for ( map<string,Object*>::iterartor amapitr = amap.begin(); amapitr != amap.end(); amapitr++)
erase(amapitr);

or

amap.clear();

Which code yields the best performance interms of time complexity??
And also which one is secure to clear the dynamically allocated entries of map(here Object* is dynamically allocated).

Thanks in advance.
Prasad

[Zhuge]

Neither deallocate the memory; you have to do that yourself. As for time complexity, I imagine (read: I don't know for sure, but think) that they are the same though clear() could potentially be quicker with it's access to the private members.

[prasadi]

Of course deletion of Object* shuld be taken care.
I'm concerned about the time complexity ...
In wikipedia
vector::erase - Deletes elements from a vector (single & range), shifts later elements down. O(n) time.

vector::clear - Erases all of the elements. (For most STL implementations this is O(1) time and does not reduce capacity)

What is your opinion for the above statements.

Thanks
Prasad.

[Disch]

Are you looking up map or vector?

vector is definately faster to clear than it is to erase individual elements.

map will probably self balance if you erase elements one by one, so it too is better to clear than erase individual elements.

[prasadi]

both, what happens if clear map/vector, does the capacity remains same even after clear??

[Disch]

See other post:

http://cplusplus.com/forum/general/17280/

[melkiy]

map<string,Object*> amap; // delcartion of map

for ( map<string,Object*>::iterartor amapitr = amap.begin(); amapitr != amap.end(); amapitr++)
erase(amapitr);

Don't do that. After erase(amapitr) the iterator becomes invalid, then you ++it... The program must crash.

Even if you would have written it correctly, each erase() operation requires rebalancing. Maybe clear() method gets it around.

[jsmith]

clear() cannot be slower than erase() in a for-loop, as otherwise clear() would be implemented
using the loop. Having said that, I am almost certain that the loop is slower because each removal
of an element may cause the tree to get rebalanced, an operation that would clearly be avoided
inside a clear() method since the end condition is an empty map.

If you need to store pointers in a map, a better choice of container perhaps is boost::ptr_map<>, which
works similar to std::map<> where the value is a pointer, except that boost::ptr_map<> internally
does a delete of the pointer for you.

[melkiy]

I've mesured the times of cycle erasion and clear(). Map had 10^6 elements. For 2 methods:

for(; !m.empty(); m.erase(m.begin()));

m.clear();

the results are quite close: 0.34 vs 0.33 sec.

[kempofighter]

A general rule of thumb is to trusy the algorithms and container member functions over your own hand written loops. The container and algorithm designers have intimate knowledge of the implementation where as we don't unless we spend an extraordinary amount of time studying the implementation so that we are aware of the same details as they are. You might be able to write your own loop that comes close but I seriously doubt that many people could write a custom loop that is faster than the member function. Even if you could write something to be slightly faster, would it be worth the time spent doing the research? You'd have to prove that your implementation is significantly better so that you can justify the time spent. Then try your implementation with different compilers and see what happens. Another issue involves portability. The underlying implementation could change in the future rendering your hand written improvement obsolete.