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
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.
Boost list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk