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*, ltstr> A(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]

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*, ltstr> A(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.

 

[Ian Collins]

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*, ltstr> A(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.

 

[dizzy]

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*, ltstr> A(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?

By using your provided predicate.

I did not specify any equality operator?

It does not need to. And btw, it does not want to find equality, it wants to
find "equivalence", any good stdlib book will describe the difference
between the two. Basically, you check for equality with op==/!= and you
check for equivalence with an expression like iff (!(arg1 < arg2) && !(arg2
< arg1)) then arg1 and arg2 are equivalent for your given order predicate.

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?

See above.

 

[Ian Collins]

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*, ltstr> A(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.

 

[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*, ltstr> A(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,

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]

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*, ltstr> A(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,

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

 

[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*, ltstr> A(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?

By using your provided predicate.

I did not specify any equality operator?

It does not need to. And btw, it does not want to find equality, it wants to
find "equivalence", any good stdlib book will describe the difference
between the two. Basically, you check for equality with op==/!= and you
check for equivalence with an expression like iff (!(arg1 < arg2) && !(arg2
< arg1)) then arg1 and arg2 are equivalent for your given order predicate.

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?

See above.

Dizzy,

How does this strcmp(s1, s2) < 0 fitting in the equivalence theorem?
It will not return true in case they are equivalent.

 

[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*, ltstr> A(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,

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]

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]

Dizzy,

How does this strcmp(s1, s2) < 0 fitting in the equivalence theorem?
It will not return true in case they are equivalent.

It does not, reread the reply to see how the less than operator is used
to determine equivalence.

 

[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]

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*, ltstr> A(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.)

 

[dizzy]

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).

 

[terminator]

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*, ltstr> A(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]

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*, ltstr> A(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:[email protected]
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

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]

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.