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

Subject: Re: [boost] [unordered] unordered_set::erase() complexity bug?
From: Stefan Strasser (strasser_at_[hidden])
Date: 2009-11-25 16:17:30

Am Wednesday 25 November 2009 18:12:32 schrieb Thorsten Ottosen:
> > it happened in real code.
>
> Ok. Can we see that code snippet, or is it impossible for you to post it?

I can post the snippet doing the actual access, the code that results in the 
elements being removed in reverse order is quite large, so I'll write a short 
description:

I have to be able to access some objects by an object id as long as they're in 
memory, so there is a

unordered_map<object_id,weak_ptr<object> > objects;

the reverse order is the result of an object caching algorithm.
when a cache sweep finds that a couple of thousand objects need to be 
disposed, those objects happen to be in reverse order. they must still be 
removed from the unordered_map one-by-one, because some objects may have been 
accessed at a later time and re-inserted, so they're not disposed in this 
sweep.
the order could probably be changed but I didn't expect it to make a 
difference.

>
> Was there any reason that you could not erase by key instead of by
> iterator, or did it just feel more natural to erase by iterator?

here's the (simplified) code:

unordered_map<object_id,weak_ptr<object> > objects;

iterator it=objects.find(id);
if(it != objects.end() && it->second.expired()){
  objects.erase(it);
}

so I already had the iterator around because the element value is used before 
erasing.
once you discovered the problem it is easy to fix (erase by key), but you 
certainly wouldn't expect that 2 lookups are faster than 1.
with ordered containers you'd want to make sure that you only use 1 lookup, 
and that extends to unordered containers to some degree as well, if there are 
bucket sizes > 1 in the table.

this is just an idea off the top of my head, I haven't thought this through, 
but has the committee ever considered making functions overloadable by their 
return type?

void f(); // 1
int f(); // 2

int main(){
  f(); //resolves to 1
  int b=f(); //resolves to 2
}