STL set/map w.r.t const char*

[S S]

Hi

I have a very basic question, but it's a good one. Below is the code
fragment.

struct ltstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) < 0;
}
};

int main()
{
const int N = 6;
const char* a[N] = {"isomer", "ephemeral", "prosaic",
"nugatory", "artichoke", "serif"};
set<const char*, ltstrA(a, a + N);
if (A.find("ephemeral") != A.end())
cout << "Found";
else
cout << "Not found";
return 0;
}

Output will be -"Found"
My question is , Why?

How it is able to compare a const char* with another const char* to
find that value? I did not specify any equality operator? I just
mentioned strcmp(s1, s2) < 0
which means, when strcmp(s1, s2) == 0 (in case of match)
it will return false. So how set/map are able to find the const char*
value?

[Jim Langston]

S S wrote:

Hi

I have a very basic question, but it's a good one. Below is the code
fragment.

struct ltstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) < 0;
}
};

int main()
{
const int N = 6;
const char* a[N] = {"isomer", "ephemeral", "prosaic",
"nugatory", "artichoke", "serif"};
set<const char*, ltstrA(a, a + N);
if (A.find("ephemeral") != A.end())
cout << "Found";
else
cout << "Not found";
return 0;
}

Output will be -"Found"
My question is , Why?

How it is able to compare a const char* with another const char* to
find that value? I did not specify any equality operator? I just
mentioned strcmp(s1, s2) < 0
which means, when strcmp(s1, s2) == 0 (in case of match)
it will return false. So how set/map are able to find the const char*
value?

I believe it's undefined behavior. You have the constant "ephemeral" in
your program twice. Once for the char array, once for the parameter of the
find. The compiler probably sees that they are exactly the same, so instead
of making 2 it just makes one and uses the same pointer for both.

An example of this is this program that on my system outputs:
00416808 00416808
one time I run it

#include <iostream>

int main()
{
const char* foo = "Hello";
const char* bar = "Hello";

std::cout << reinterpret_cast<const int*>( foo ) << " " <<
reinterpret_cast<const int*>( bar ) << "\n";
}

The compiler doesn't bother to create two constant arrays for "Hello", since
it's constant it just creates it once and uses the same address for both foo
and bar.

--
Jim Langston
ta*******@rocketmail.com

[Ian Collins]

Jim Langston wrote:

S S wrote:

>Hi

I have a very basic question, but it's a good one. Below is the code
fragment.

struct ltstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) < 0;
}
};

int main()
{
const int N = 6;
const char* a[N] = {"isomer", "ephemeral", "prosaic",
"nugatory", "artichoke", "serif"};
set<const char*, ltstrA(a, a + N);
if (A.find("ephemeral") != A.end())
cout << "Found";
else
cout << "Not found";
return 0;
}

Output will be -"Found"
My question is , Why?

How it is able to compare a const char* with another const char* to
find that value? I did not specify any equality operator? I just
mentioned strcmp(s1, s2) < 0
which means, when strcmp(s1, s2) == 0 (in case of match)
it will return false. So how set/map are able to find the const char*
value?

I believe it's undefined behavior. You have the constant "ephemeral" in
your program twice. Once for the char array, once for the parameter of the
find. The compiler probably sees that they are exactly the same, so instead
of making 2 it just makes one and uses the same pointer for both.

That does not matter, note the use of the second template argument of
std::set.

--
Ian Collins.

[Ian Collins]

S S wrote:

Hi

I have a very basic question, but it's a good one. Below is the code
fragment.

struct ltstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) < 0;
}
};

int main()
{
const int N = 6;
const char* a[N] = {"isomer", "ephemeral", "prosaic",
"nugatory", "artichoke", "serif"};
set<const char*, ltstrA(a, a + N);
if (A.find("ephemeral") != A.end())
cout << "Found";
else
cout << "Not found";
return 0;
}

Output will be -"Found"
My question is , Why?

How it is able to compare a const char* with another const char* to
find that value? I did not specify any equality operator? I just
mentioned strcmp(s1, s2) < 0
which means, when strcmp(s1, s2) == 0 (in case of match)
it will return false. So how set/map are able to find the const char*
value?

