id	summary	reporter	owner	description	type	status	milestone	component	version	severity	resolution	keywords	cc
3693	unordered_set::erase(iterator) complexity	jzwinck@…	Daniel James	"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):
[changeset: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."	Feature Requests	closed	Boost 1.42.0	unordered	Boost 1.41.0	Problem	fixed	unordered_set unordered_map erase iterator complexity n2023