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

Subject: Re: [boost] [unordered] unordered_set::erase() complexity bug?
From: Jeffrey Bosboom (jbosboom_at_[hidden])
Date: 2009-11-26 01:53:04

Stefan Strasser wrote:
> I don't want to argue for it because as I've said, I haven't really thought 
> this through.
> but this isn't a library specific problem, it applies to unnecessary 
> evaluation of discarded return values in general.
> it's just exacerbated in this case because you can't just add a parameter or 
> create a second function like you normally would because the function 
> signature is specified.

Well, C++ is an eagerly-evaluated language, and the construction of a 
return value is part of the effects of a function.  So simply not 
creating return values when they aren't used isn't possible now, as that 
could break existing code; I'm also not sure how this interacts with the 
separate compilation model.  (On the other hand, compilers are allowed 
to perform copy elision, and the consequences of this are more 
surprising when elision isn't performed (leading to performance loss) 
than when it is performed.  Perhaps allowing this optimization wouldn't 
be a problem in practice?)

Allowing overloading on return type wouldn't work well with the type 
inference already performed by compilers, and would create a new way to 
add ambiguity to valid code.  For example, the following code works just 
fine:

int f();
auto i = f();
std::cout << std::make_pair(f(), f());

But add an overload on return type:

int f();
Foo* f(); //added later
auto i = f(); //what's the type of i?
//what are the template args for make_pair?
std::cout << std::make_pair(f(), f());

It's certainly possible for adding an overload on parameter types to 
create an ambiguity when there wasn't one, so perhaps this is 
acceptable, but I find it surprising.

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().

--Jeffrey Bosboom