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: 2010-06-04 02:58:13

#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
 Keywords:                |  
--------------------------+-------------------------------------------------

Comment(by anonymous):

 The problem with keeping track of the first non-empty bucket is just as
 big a problem, we use it for an ultra low latency application and we can't
 use any function that has linear time, even if it is only one in a few
 calls. we can't afford the risk that our erase() happens to be erasing the
 first non-empty bucket and causes a linear search no matter how infrequent
 it may happen.

 Would it be possible to have a function call on the hashmap that I can
 explicitly call to disable this keeping-track-of-first-non-empty feature,
 with the understanding that begin() will no longer have constant time
 complexity? what would be the ramifications of begin() having linear time
 complexity?

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