unordered_set::erase(iterator) complexity

[jzwinck@…]

Recently raised on the Developers mailing list is the issue that unordered_set::erase(iterator) has complexity O(bucket_count): ​http://lists.boost.org/Archives/boost/2009/11/159116.php

The same issue came up just three weeks ago on the GCC bug tracker: ​http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975

It was also warned about in 2006: ​http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2023.pdf

Slightly related, a change to Boost.MultiIndex (made by the author of n2023): 33914

Daniel James suggested in the Developers thread that I should file this ticket. My desired outcome is the ability to erase by iterator from an unordered_set or unordered_map in constant time. The name of the method is not important to me; I suggested erase_fast or erase_void just to get the ball rolling.

[anonymous]

related to #3668 (same issue in Boost.Intrusive)

[Daniel James]

Fixed in [58403] on trunk, [58605] on release. I called it erase_return_void.

[anonymous]

reopening this because there appears now to be a consensus to change the result of erase() to "void": ​http://home.roadrunner.com/~hinnant/issue_review/lwg-active.html#579

[anonymous]

GCC changed to void ​http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975

[Daniel James]

I've created a new ticket (#3966) for this.

[Daniel James]

Btw. I'll wait until after the next meeting before dealing with this, I think it should be in time for the next release.

[anonymous]

GCC reverted the changing the return type to void: ​http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975 erase (once again) returns an iterator, referencing the Dinkumware implementation.