Multimap question: is find() guaranteed to return the first matching key

I'm trying to track down a problem in someone else's code. At one spot, find() is used on a multimap like so (i is an int):

Code:

---

MyMultiMap::iterator matching = myMultimap.find( i );
while ( matching != myMultimap.end() && matching->first == i )
{
  // do stuff
}

---

My question is if this could be the source of the problem I'm trying to track down. More specifically, is this code guaranteed to iterate over all values in the multimap that have a key of i? In other words, is find() guaranteed to find the first value with i?

According to Schildt (STL Programming From the Ground Up), it is: "[The find() function] always returns an iterator to the first matching key" (page 172). But Meyers, in Effective STL (page 201), writes: "For the multi containers, however, find is not guaranteed to identify the first element in the container with a given value if more than one is present; its character is only to identify one of those elements."

I'm inclined to believe that Schildt is full of bullschildt, and that Meyers is correct, but could someone please confirm this? It's not that I'm worried that Schildt is right when Meyers is wrong (yeah, that'll happen!), I'm more worried that I'm interpreting Meyers wrongly and that find doesn't work with multimaps like I think it does. (One confusing thing is that Meyers uses the word "value" when I think he should be using "key".)

Thanks,
Just

Depends on your semantics.....
The first item found is always the first item found :)
However, there are no gaurentees that it will be the item that was inserted first.

Meyers is more correct.

gg

Thanks for the reply CodePlug.

I think when Meyers uses the word "first", he means "first in the map according to the order it's sorted", not "first element inserted". This would explain why in the next sentence he writes "If you really need the find the first object with a given value, you'll want to employ lower_bound...". (Again I think he should use "key", not "value".)

Having said this, I've done a bit more searching on google groups, and the conclusion I've reached is this: find does not have to return the first element (ie the code in my first post is not technically portable). However, in all commonly used STL implementations, it will work. I don't have a copy of the C++ standard, but I'm guessing it doesn't require find to return the first element, it just happens to have been implemented that way in most (all?) cases.

If one of the more experienced STL users could confirm this (Prelude? Salem?), or if someone could please look this up in the standard, I'd certainly appreciate it. But I'm pretty sure I've got it right, and that the source of the problem I'm trying to track down is elsewhere.

Thanks,
Just

The only guarantee given by the standard is that mm.find(k) will "return an iterator pointing to an element with the key equivalent to k, or mm.end() if such an element is not found".
Key equivalence is defined by the standard as follows: "two keys k1 and k2 are considered to be equivalent if for the comparison object comp, comp(k1, k2) == false && comp(k2, k1) == false".

>> "If you really need [to] find the first object with a given value, you'll want to employ lower_bound"

This is correct. The standard states that lower_bound(k) "returns an iterator pointing to the first element with key not less than k". So if there are one or more keys that are equivalent to k, then lower_bound(k) returns the "first" such key. In this case, the definition of "first" is the first iterator in the sequence which is equivalent to k - and which the previous element (if exists) is always less-than k according the comparison object.

If you require a specific ordering of your Key-Data pairs for those Keys that are equivalent, then you'll have to supply your own Compare object which provides that ordering.

I can tell just by the question's you're asking that you don't need any hand-holding...read and interpret the standard for yourself.
Here's one source.
http://www.kuzbass.ru:8086/docs/isocpp/

I like to use to the SGI documentation on STL as well:
http://www.sgi.com/tech/stl/

gg

Thanks again CodePlug. So my guess on what the standard says was correct, but it seems most STL implementations happen to have find() return the first element anyway (even though it's not required). It also seems (judging from some google groups searching) that many developers actually assume this behaviour!

(Thanks also for the links. I'd already looked at the SGI docs, but they just don't have nearly enough detail to answer this question.)

In case anyone cares, I've just visited Meyer's errata list for Effective STL, and he writes:

Quote:

---

I should make clearer in my discussion of
multimap::find vs. multimap::lower_bound that
only lower_bound is guaranteed to locate the
first element with a given key value; find
is guaranteed only to locate some element
with the given key value.

---

Yes, Meyers, you should! Would have saved me some time!