[Bug libstdc++/44480] [C++0x] Linear performance of begin() in unordered associative containers

[joaquin at tid dot es]

------- Comment #9 from joaquin at tid dot es  2010-08-12 12:32 -------
Hi Paolo,

My comments on your last two posts:

I think the impact of this is independent of #579: even if erase
does not return an iterator, the cached bucket pointer has to
be synced. This happens for erase(const key_type&) as well as
erase(const_iterator). Of course, if erase(const_iterator) returns
an iterator then the cached bucket pointer cost is masked
(because you need to reach for the next non-empty bucket anyway).

And yes, there is a non-negligible impact on doing the
cache thing. There was no discussion on this on the committe, so
we are basically on our own :-) I agree with you the impact
does not affect the O complexity of insert/erase, but it's
an impact nonetheless. The testcase provided is this: you
have an *empty* container with a large bucket count (because
it held a large number of elements before) and keep adding
and removing the same element: the resulting performance is
linear with the number of buckets. Whether this must be considered
or not a pathological use case I don't know.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44480