Re: [boost] [unordered] equal_range is O(bucket_count()), not O(size())

Subject: Re: [boost] [unordered] equal_range is O(bucket_count()), not O(size())
From: Daniel James (dnljms_at_[hidden])
Date: 2011-04-07 12:39:30

On 7 April 2011 16:52, Brad Higgins <bhiggins_at_[hidden]> wrote:
> TR1 specifies that unordered_multimap::equal_range(k) worst case complexity is O(size()).  However, in practice, I find that the worst case performance of boost unordred_multimap's equal_range is O(bucket_count()).  Is this known?

There was a defect report about this:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3247.html#764

Also, erase has a similar problem:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3247.html#579

I think I'm going to have to change the data structure to something
more efficient for these cases. The claim that it can be done without
loss of efficiency seems a bit dubious to me, I'm pretty sure it'll
require using more memory (i.e. an extra pointer or std::size_t per
node or per bucket) which I've been discouraged from doing in the
past.