Re: [Boost-bugs] [Boost C++ Libraries] #4264: boost multi_index hashed_unique erase takes linear time

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #4264: boost multi_index hashed_unique erase takes linear time
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2012-06-07 21:56:49

#4264: boost multi_index hashed_unique erase takes linear time
---------------------------+------------------------------------------------
  Reporter:  anonymous     |       Owner:  joaquin    
      Type:  Bugs          |      Status:  new        
 Milestone:                |   Component:  multi_index
   Version:  Boost 1.41.0  |    Severity:  Showstopper
Resolution:                |    Keywords:             
---------------------------+------------------------------------------------

Comment (by anonymous):

 C++11 is now released, I don't think there is any more debate about the
 complexity guarantees of these routines, or their return values.  Can
 multi-index hashed_index be updated to meet the standard's complexity
 guarantees?  Specifically, the issues mentioned in this bug - a.erase(itr)
 is O(bucket_count) but it is specified to be O(1) average, O(a.size())
 worst-case.

 multi-index is an extremely useful library that I would like to use in
 production code, but I can't use the hashed_index while erase(itr) is
 O(bucket count).  For a hash with a low load factor, O(bucket count) is
 very bad indeed.

 It's unfortunate that the standard requires a larger data structure size
 in implementation.  Perhaps the smaller memory hashtable can still be
 included with the multi-index which does not meet the standard (perhaps
 with a non-constant begin() method, and an erase(itr) that returns void),
 for those who would prefer a smaller memory footprint.

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