Given an ordered set, A < B < C and a search item X,

if (X < C) and !(B < X) then X is equivalent to B.

--
Ian Collins.

[S S]

On May 6, 2:38 pm, "Jim Langston" <[e-mail]:

S S wrote:

Hi

I have a very basic question, but it's a good one. Below is the code
fragment.

struct ltstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) < 0;
}
};

int main()
{
const int N = 6;
const char* a[N] = {"isomer", "ephemeral", "prosaic",
"nugatory", "artichoke", "serif"};
set<const char*, ltstrA(a, a + N);
if (A.find("ephemeral") != A.end())
cout << "Found";
else
cout << "Not found";
return 0;
}

Output will be -"Found"
My question is , Why?

How it is able to compare a const char* with another const char* to
find that value? I did not specify any equality operator? I just
mentioned strcmp(s1, s2) < 0
which means, when strcmp(s1, s2) == 0 (in case of match)
it will return false. So how set/map are able to find the const char*
value?

I believe it's undefined behavior. You have the constant "ephemeral" in
your program twice. Once for the char array, once for the parameter of the
find. The compiler probably sees that they are exactly the same, so instead
of making 2 it just makes one and uses the same pointer for both.

An example of this is this program that on my system outputs:
00416808 00416808
one time I run it

#include <iostream>

int main()
{
const char* foo = "Hello";
const char* bar = "Hello";

std::cout << reinterpret_cast<const int*>( foo ) << " " <<
reinterpret_cast<const int*>( bar ) << "\n";

}

The compiler doesn't bother to create two constant arrays for "Hello", since
it's constant it just creates it once and uses the same address for both foo
and bar.

--
Jim Langston
[e-mail]

Jim,

This way, it has been used extensively in our code, and it all works
fine. I am not much convinced with your argument, but you may be true.
But then, how to use find() function?

[S S]

On May 6, 2:45 pm, Ian Collins <[e-mail]:

Jim Langston wrote:

S S wrote:

Hi

I have a very basic question, but it's a good one. Below is the code
fragment.

struct ltstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) < 0;
}
};

int main()
{
const int N = 6;
const char* a[N] = {"isomer", "ephemeral", "prosaic",
"nugatory", "artichoke", "serif"};
set<const char*, ltstrA(a, a + N);
if (A.find("ephemeral") != A.end())
cout << "Found";
else
cout << "Not found";
return 0;
}

Output will be -"Found"
My question is , Why?

How it is able to compare a const char* with another const char* to
find that value? I did not specify any equality operator? I just
mentioned strcmp(s1, s2) < 0
which means, when strcmp(s1, s2) == 0 (in case of match)
it will return false. So how set/map are able to find the const char*
value?

I believe it's undefined behavior. You have the constant "ephemeral" in
your program twice. Once for the char array, once for the parameter of the
find. The compiler probably sees that they are exactly the same, so instead
of making 2 it just makes one and uses the same pointer for both.

That does not matter, note the use of the second template argument of
std::set.

--
Ian Collins.

Ian,

You wanted to explain something? I did not get you, sorry. Could you
elaborate please?

[S S]

On May 6, 3:34 pm, S S <[e-mail]:

On May 6, 2:38 pm, "Jim Langston" <[e-mail]:

S S wrote:

Hi

I have a very basic question, but it's a good one. Below is the code
fragment.

struct ltstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) < 0;
}
};

int main()
{
const int N = 6;
const char* a[N] = {"isomer", "ephemeral", "prosaic",
"nugatory", "artichoke", "serif"};
set<const char*, ltstrA(a, a + N);
if (A.find("ephemeral") != A.end())
cout << "Found";
else
cout << "Not found";
return 0;
}

Output will be -"Found"
My question is , Why?

How it is able to compare a const char* with another const char* to
find that value? I did not specify any equality operator? I just
mentioned strcmp(s1, s2) < 0
which means, when strcmp(s1, s2) == 0 (in case of match)
it will return false. So how set/map are able to find the const char*
value?

