STL Map

[Michael McKnerney]

Hi,

When find(x) is called on an STL map, is the check for equality for the
key performed as:

for all y in the map, find the case where the following is true:
key_compare(x, y)==false && key_compare(y, x)==false


Thanks,
Mike

 

[Leor Zolman]

Hi,

When find(x) is called on an STL map, is the check for equality for the
key performed as:

for all y in the map, find the case where the following is true:
key_compare(x, y)==false && key_compare(y, x)==false

Yes, but this is referred to as "equivalence" rather than "equality" (just
so the concepts can be kept distinct.) Thus it is possible for keys to be
equivalent, based on comparing only some subset of their attributes, when
they'd (perhaps) not compare equal using the == (or !=) operators.

I think your wording "for all y in the map" holds here, but it might not
hold for, say, a multimap (I know, that isn't a "map") , where it would
stop searching when it finds the /first/ equivalent key.
-leor

 

[Claudio Puviani]

When find(x) is called on an STL map, is the check for equality for
the key performed as:

for all y in the map, find the case where the following is true:
key_compare(x, y)==false && key_compare(y, x)==false

The standard guarantees that the order of map's 'find' is log(N), so it will
not compare the search key to every key already in the map but only to those
keys along the search path. In other words, given the red-black tree
structure used by almost all implementations, you should expect at most
2*(log2(length)+1) key comparisons to occur.

Claudio Puviani

 

[Leor Zolman]

The standard guarantees that the order of map's 'find' is log(N), so it will
not compare the search key to every key already in the map but only to those
keys along the search path. In other words, given the red-black tree
structure used by almost all implementations, you should expect at most
2*(log2(length)+1) key comparisons to occur.

At first I thought the OP meant "every element will be examined", but upon
further reflection on his wording, I decided his "all y" was more
math-speak than a reflection of his expectations re. performance (I may, of
course, be wrong about that.)

Anyway, if I'm right, then if he really wanted a solution "for all y" in
the case of multimap, he'd be looking at something like equal_range() for
his answer. Make sense?
-leor

 

[Claudio Puviani]

comparisons to occur.

At first I thought the OP meant "every element will be
examined", but upon further reflection on his wording,
I decided his "all y" was more math-speak than a reflection
of his expectations re. performance (I may, of course,
be wrong about that.)

You could easily be right about that.

Anyway, if I'm right, then if he really wanted a solution
"for all y" in the case of multimap, he'd be looking at
something like equal_range() for his answer. Make sense?

Totally. Or possibly lower_bound() followed by manually testing the key
values while iterating, depending on the specific needs.

Claudio Puviani