Re: no upper_bound() for unordered_multimap
Pete Becker wrote:
On 2010-10-18 09:20:47 -0400, Ralf Goertz said:
Pete Becker wrote:
On 2010-10-18 07:52:33 -0400, Ralf Goertz said:
Hi,
why is there no upper_bound() (or lower_bound()) for unordered_multimap
like there is for normal multimap? I think this is odd since there is
equal_range() for unordered_multimap and the interators in the returned
pair is what I would lower_bound() and upper_bound() expect to return.
As the name suggests, unordered_multimap isn't required to store its
elements in any particular order. This makes upper_bount and
lower_bound much more expensive than they are for multimap.
Hm, pairs with equal keys must be contiguously stored also in an
unordered map so that when you start with m.equal_range(key).first and
increment it until you reach m.equal_range(key).second you have visited
*all* elements with key "key" and *no* *other*. At least that is my
understanding. Why then should it be much more expensive to find the
upper bound? You only need to find an appropriate element's iterator and
increment it until you get an iterator which points to an element with a
different key. So this shouldn't be more expensive then traversing the
map, right?
upper_bound gives you an iterator that guarantees that every element
that comes before the key is in front of that iterator. While that can
be done, for an unsorted sequence it's not particularly useful:
{ 1, 4, 3, 2 };
What should upper_bound return for a key of 3? Yes, it could return an
iterator pointing to the first element, but what can you sensibly do
with that iterator?
It should return the iterator that comes after the iterator for "3".
That is the iterator that I get when I traverse the whole unordered
multimap. I think that is the one I get with equal_range(3).second. As I
said in my OP I don't see why there is equal_range() for
unordered_multimap but no upper/lower_bound().
As to why I need upper bound: I use equal_range to visit all elements in
a multithreaded program. There will be no inserts into the
unordered_multimap (which could invalidate iterators) during the
multithreading. There are only erases. And that is the problem. I can't
be sure that the upper_bound-element still exists. Another thread might
have erased the element. That's why I want to check if my just
incremented iterator is equal to the upper_bound for that key. Maybe this
example explains it:
typedef unordered_multimap<int,int> UM;
UM m;
//m is filled and then multithreading begins
pair<UM::iterator,UM::iterator> itp=m.equal_range(thread_specifik key);
for(;itp.first!=itp.second;++itp.first) // does itp.second still exist?
{
//possibly erase(itp.first)
}