[Boost-bugs] [Boost C++ Libraries] #3693: unordered_set::erase(iterator) complexity

Subject: [Boost-bugs] [Boost C++ Libraries] #3693: unordered_set::erase(iterator) complexity
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2009-11-28 22:51:04

#3693: unordered_set::erase(iterator) complexity
-------------------------------------------------------------------------+--
 Reporter:  jzwinck@…                                                    |       Owner:  danieljames
     Type:  Feature Requests                                             |      Status:  new        
Milestone:  Boost 1.42.0                                                 |   Component:  unordered  
  Version:  Boost 1.41.0                                                 |    Severity:  Problem    
 Keywords:  unordered_set unordered_map erase iterator complexity n2023  |  
-------------------------------------------------------------------------+--
 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.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/3693>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.