std::map< MyString, MyString > comparison operator?

J

jstanforth

This is probably a very obvious question, but I'm not clear on what
operators need to be implemented for std::map.find() to work. For
example, I have a class MyString that wraps std::string, and which also
implements ==, <, <=, >, >=, etc. (Those operators are tested and
working correctly.)

If I assign map["hello"] = "world", it saves the MyString's correctly
in the map. But a subsequent call to map.find("hello") returns
map.end(). Even more bizarre, a cout << on destruction suggests that a
subsequent map["hello"] = "something else" results in TWO items for
map["hello"]... How is that possible? I thought that was only a
behavior of multimap, but I suspect it's related to my MyString
implementation not handling comparisons properly.

Changing the map to < string, string > then works correctly, finds the
item, etc.

So the question is, what does <string> implement that <MyString> needs
in order to work as a Key in a std::map? Thanks in advance for your
help.
 
G

Gianni Mariani

jstanforth wrote:
....
So the question is, what does <string> implement that <MyString> needs
in order to work as a Key in a std::map? Thanks in advance for your
help.
Click to expand...

bool operator<( .. ) const

Is all you need to declare.

It sounds like you have a problem with your comparison operator or you
copy constructor.
 
M

Mark Van Peteghem

jstanforth said:
This is probably a very obvious question, but I'm not clear on what
operators need to be implemented for std::map.find() to work. For
example, I have a class MyString that wraps std::string, and which also
implements ==, <, <=, >, >=, etc. (Those operators are tested and
working correctly.)

If I assign map["hello"] = "world", it saves the MyString's correctly
in the map. But a subsequent call to map.find("hello") returns
map.end().
Click to expand...
In addition to what the other poster said, I suspect that you forgot
to define a copy constructor and/or operator= on your class MyString.
std::map makes copies of your objects, that’s why you need them,
That could explain why map.find(“hello”) returns map.end().
Even more bizarre, a cout << on destruction suggests that a
subsequent map["hello"] = "something else" results in TWO items for
map["hello"]... How is that possible? I thought that was only a
behavior of multimap, but I suspect it's related to my MyString
implementation not handling comparisons properly.
Click to expand...
It's normal that the destructor is called twice, because the second
assignment will destroy the first one, remember that the map has
copies.
 
?

=?ISO-8859-1?Q?=22Daniel_Kr=FCgler_=28ne_Spangenbe

Hello "jstanforth"
This is probably a very obvious question, but I'm not clear on what
operators need to be implemented for std::map.find() to work. For
example, I have a class MyString that wraps std::string, and which also
implements ==, <, <=, >, >=, etc. (Those operators are tested and
working correctly.)

If I assign map["hello"] = "world", it saves the MyString's correctly
in the map. But a subsequent call to map.find("hello") returns
map.end(). Even more bizarre, a cout << on destruction suggests that a
subsequent map["hello"] = "something else" results in TWO items for
map["hello"]... How is that possible? I thought that was only a
behavior of multimap, but I suspect it's related to my MyString
implementation not handling comparisons properly.

Changing the map to < string, string > then works correctly, finds the
item, etc.

So the question is, what does <string> implement that <MyString> needs
in order to work as a Key in a std::map? Thanks in advance for your
help.
Click to expand...
You should provide a complete (short) test program, otherwise the
community has no chance to
help you. From your description it seems, there could be many reasons of
error. A a simple list
of possibilities:

1) You have specialized std::less for your MyString class in a way
violating strictly weak ordering
requirements.
Note: This functor is used in std::map, if you don't provide a
special comparator. The standard
implementation of std::less<MyString> operator() will use operator<.
2) At least your implementation of operator< of your MyString class does
not work correctly, although
you claim it should work. This cannot be argued without its
implementation, but you can easily test it:
Just ensure that it obeys the strictly weakly comparable
requirements, which are:
(a) (x < x) == false
(b) if x < y, than !(y < x)
(c) if x < y and y < z than x < z
(d) Equivalence: If x and y are equivalent, than (x < y) == false
and (y < x) == false
3) Your test program causes undefined behaviour or tests the wrong thing.

Greetings from Bremen,

Daniel Krügler
 
J

Junker

jstanforth said:
This is probably a very obvious question, but I'm not clear on what
operators need to be implemented for std::map.find() to work. For
example, I have a class MyString that wraps std::string, and which also
implements ==, <, <=, >, >=, etc. (Those operators are tested and
working correctly.)

If I assign map["hello"] = "world", it saves the MyString's correctly
in the map. But a subsequent call to map.find("hello") returns
map.end(). Even more bizarre, a cout << on destruction suggests that a
subsequent map["hello"] = "something else" results in TWO items for
map["hello"]... How is that possible? I thought that was only a
behavior of multimap, but I suspect it's related to my MyString
implementation not handling comparisons properly.

Changing the map to < string, string > then works correctly, finds the
item, etc.

So the question is, what does <string> implement that <MyString> needs
in order to work as a Key in a std::map? Thanks in advance for your
help.
Click to expand...

Have you implemented the assignment operator and copy constructor for
the MyString class? If you are storing MyString by value in the map
these are required.

The only operator required to store UDTs in an ordered container is
the < operator, which you have already defined. The other comparison
operators can be implemented in terms of these.
 
J

jstanforth

Thank you, each of you--- I really appreciate your generous help with
this. I was initially going to post a test example except that it
relies on the MyString definition, etc. and I don't see a manageable
(for you folks) way to attach files here without posting 7K of text
into a message (which is tough for you to read).

So for starters, perhaps I can just use excerpts where the problem
likely lies, namely the copy constructor and overloaded operator<. I'm
happy to email compilable source code to anyone interested or provide
any other information. But hopefully I'm just making some simple
mistake in these specific areas....

- Imagine XString as a class with std::string _container as a private
member.
- The copy constructor, operator<, and operator= are defined as
follows:

XString::XString(XString& str) :
_container( str._container )
{

};

bool XString::eek:perator<(const XString& str)
{
return (_container < str._container);
};

// assignment operator from a char*
XString& XString::eek:perator=(const char* cs)
{
_container = cs;
return *this;
};

// assignment operator from an STL std::string
XString& XString::eek:perator=(const std::string& str)
{
_container = str;
return *this;
};

// assignment operator from another XString
XString& XString::eek:perator=(const XString& str)
{
_container = str._container;
return *this;
};


Then the test code (in a main() block) looks like this:

map< XString, XString > xsmap;
map< XString, XString >::iterator xsmapItr;

XString t1("john");
XString t2("annakin");
XString t3("george");

xsmap["hello"] = "world";
xsmap[t1] = "adams";
xsmap[t2] = "skywalker";
xsmap[t3] = "lucas";
xsmap["john"] = "doe";
xsmap[t1] = "something else";

xsmapItr = xsmap.find("hello");

if ( xsmapItr == xsmap.end() )
cout << "xstring not found" << endl;

== OUTPUTS: xstring not found


for ( xsmapItr = xsmap.begin() ; xsmapItr != xsmap.end();
++xsmapItr )
cout << xsmapItr->first << " : " << xsmapItr->second << endl;

==OUTPUTS:
john : adams
hello : world
annakin : skywalker
george : lucas
john : something else
john : doe


cout << t1 << " < " << t2 << " : " << ( t1 < t2 ? true : false ) <<
endl;
cout << t1 << " < " << t3 << " : " << ( t1 < t3 ? true : false ) <<
endl;

cout << t2 << " < " << t1 << " : " << ( t2 < t1 ? true : false ) <<
endl;
cout << t2 << " < " << t3 << " : " << ( t2 < t3 ? true : false ) <<
endl;

cout << t3 << " < " << t1 << " : " << ( t3 < t1 ? true : false ) <<
endl;
cout << t3 << " < " << t2 << " : " << ( t3 < t2 ? true : false ) <<
endl;

==OUTPUTS:
john < annakin : 0
john < george : 0
annakin < john : 1
annakin < george : 1
george < john : 1
george < annakin : 0


So... note the correct results for the < tests, plus note that
iterating through the map shows three results for "john".... (ie. this
isn't a destruction-on-copy operation as a previous poster suggested,
but all three exist in the map simultaneously). But all assignments
and comparisons seem to work correctly, suggesting the copy constructor
and operator< are working as expected. Also, I have operators and
methods all provide for const char* cs, std::string& str, and XString&
str for all possible operations.

Thanks so much for your help with this. Hopefully I'm just missing
something obvious here...
 
A

Antoun Kanawati

jstanforth said:
Thank you, each of you--- I really appreciate your generous help with
this. I was initially going to post a test example except that it
relies on the MyString definition, etc. and I don't see a manageable
(for you folks) way to attach files here without posting 7K of text
into a message (which is tough for you to read).

So for starters, perhaps I can just use excerpts where the problem
likely lies, namely the copy constructor and overloaded operator<. I'm
happy to email compilable source code to anyone interested or provide
any other information. But hopefully I'm just making some simple
mistake in these specific areas....

- Imagine XString as a class with std::string _container as a private
member.
- The copy constructor, operator<, and operator= are defined as
follows:
Click to expand...
[snip]

I tried the following, using your source, and some minor mods.
And, it works just right. What compiler are you using?

Note:

1. The default constructor.
2. The 'const' operator<.
3. The 'const char *' constructor.
4. operator<< overload for ostream.

Copy and assignment were left pretty much as-is.

This is merely an algorithmic check; so, I didn't bother with
encapsulation at all.
--
A. Kanawati
(e-mail address removed)


#ifndef XString_dot_h_
#define XString_dot_h_

#include <string>
#include <iosfwd>

struct XString {
std::string _container;

XString();
XString(const XString &);
XString(const char *);

XString &operator=(const XString &);
XString &operator=(const std::string &);
XString &operator=(const char *);

bool operator< (const XString &) const;
bool operator< (const XString &);
};

inline XString::XString() : _container()
{
}

