Modify

Opened 8 years ago

Closed 7 years ago

Last modified 7 years ago

#3693 closed Feature Requests (fixed)

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:

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 7 years ago by danieljames

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

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

comment:3 Changed 7 years ago by anonymous

  • Resolution fixed deleted
  • Status changed from closed to reopened

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 7 years ago by danieljames

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

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 7 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.

Add Comment

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain danieljames.
The resolution will be deleted. Next status will be 'reopened'.
Author


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

 
Note: See TracTickets for help on using tickets.