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-08 17:07:30

#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):

 Hello

 A possible solution to this bug is to keep an intrusive list of the nodes
 in the table, so begin() and the returned iterator are O(1) when using
 erase(iterator).

 BTW, it is not amortized.  If the bucket table is resized to be 2 million,
 and you constantly insert()/erase() a couple of elements.  You
 consistently get the worse case scenario.

 Also, since, the bucket vector never shrinks, the problem can also be
 reproduced by insert()ing 2 million objects, then erase()ing them. The
 erase()ing will take forever.

 Thanks,
 Sasha

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