Ticket #3693 (closed Feature Requests: fixed)

Opened 7 years ago

Last modified 6 years ago

unordered_set::erase(iterator) complexity

Reported by: jzwinck@… Owned by: danieljames
Milestone: Boost 1.42.0 Component: unordered
Version: Boost 1.41.0 Severity: Problem
Keywords: unordered_set unordered_map erase iterator complexity n2023 Cc:


Recently raised on the Developers mailing list is the issue that unordered_set::erase(iterator) has complexity O(bucket_count):

The same issue came up just three weeks ago on the GCC bug tracker:

It was also warned about in 2006:

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.


Change History

comment:1 Changed 7 years ago by anonymous

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

comment:2 Changed 7 years ago by danieljames

  • Status changed from new to closed
  • Resolution set to fixed

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

comment:3 Changed 7 years ago by anonymous

  • Status changed from closed to reopened
  • Resolution fixed deleted

reopening this because there appears now to be a consensus to change the result of erase() to "void":

comment:4 Changed 7 years ago by anonymous

comment:5 Changed 7 years ago by danieljames

  • Status changed from reopened to closed
  • Resolution set to fixed

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

comment:6 Changed 7 years ago by danieljames

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

comment:7 Changed 6 years ago by anonymous

GCC reverted the changing the return type to void: erase (once again) returns an iterator, referencing the Dinkumware implementation.


Add a comment

Modify Ticket

Change Properties
<Author field>
as closed
The resolution will be deleted. Next status will be 'reopened'

E-mail address and user name can be saved in the Preferences.

Note: See TracTickets for help on using tickets.