inline
XString::XString(const char *s) : _container(s)
{
}

inline
XString::XString(const XString& str) :
_container( str._container )
{

}

inline
bool XString::eek:perator<(const XString& str)
{
return (_container < str._container);
}

inline
bool XString::eek:perator<(const XString& str) const
{
return (_container < str._container);
}

// assignment operator from a char*
inline
XString& XString::eek:perator=(const char* cs)
{
_container = cs;
return *this;
}

// assignment operator from an STL std::string
XString& XString::eek:perator=(const std::string& str)
{
_container = str;
return *this;
}

// assignment operator from another XString
inline
XString& XString::eek:perator=(const XString& str)
{
_container = str._container;
return *this;
}

inline std::eek:stream &operator<<(std::eek:stream & o, const XString &str)
{
return o << str._container;
}

#endif
 
J

Joshua Lehrer

jstanforth said:
XString::XString(XString& str) :
_container( str._container )
{

};
Click to expand...

1: the proper form of a copy constructor is *usually*:

T::T(const T& rhs); // notice the const


2: do not name data members starting with an underscore. 17.4.3.1.2.1:

- Each name that contains a double underscore (_ _) or begins with an
underscore followed by an uppercase letter (2.11) is reserved to the
implementation for any use.

- Each name that begins with an underscore is reserved to the implementation
for use as a name in the global namespace.


I'd like to see your class definition. I suspect that either your
"_container" is declared static, or some other issue with the class
declaration.

Here is an idea for you. You should be able to create a very small class
XString. All you should need is the constructors (default, copy,
construct-from-const char*), and operator<. Then, your above test code
should work correctly.

Trim the class XString down as small as possible and repost the entire
class, declaration AND definition. We can then get to the bottom of your
problem.


joshua lehrer
factset research systems
NYSE:FDS
 
J

Joshua Lehrer

Antoun Kanawati said:
bool operator< (const XString &) const;
bool operator< (const XString &);
Click to expand...


Why the overloaded operator<? The first one should suffice.

joshua lehrer
factset research systems
NYSE:FDS
 
W

wade

jstanforth said:
bool XString::eek:perator<(const XString& str)
{
return (_container < str._container);
};
Click to expand...

Make this member const. If the map is doing a comparison with const
'this', then something else is being called. Perhaps XString has an
implicit conversion to const char * (in which case you are comparing
text locations, not values) or perhaps to something else (I've seen
string classes with implicit conversion to double).

Provide a complete listing of all your XString members (as tested) and
we may be able to figure this out.
 
A

Antoun Kanawati

Why the overloaded operator<? The first one should suffice.
Click to expand...

The second (non-const) is left-over from the original posting;
I didn't try to make the code elegant, or encapsulated; just
tweaked enough to compile and test.

The net result: I have no idea why maps are not working for the
OP.
 
A

Allan W

Joshua said:
2: do not name data members starting with an underscore. 17.4.3.1.2.1:

- Each name that contains a double underscore (_ _) or begins with an
underscore followed by an uppercase letter (2.11) is reserved to the
implementation for any use.
Click to expand...

Okay, the second character wasn't uppercase and there wasn't a double
underscore.
- Each name that begins with an underscore is reserved to the implementation
for use as a name in the global namespace.
Click to expand...

Okay, members are not in the global namespace.

It should be okay to use a name starting with _ as a member, provided
that
the next character is a digit or lowercase letter.
 
J

jstanforth

NICE CALL on making the member const! I'd already made a simplified
XString object with just the few members (used in the test case posted
a little earlier), and making this member const makes the sample output
EXACTLY as expected, no more duplicates. And yes, there is an implicit
conversion happening--- very good guess!

Thanks so much to everyone for your help... You guys are great. The
fact that you're debugging this abstractly and still finding the
problem I couldn't find is seriously impressive. (And I'd tried almost
all the suggestions except this one before even posting here, so I was
about ready to lose hope and code around it...) Thanks again.
 
W

wade

jstanforth said:
NICE CALL on making the member const!
Click to expand...

Glad to help. Before you get too happy, I strongly recommend that you
make sure you understand why std::basic_string has "c_str()" instead of
"operator const char*()" and also why its operator<() is a non-member
function.

I believe section 11 of TC++PL (3rd edition) has some pertinent
discussion.

Production quality SomeString classes that do provide operator const
char*(), will typically provide multiple operator<() declarations.
See, for example,
http://msdn.microsoft.com/library/d...98/html/_mfc_cstring_comparison_operators.asp
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

std::map<std::string,int> Problem 3
std::map get n max elements 6
Support Map<String, String> & Map<String, MyString> 12
Overhead of subscript operator for STL maps 17
map vs list performance 15
Initializing std::map Objects 9
What is wrong with reference into std::map? 10
Sorting an STL map 1

Members online

Total: 67 (members: 3, guests: 64)
Robots: 391

Forum statistics

Threads
473,994
Messages
2,570,222
Members
46,810
Latest member
Kassie0918

Latest Threads

Top