I believe it's undefined behavior. You have the constant "ephemeral" in
your program twice. Once for the char array, once for the parameter of the
find. The compiler probably sees that they are exactly the same, so instead
of making 2 it just makes one and uses the same pointer for both.

An example of this is this program that on my system outputs:
00416808 00416808
one time I run it

#include <iostream>

int main()
{
const char* foo = "Hello";
const char* bar = "Hello";

std::cout << reinterpret_cast<const int*>( foo ) << " " <<
reinterpret_cast<const int*>( bar ) << "\n";

}

The compiler doesn't bother to create two constant arrays for "Hello", since
it's constant it just creates it once and uses the same address for both foo
and bar.

--
Jim Langston
[e-mail]

Jim,

This way, it has been used extensively in our code, and it all works
fine. I am not much convinced with your argument, but you may be true.
But then, how to use find() function?

One more point I wanted to make, same should be the case with map when
we use something like
m["somestring"]
? So what to do in such case where find and above kind of syntax is
undefined???

[Ian Collins]

S S wrote:

On May 6, 2:45 pm, Ian Collins <[e-mail]:

>Jim Langston wrote:

>>I believe it's undefined behavior. You have the constant "ephemeral" in
your program twice. Once for the char array, once for the parameter of the
find. The compiler probably sees that they are exactly the same, so instead
of making 2 it just makes one and uses the same pointer for both.

>That does not matter, note the use of the second template argument of
std::set.

Please trim and don't quote signatures.

>
Ian,

You wanted to explain something? I did not get you, sorry. Could you
elaborate please?

I was pointing out to Jim that you had provided your own less object, so
there wasn't any UB.

--
Ian Collins.

[S S]

Dizzy, Ian

May be I am missing something, but my statement
strcmp(s1, s2) < 0
will give me the expression

return 0 < 0;

which is FALSE. Am I correct?

if (0 < 0)
cout << "Its true";
else
cout << "Its false";

It prints, Its false.

Thanks in advance.

[James Kanze]

On May 6, 11:58 am, Ian Collins <[e-mail]:

S S wrote:

I have a very basic question, but it's a good one. Below is
the code fragment.

struct ltstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) < 0;
}
};

int main()
{
const int N = 6;
const char* a[N] = {"isomer", "ephemeral", "prosaic",
"nugatory", "artichoke", "serif"};
set<const char*, ltstrA(a, a + N);
if (A.find("ephemeral") != A.end())
cout << "Found";
else
cout << "Not found";
return 0;
}

Output will be -"Found"
My question is , Why?

How it is able to compare a const char* with another const char* to
find that value? I did not specify any equality operator? I just
mentioned strcmp(s1, s2) < 0
which means, when strcmp(s1, s2) == 0 (in case of match)
it will return false. So how set/map are able to find the const char*
value?

Given an ordered set, A < B < C and a search item X,

if (X < C) and !(B < X) then X is equivalent to B.

The issue in std::set is a bit more complicated, because the
domain may include elements which are not members of std::set.
Basically, set<>::find first locates an element i such that for
all previous elements j, j < x, and i for i, !(i < x) (which
implies that the same holds for all following elements, of
course). Having found this i, if !(x < i) determines whether
the elements are equivalent or not: if !(i < x) && !(x < i), the
elements are considered to be equivalent.

Note the "considered to be". You can easily define an operator<
which is inconsistent with ==. (He has, in fact: his ltstr is
inconsistent with == over char const*. Of course, if he were
also interested in ==, he'd define an eqstr, which returned
strcmp(s1, s2) == 0.)

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]

[dizzy]

S S wrote:

Dizzy, Ian

May be I am missing something, but my statement
strcmp(s1, s2) < 0
will give me the expression

return 0 < 0;

which is FALSE. Am I correct?

Correct.

>
if (0 < 0)
cout << "Its true";
else
cout << "Its false";

It prints, Its false.

