Broken STL implementation?

[Christopher Benson-Manica]

Is my implementation correct to print only a blank line when the
following program is compiled and run?

#include <iostream>
#include <map>

int main()
{
std::map< const char *, std::string > m;
m["foo"]="bar";
std::cout << m["foo"] << std::endl;
return 0;
}

g++ prints "bar", which is of course the behavior I want. If this is
a(nother) problem with my implementation, what, if anything, can I do
to work around it?

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.

[Victor Bazarov]

Christopher Benson-Manica wrote:

Is my implementation correct to print only a blank line when the
following program is compiled and run?

#include <iostream>
#include <map>

int main()
{
std::map< const char *, std::string > m;
m["foo"]="bar";
std::cout << m["foo"] << std::endl;
return 0;
}

g++ prints "bar", which is of course the behavior I want. If this is
a(nother) problem with my implementation, what, if anything, can I do
to work around it?

There is no guarantee that the first "foo" and the second "foo" are
the same constant string. Both implementations are, therefore, correct.

The work-around is to ensure that you're passing the same pointer value
both times:

int main()
{
..
const char *pfoo = "foo";
m[pfoo] = "bar";
std::cout << m[pfoo] << std::endl;
}

Victor

[tom_usenet]

On Wed, 18 Aug 2004 16:09:02 +0000 (UTC), Christopher Benson-Manica
<at***@nospam.cyberspace.org> wrote:

Is my implementation correct to print only a blank line when the
following program is compiled and run?

#include <iostream>
#include <map>

