Boost logo

Boost :

Subject: Re: [boost] [unordered] unordered_set::erase() complexity bug?
From: Peder Holt (peder.holt_at_[hidden])
Date: 2009-11-26 03:35:32


2009/11/26 Jeffrey Bosboom <jbosboom_at_[hidden]>

> 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().
>
> Would it be possible to implement lazy evaluation of the iterator?

template<typename UnorderedSet>
class lazy_iterator_evaluator {
public:
    lazy_iterator_evaluator(...)
    typedef typename UnorderedSet::iterator iterator;
    operator iterator() {//Do the heavy calculations here}
};

an let erase return this instead?
lazy_iterator_evaluator<unordered_set<T> > unordered_set<T>::erase(...);

Regards
Peder Holt

--Jeffrey Bosboom
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk