Subject: Re: [boost] [unordered] unordered_set::erase() complexity bug?
Date: 2010-03-15 17:27:37
Zitat von Howard Hinnant <howard.hinnant_at_[hidden]>:
> At each remove() the node_ptr is ignored/destructed, thus
> deallocating the node. There is no iterator increment.
> This is a performance-tested solution with your test program:
> 20000: 0m0.012s // your time is 0m0.244s
> 40000: 0m0.017s // your time is 0m0.940s
> 60000: 0m0.024s // your time is 0m5.584s
> 80000: 0m0.028s // your time is 0m4.232s
> 100000: 0m0.037s // your time is 0m34.814s
> 120000: 0m0.041s // your time is 0m33.486s
> The bad news is that the LWG will consider this much too inventive
> at this late date. That being said, I believe it solves several
> real world performance problems (this one and others listed in LWG
> 839). I offer it here in case someone wants to implement it for
> boost containers.
> In case you don't like the "too inventive" response from the C++
> committee, I'm the one to yell at. I will happily forward your
> response to the committee.
I think none of the solutions are perfect, with Option 1(void result)
being the one that makes the most sense to me.
as others have noted it wouldn't be the first time a container
violates that requirement, and a returned iterator is of very limited
use in an unordered container anyway.
but while we're being inventive, I would like to see the following
considered, for the long-term.
if I am not mistaken we're dealing with a function overloading problem here.
overloading by return type.
void erase(iterator); // (1)
iterator erase(iterator); // (2)
s.erase(it); //calls (1)
it=s.erase(it); //calls (2)
this obviously requires language support, but it would solve the
problem beyond this specific case.
problems like this are quite common, and are usually (when you're not
bound to a Container concept) solved like this:
void erase(iterator in,iterator *out=0);
void erase(iterator in);
void erase(iterator in,iterator &out);
you can find signatures like this in several boost libraries.
more examples of overloading by return type:
int f(); // (1)
float f(); // (2)
void f(); // (3)
int a=f(); //calls (1)
f(); //calls (3)
(float)f(); //calls (2)
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk