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]

On Fri, 09 Apr 2004 19:15:26 GMT, Michael McKnerney
<mi***************@baesystems.com> wrote:

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

Thanks,
Mike

--
Leor Zolman --- BD Software --- www.bdsoft.com
On-Site Training in C/C++, Java, Perl and Unix
C++ users: Download BD Software's free STL Error Message Decryptor at:
www.bdsoft.com/tools/stlfilt.html

[Leor Zolman]

On Fri, 09 Apr 2004 19:15:26 GMT, Michael McKnerney
<mi***************@baesystems.com> wrote:

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

Thanks,
Mike

--
Leor Zolman --- BD Software --- www.bdsoft.com
On-Site Training in C/C++, Java, Perl and Unix
C++ users: Download BD Software's free STL Error Message Decryptor at:
www.bdsoft.com/tools/stlfilt.html

[Claudio Puviani]

"Michael McKnerney" <mi***************@baesystems.com> wrote

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

[Claudio Puviani]

"Michael McKnerney" <mi***************@baesystems.com> wrote

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]

On Fri, 09 Apr 2004 19:50:20 GMT, "Claudio Puviani" <pu*****@hotmail.com>
wrote:

"Michael McKnerney" <mi***************@baesystems.com> wrote

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.

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

--
Leor Zolman --- BD Software --- www.bdsoft.com
On-Site Training in C/C++, Java, Perl and Unix
C++ users: Download BD Software's free STL Error Message Decryptor at:
www.bdsoft.com/tools/stlfilt.html

[Leor Zolman]

On Fri, 09 Apr 2004 19:50:20 GMT, "Claudio Puviani" <pu*****@hotmail.com>
wrote:

"Michael McKnerney" <mi***************@baesystems.com> wrote

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.

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

--
Leor Zolman --- BD Software --- www.bdsoft.com
On-Site Training in C/C++, Java, Perl and Unix
C++ users: Download BD Software's free STL Error Message Decryptor at:
www.bdsoft.com/tools/stlfilt.html

[Claudio Puviani]

"Leor Zolman" <le**@bdsoft.com> wrote

"Claudio Puviani" <pu*****@hotmail.com> wrote:

"Michael McKnerney" <mi***************@baesystems.com> wrote

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.

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

[Claudio Puviani]

"Leor Zolman" <le**@bdsoft.com> wrote

"Claudio Puviani" <pu*****@hotmail.com> wrote:

"Michael McKnerney" <mi***************@baesystems.com> wrote

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.

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