Modify

Opened 8 years ago

Closed 8 years ago

Last modified 8 years ago

#3693 closed Feature Requests (fixed)

unordered_set::erase(iterator) complexity

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

Description

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.

Attachments (0)

Change History (7)

comment:1 Changed 8 years ago by anonymous

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

comment:2 Changed 8 years ago by Daniel James

Resolution: fixed
Status: newclosed

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

comment:3 Changed 8 years ago by anonymous

Resolution: fixed
Status: closedreopened

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

comment:5 Changed 8 years ago by Daniel James

Resolution: fixed
Status: reopenedclosed

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

comment:6 Changed 8 years ago by 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.

comment:7 Changed 8 years ago by 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.

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain Daniel James.
The resolution will be deleted.

Add Comment


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

 
Note: See TracTickets for help on using tickets.