Re: [boost] [unordered] unordered_set::erase() complexity bug?

Subject: Re: [boost] [unordered] unordered_set::erase() complexity bug?
From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2009-11-27 05:03:10

John Zwinck skrev:
> Jeffrey Bosboom wrote:
>> Getting back to this specific case, I think the two versions of 
>> erase() are different enough in performance to warrant providing both. 
>> Unfortunately, I don't know of a good alternate name for whichever one 
>> isn't named erase().
> 
> A name which is simply synonymous with "erase" may leave people confused.
> I do think that creating a new function name is what's needed here so
> that we may move forward with an obviously-viable solution (as opposed
> to ones which may raise substantive objections, such as lazy evaluation).

I don't think we have sufficient reason for adding two functions. (The 
obvious name remove() is needed for the purpose of getting a unique_ptr 
to a node).

> I suggest augmenting the existing name: something like "erase_fast"
> or even "erase_void" would be fine (at least until someone else comes up
> with something better, for which there will no doubt be plenty of time).

We can just do

   m.erase(++it)

like we do with std::map, so I don't see the need for non-void return.

> As for the production code which I mentioned in my previous message, we
> decided to deploy a solution which erases by key.  This solution is
> almost tragic, for we have the iterator in hand when we decide to
> erase() it, but at least the performance doesn't blow up now.

That is tragic.

-Thorsten