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-05-30 10:00:32

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

 Hi,

 The first problem you mention has been debated for a number of years in
 the C++ commitee (C++0x unordered associative containers have exactly the
 same problem) and that debate is probably not over yet:

 http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#579


 I still hope that the signature of `erase` will be changed so as to return
 `void`, and will update Boost.MultiIndex accordingly. In the meantime, if
 your hashed index is unique (no duplicates) or you don't mind erasing all
 equivalent elements at once, you can replace your statements of the form

 `c.erase(it);`

 with

 `c.erase(c.key_extractor()(*it));`

 that is, you erase based on the key of the element pointed to by `it`;
 this overload of `erase` does not return an iterator and thus has constant
 complexity.

 As for the second problem with tracking the first non-empty bucket, I
 don't see an easy solution here, because `begin` is required to be
 constant. How big the impact of this particular issue is in your case
 (leaving aside the first problem)?

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