no upper_bound() for unordered_multimap

[Ralf Goertz]

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.

BTW, what iterator is returned by multimap::find()? Is it
multimap::lower_bound() or is it not specified? What about
unordered_multimap::find()?

Thanks,

Ralf

 

[SG]

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. The
expensive versions are, however, available in namespace std through the
<algorithms> header.

But std::upper_bound expects iterators referring to an ordered
sequence which -- as you pointed out already -- unordered_multimap
does /not/ provide. So, std::upper_bound cannot be used with iterators
from an unordered_multimap.

 

[Ralf Goertz]

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?

The expensive versions are, however, available in namespace std
through the <algorithms> header.

Could you tell me how to use them? I thought std::upper_bound only works
for ordered containers?

 

[SG]

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?

Equal keys are stored adjacently but other than that there is no
order. So, from what I can tell, an upper_bound function doesn't
really make any sense in this case. Suppose an
unordered_multimap<int,something> contains the following keys in that
order:

4 4 1 8 7 7 5 3

What iterator is upper_bound(7) supposed to return? I have no idea.
Tell me.

Cheers!
SG

 

[Ralf Goertz]

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)
}

 

[SG]

[...] Rephrasing what I said earlier, [upper_bound] returns
an iterator that points to the first element for which every
preceding value is less than or equal to the target key.

That doesn't sound right. You probably meant to say "that points to
the /last/ element for which...". Also, this doesn't cover the case
where the returned iterator equals the second parameter (which doesn't
necessarily point to anything).

Looking at a very early C++0x draft which contains almost no C++0x
feature (N1804.pdf):

std::upper_bound(first,last,value,comp)

returns the furthermost iterator i in the range [first,last) such
that for any iterator j in the range [first,i) the following
corresponding conditions hold: !(value<*j) or comp(value,*j)==false.

But even this definition contains a bug. It rules out i==last which I
think is not intentional. So, it should be "...furthermost iterator i
in the range [first,last] such that..." (including last).

So, on my example, 4 4 1 8 7 7 5 3, upper_bound(7), this could return
an iterator pointing to the element with the key 8. That is, ignoring
the requirement for ordered sequences...

Cheers!
SG

 

[Juha Nieminen]

[...] Rephrasing what I said earlier, [upper_bound] returns
an iterator that points to the first element for which every
preceding value is less than or equal to the target key.

That doesn't sound right. You probably meant to say "that points to
the /last/ element for which...". Also, this doesn't cover the case
where the returned iterator equals the second parameter (which doesn't
necessarily point to anything).

Both are wrong. upper_bound() returns an iterator to the first element
that is greater than the value. (In other words, even if the searched
element exists in the search range, the returned iterator won't point
to it; it will point to the next value that is greater than it.)

The reasoning is simple: upper_bound() returns an "end()" iterator
to the range of equal values in the (ordered) container. In other words,
"one past" the last equal value. Togetether with lower_bound() you can
get the range of equal values (in the same way as equal_range()).

Another property of both lower_bound() and upper_bound() is that if
you insert the searched value at the iterator position returned by
either function, the container will remain ordered. The difference is
that in the first case the element will be inserted as the first element
in the range of equal elements, while in the last case it will be
inserted as the last one.

 

[SG]

On 18 Okt., 18:33, Pete Becker wrote:

[...] Rephrasing what I said earlier, [upper_bound] returns
an iterator that points to the first element for which every
preceding value is less than or equal to the target key.

That doesn't sound right. You probably meant to say "that points to
the /last/ element for which...". Also, this doesn't cover the case
where the returned iterator equals the second parameter (which doesn't
necessarily point to anything).

  Both are wrong. upper_bound() returns an iterator to the first element
that is greater than the value. (In other words, even if the searched
element exists in the search range, the returned iterator won't point
to it; it will point to the next value that is greater than it.)

Your wording isn't any better. It suffers from the same problem I
already pointed out in the above paragraph. Why you snipped my quote
from the standard library is beyond me... Here is it again, just for
your enjoyement. I took the liberty to fix the other issue I pointed
out earlier:

std::upper_bound(first,last,value[,comp])

returns the furthermost iterator i in the range [first,last] such
that for any iterator j in the range [first,i) the following
corresponding conditions hold: !(value<*j) or !comp(value,*j).

The closing ] for the first range is intentional, btw.

Cheers!
SG

 

[Ralf Goertz]

That's a different definition of upper_bound than the current one,

I know that upper_bound might be a misleading name, it is just
convenient to have an interface to unordered_multimap that is as similar
to multimap as possible. In fact the problem arose when I changed a
multimap to unordered_multimap in a working program. I am not
particularly interested in the iterator ub returned by upper_bound. I
just use it to make sure I haven't left the equal_range. Therefore I
don't care whether the key of ub is greater or less than the key I am
currently working on. I just want ub to be the same iterator that comes
*after* the last interesting iterator so that comparison i!=ub returns
false.

Even if you could use upper_bound to get the value you want, this code
formally has data races. Erasing from the container in one thread while
another thread is incrementing an iterator into the same container is a
data race, and results in undefined behavior. For example, suppose one
thread is inside the call to equal_range, and happens to hold an
iterator to element X when a context switch occurs, and the new thread
erases element X; now there's serious trouble.

I know that. That's why (using OMP for multithreading) every change of
the map is guarded by a

#pragma omp critical

directive.

 

[Ralf Goertz]

Seems to me that the solution is one less level of abstraction:

UM::iterator current = m.lower_bound(key);
while (current->first == key)
{
UM::iterator temp = current++;
maybe_delete(temp);
}

Yes, I came up with the same solution this morning, thanks.

Would you be so nice and comment on my second question in the OP: Is it
specified which iterator (if there are more than one) is returned by
find(key) for (unordered)_multimaps? Is it the same as lower_bound()?

Ralf

 

[Joe Gottman]

Seems to me that the solution is one less level of abstraction:

UM::iterator current = m.lower_bound(key);
while (current->first == key)
{
UM::iterator temp = current++;
maybe_delete(temp);
}

Actually, the unordered containers don't provide lower_bound either.
They just provide equal_range, I assume on the logic that you need
both lower_bound and upper_bound to do any useful work.

Joe Gottman