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

Subject: Re: [boost] [unordered] unordered_set::erase() complexity bug?
From: strasser_at_[hidden]
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.

template<class T,...>
class unordered_set{
   ...
   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);

or

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)

void g(int);
void g(float);

g(f()); //ambiguous

Regards,

Stefan