------- Comment #7 from paolo dot carlini at oracle dot com 2010-08-12 10:02 ------- In practice, I don't see how this issue can be tackled independently from the complexity of erase returning iterator: adding a cache for the first non-empty bucket is generally simple, but there is a problem with erase(const key_type&), when it erases the entire first non-empty bucket, thus potentially has to scan all the buckets to update the cache. In other terms, it seems to me that simply adding a cache fixes the complexity of begin() but deteriorates the complexity of erase(const key_type&). Is this the specific point raised in the Boost PR or I'm missing something? Understand it's the first time I'm seriously touching the unordered containers, only simple fixes and cleanups so far.
-- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44480