Boost logo

Boost :

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

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
the order could probably be changed but I didn't expect it to make a

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

so I already had the iterator around because the element value is used before
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

Boost list run by bdawes at, gregod at, cpdaniel at, john at