int main()
{
std::map< const char *, std::string > m;
Ok, so your map is flawed already - you can't < compare pointer values
unless those pointers point into the same object (or array).
m["foo"]="bar";
std::cout << m["foo"] << std::endl;
The second "foo" may or may not have the same address as the first one
- it's unspecified. So that may or may not have undefined behaviour
(which is what you're seeing).
return 0;
}

g++ prints "bar", which is of course the behavior I want. If this is
a(nother) problem with my implementation, what, if anything, can I do
to work around it?

I think you way to have the map sorted according to the contents of
the string, not the pointer value? If so, then you need something
like:

#include <cstring>

struct strcmper
{
typedef bool result_type;
typedef const char* first_argument_type;
typedef const char* second_argument_type;
bool operator()(const char* lhs, const char* rhs) const
{
return std::strcmp(lhs, rhs) < 0;
}
};

//...
std::map< const char *, std::string, strcmper > m;

Tom

[Kai-Uwe Bux]

Christopher Benson-Manica wrote:

Is my implementation correct to print only a blank line when the
following program is compiled and run?

#include <iostream>
#include <map>

int main()
{
std::map< const char *, std::string > m;
m["foo"]="bar";
std::cout << m["foo"] << std::endl;
return 0;
}

g++ prints "bar", which is of course the behavior I want. If this is
a(nother) problem with my implementation, what, if anything, can I do
to work around it?

This is not a problem with your library. The following code will yield a
blank line with g++, and I venture to say, on any standard complient
compiler:

#include <iostream>
#include <map>

int main()
{
char foo1 [4] = "foo";
char foo2 [4] = "foo";
std::map< const char *, std::string, std::less< const char * > m;
m[foo1]="bar";
std::cout << m[foo2] << std::endl;
return 0;
}

Back to your code:
std::map< const char *, std::string > m;

This is a bas idea: map operations will call operator< which is supposed to
be a weak total ordering. The standard makes no requirement that this holds
for comparision of const char *. Thus

std::map< const char *, std::string, std::less< const char * > m;

is better. However, it is clearly not what you want.

What happens is that your map m just stores a pointer to char and not a
copy of that string. Moreover, you donot compare the entries by their
values as strings but just by their address. Since foo1 and foo2 point to
different memory locations, the second programm prints a blank line. That
g++ prints "bar" for your code indicates that g++ folded the two occurences
of "foo" in your code to the same memory location: this tells us a little
bit about g++ handles string constants.

Recommendation: fix your code by using std::string for the keys in the map,
as well.
Best

Kai-Uwe

[Andre Kostur]

Christopher Benson-Manica <at***@nospam.cyberspace.org> wrote in
news:cf**********@chessie.cirr.com:

Is my implementation correct to print only a blank line when the
following program is compiled and run?
Yes.
#include <iostream>
#include <map>

int main()
{
std::map< const char *, std::string > m;
Keep in mind that this means that std::map is using std::less<const char
*> to determine equivalence. So the map will be comparing pointer
values, not what they're pointing _at_....
m["foo"]="bar";
This string literal "foo" lives at some memory location somewhere. Say,
0x00000004. So you're effectively doing:

m[reinterpret_cast<const char *>(0x00000004)] = "bar";
std::cout << m["foo"] << std::endl;
This string literal "foo" _may_ live at a different memory location.
Say, 0x00000008. So you're effectively doing:

m[reinterpret_cast<const char *>(0x00000008)] = "bar";

A different index than the first one....
return 0;
}

g++ prints "bar", which is of course the behavior I want. If this is
a(nother) problem with my implementation, what, if anything, can I do
to work around it?

Make your map: std::map<std::string, std::string>. A second alternative
is to supply your own comparison functor that knows to follow the pointer
to the actual string and compare those.

g++ is probably doing a string folding optimization where the compiler
notices that "foo" and "foo" are the same string literal, thus can share
the same memory location.

[Rob Williscroft]

tom_usenet wrote in news:kc********************************@4ax.com in
comp.lang.c++:

Ok, so your map is flawed already - you can't < compare pointer values
unless those pointers point into the same object (or array).

No, the map uses std::less< char const * > which is required to
handle such cases 20.3.3/8.

Rob.
--
http://www.victim-prime.dsl.pipex.com/

[David Hilsee]

"Kai-Uwe Bux" <jk********@gmx.net> wrote in message
news:cg**********@news01.cit.cornell.edu...
<snip>

std::map< const char *, std::string > m;
This is a bas idea: map operations will call operator< which is supposed

to be a weak total ordering. The standard makes no requirement that this holds for comparision of const char *. Thus

std::map< const char *, std::string, std::less< const char * > m;

is better. However, it is clearly not what you want.

<snip>

FYI, std::map's third template argument defaults to std::less<Key>. Your
"correction" is equivalent to the original code.

--
David Hilsee

[Kai-Uwe Bux]

David Hilsee wrote:

"Kai-Uwe Bux" <jk********@gmx.net> wrote in message
news:cg**********@news01.cit.cornell.edu...
<snip>

> std::map< const char *, std::string > m;

This is a bas idea: map operations will call operator< which is supposed

to

be a weak total ordering. The standard makes no requirement that this

holds

for comparision of const char *. Thus

std::map< const char *, std::string, std::less< const char * > m;

is better. However, it is clearly not what you want.

<snip>

FYI, std::map's third template argument defaults to std::less<Key>. Your
"correction" is equivalent to the original code.

Thanks!
Kai-Uwe Bux

[tom_usenet]

On 18 Aug 2004 21:11:57 GMT, Rob Williscroft <rt*@freenet.co.uk>
wrote:

tom_usenet wrote in news:kc********************************@4ax.com in
comp.lang.c++:

Ok, so your map is flawed already - you can't < compare pointer values
unless those pointers point into the same object (or array).

No, the map uses std::less< char const * > which is required to
handle such cases 20.3.3/8.

Interesting, I didn't realise that std::less ever did anything beyond
<.

Tom

[Ioannis Vranos]

Christopher Benson-Manica wrote:

Is my implementation correct to print only a blank line when the
following program is compiled and run?

#include <iostream>
#include <map>

int main()
{
std::map< const char *, std::string > m;
m["foo"]="bar";
std::cout << m["foo"] << std::endl;
return 0;
}

g++ prints "bar", which is of course the behavior I want. If this is
a(nother) problem with my implementation, what, if anything, can I do
to work around it?

The above is not a well-defined behaviour.Use map<string, string> instead.
The two string literals used, may have different addresses.


Regards,

Ioannis Vranos

http://www23.brinkster.com/noicys