Re: [Boost-users] [multi-index] Container not safe against reentrant clear() / erase() ?

Subject: Re: [Boost-users] [multi-index] Container not safe against reentrant clear() / erase() ?
From: joaquin_at_[hidden]
Date: 2009-06-05 05:03:51

Sebastian Theophil escribió:
>> But you can circumvent this simply by using
>>
>>   erase(begin(),end())
>>     
>
> Thanks for the information, I can live with that. How big is the performance impact when using erase(begin(), end()) vs clear()? Now I guess I'm challenging your design ;-) 

Well, you can just profile it. I can't give you exact figures right off 
the top of
my head, but the improvement was huge. Not only the speedup is big in
practical terms, it also affects to big-O complexity (linear with the 
smart clear()
implementation as opposed to O(nlogn) for erase(begin(),end())).

> My only point is that in the few cases where the C++ standard defines the behavior of clear() for the STL containers, it simply says clear() should be equivalent to erase(begin(), end()). It is a bit surprising if the multi_index_container behaves differently in that regard.  
>   
The equivalence stated by the standard refers only to external behavior
and big-O complexity, and implementations are free to improve on that
if they can. In fact, any serious stdlib implementation already does: open
your favorite environment's <set> header, for instance, and if you dig
a little you'll see that clear() is not implemented as erase(begin(),end()),
but usually the removal is done recursively from the root node. This is
the same as ordered indices in Boost.MultiIndex do.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo