On 7 April 2011 16:52, Brad Higgins <bhiggins@arbor.net> 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.