By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,232 Members | 1,679 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,232 IT Pros & Developers. It's quick & easy.

Broken STL implementation?

P: n/a
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.
Jul 22 '05 #1
Share this Question
Share on Google+
9 Replies


P: n/a
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
Jul 22 '05 #2

P: n/a
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
Jul 22 '05 #3

P: n/a
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
Jul 22 '05 #4

P: n/a
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.
Jul 22 '05 #5

P: n/a
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/
Jul 22 '05 #6

P: n/a
"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
Jul 22 '05 #7

P: n/a
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
Jul 22 '05 #8

P: n/a
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
Jul 22 '05 #9

P: n/a
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
Jul 22 '05 #10

This discussion thread is closed

Replies have been disabled for this discussion.