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-11 13:03:46

#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

 How about using policy based programming to get the best of both worlds?

 One possibility is to use template arguments that override the current
 default implementation, and make erase() O(1) and begin() O(bucket vector
 size).

 Another possibility is to add a method like enable_fast_erase_slow_begin()
 that override the current default implementation, and make erase() O(1)
 and begin() O(bucket vector size).

 Obviously, once policy based programming is used, it opens the door to
 several implementations that will satisfy all users of multi-index.

 Thanks,
 Sasha

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