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]

Re: STL Map

On Fri, 09 Apr 2004 19:15:26 GMT, Michael McKnerney
<michael.mckner ney@baesystems. com> wrote:
[color=blue]
>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[/color]

Yes, but this is referred to as "equivalenc e" 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
[color=blue]
>
>Thanks,
>Mike
>[/color]

--
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:

https://www.bdsoft.com/tools/stlfilt.html

[Leor Zolman]

Re: STL Map

On Fri, 09 Apr 2004 19:15:26 GMT, Michael McKnerney
<michael.mckner ney@baesystems. com> wrote:
[color=blue]
>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[/color]

Yes, but this is referred to as "equivalenc e" 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
[color=blue]
>
>Thanks,
>Mike
>[/color]

--
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:

https://www.bdsoft.com/tools/stlfilt.html

[Claudio Puviani]

Re: STL Map

"Michael McKnerney" <michael.mckner ney@baesystems. com> wrote[color=blue]
> 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[/color]

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]

Re: STL Map

"Michael McKnerney" <michael.mckner ney@baesystems. com> wrote[color=blue]
> 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[/color]

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]

Re: STL Map

On Fri, 09 Apr 2004 19:50:20 GMT, "Claudio Puviani" <puviani@hotmai l.com>
wrote:
[color=blue]
>"Michael McKnerney" <michael.mckner ney@baesystems. com> wrote[color=green]
>> 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[/color]
>
>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.[/color]

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
[color=blue]
>
>Claudio Puviani
>[/color]

--
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:

https://www.bdsoft.com/tools/stlfilt.html

[Leor Zolman]

Re: STL Map

On Fri, 09 Apr 2004 19:50:20 GMT, "Claudio Puviani" <puviani@hotmai l.com>
wrote:
[color=blue]
>"Michael McKnerney" <michael.mckner ney@baesystems. com> wrote[color=green]
>> 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[/color]
>
>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.[/color]

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
[color=blue]
>
>Claudio Puviani
>[/color]

--
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:

https://www.bdsoft.com/tools/stlfilt.html

[Claudio Puviani]

Re: STL Map

"Leor Zolman" <leor@bdsoft.co m> wrote[color=blue]
> "Claudio Puviani" <puviani@hotmai l.com> wrote:[color=green]
> >"Michael McKnerney" <michael.mckner ney@baesystems. com> wrote[color=darkred]
> >> 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[/color]
> >
> >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[/color]
> 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.)[/color]

You could easily be right about that.
[color=blue]
> 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?[/color]

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

Claudio Puviani

[Claudio Puviani]

Re: STL Map

"Leor Zolman" <leor@bdsoft.co m> wrote[color=blue]
> "Claudio Puviani" <puviani@hotmai l.com> wrote:[color=green]
> >"Michael McKnerney" <michael.mckner ney@baesystems. com> wrote[color=darkred]
> >> 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[/color]
> >
> >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[/color]
> 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.)[/color]

You could easily be right about that.
[color=blue]
> 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?[/color]

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

Claudio Puviani