So? I said 2 elements are equivalent iff (!(elem1 < elem2) && !(elem2 <
elem1)). Let's take your example, let's compare "a" and "b" so we have
!(strcmp("a", "b")<0) && !(strcmp("b", "a")<0) which means false && true
which yields false so "a" and "b" are not equivalent, BUT, let's take "a"
and "a" and we have:
!(strcmp("a", "a")<0) && !(strcmp("a", "a")<0) which is "true && true" which
is true so "a" and "a" are equivalent elements acording to your given
predicate (strcmp(x,y) < 0).

--
Dizzy

[terminator]

On May 6, 1:28*pm, S S <[e-mail]:

Hi

I have a very basic question, but it's a good one. Below is the code
fragment.

struct ltstr
{
* bool operator()(const char* s1, const char* s2) const
* {
* * return strcmp(s1, s2) < 0;
* }

};

int main()
{
* const int N = 6;
* const char* a[N] = {"isomer", "ephemeral", "prosaic",
* * * * * * * * * * * "nugatory", "artichoke", "serif"};
* set<const char*, ltstrA(a, a + N);
* if (A.find("ephemeral") != A.end())
* * cout << "Found";
* else
* * cout << "Not found";
* return 0;

}

Output will be -"Found"
My question is , Why?

How it is able to compare a const char* with another const char* to
find that value? I did not specify any equality operator? I just
mentioned strcmp(s1, s2) < 0
which means, when strcmp(s1, s2) == 0 (in case of match)
it will return false. So how set/map are able to find the const char*
value?

(a==b)==((!(a<b))&&!(b<a))

regards,
FM

[S S]

On May 6, 5:28 pm, James Kanze <[e-mail]:

On May 6, 11:58 am, Ian Collins <[e-mail]:

S S wrote:

I have a very basic question, but it's a good one. Below is
the code fragment.
struct ltstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) < 0;
}
};
int main()
{
const int N = 6;
const char* a[N] = {"isomer", "ephemeral", "prosaic",
"nugatory", "artichoke", "serif"};
set<const char*, ltstrA(a, a + N);
if (A.find("ephemeral") != A.end())
cout << "Found";
else
cout << "Not found";
return 0;
}
Output will be -"Found"
My question is , Why?
How it is able to compare a const char* with another const char* to
find that value? I did not specify any equality operator? I just
mentioned strcmp(s1, s2) < 0
which means, when strcmp(s1, s2) == 0 (in case of match)
it will return false. So how set/map are able to find the const char*
value?

Given an ordered set, A < B < C and a search item X,
if (X < C) and !(B < X) then X is equivalent to B.

The issue in std::set is a bit more complicated, because the
domain may include elements which are not members of std::set.
Basically, set<>::find first locates an element i such that for
all previous elements j, j < x, and i for i, !(i < x) (which
implies that the same holds for all following elements, of
course). Having found this i, if !(x < i) determines whether
the elements are equivalent or not: if !(i < x) && !(x < i), the
elements are considered to be equivalent.

Note the "considered to be". You can easily define an operator<
which is inconsistent with ==. (He has, in fact: his ltstr is
inconsistent with == over char const*. Of course, if he were
also interested in ==, he'd define an eqstr, which returned
strcmp(s1, s2) == 0.)

--
James Kanze (GABI Software) email:[e-mail]
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]

Thanks James. It was a really nice explanation, I was linking my ltstr
operator with the find function. find has it's own searching algorithm
as you mentioned, no matter what operator I provide. My operator is
used for arranging the tree while insertion.
There is no meaning providing eqstr operator for set, it defies it's
purpose. I won't be able to add any other element (which differs from
first) to the set except the first one.

[Andrew Koenig]

"S S" <sa***********@gmail.comwrote in message
news:7c**********************************@a23g2000 hsc.googlegroups.com...

How it is able to compare a const char* with another const char* to
find that value? I did not specify any equality operator? I just
mentioned strcmp(s1, s2) < 0

Associative containers never use equality operators when they search -- they
always use < (or its equivalent, whatever its name might be).

The idea is that if a < b and b < a are both false, a and b are presumed to
be equal.