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.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

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.

bool operator<( .. ) const

Is all you need to declare.

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

jstanforth wrote:
[summary of snipped material]

        map<MyString, MyString> m;
        m["hello"] = "world";

        m.find("hello") returns m.end()

claim: operators <,>, etc... are implemented correctly and tested.

[end summary]

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

The template declaration looks like this:

        std::map<typename Key, typename Value,
                 typename Compare = std::less<Key>, ....>

std::less<Key>::operator()() is implemented as operator<().

The other relational operators are not necessary, since their results
can be derived from operator<'s results.

So, if your operator< is implemented correctly, and MyString implements
value semantics correctly, you should not be having trouble.

Try using std::map::insert() to add a few pairs; iterate through the
map to see what it thinks the order is.  Also, instrument your class
and the comparators to see what they're doing [or use the debugger].

Note: Operator[] is usually implemented [more-or-less] as follows:

    mapped_type &operator[](const key_type &k) {
        iterator i = find(k);
        if (i == end()) i = insert(i, value_type(k,  mapped_type()) );
         return i->second; // by reference, not by value
    }

-- 
A. Kanawati
NO.antounk.SPAM@comcast.net

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

jstanforth wrote:

>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().
>
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.
>  
>
It's normal that the destructor is called twice, because the second
assignment will destroy the first one, remember that the map has
copies.

-- 
  Mark dot Van dot Peteghem at q-mentum dot com
  http://www.q-mentum.com -- easier and more powerful unit testing

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Hello "jstanforth"

jstanforth schrieb:

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


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

"jstanforth" <jstanforth@gmail.com> wrote in message news:<1113168003.715211.106510@f14g2000cwb.googlegroups.com>...
> 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.

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.

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

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::operator<(const XString& str)
{
	return (_container < str._container);
};

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

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

// assignment operator from another XString
XString& XString::operator=(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...


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

jstanforth wrote:
> 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:
[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
NO.antounk.SPAM@comcast.net


#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::operator<(const XString& str)
{
      return (_container < str._container);
}

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

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

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

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

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

#endif

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

"jstanforth" <jstanforth@gmail.com> wrote in message
news:1113245877.450156.220960@o13g2000cwo.googlegroups.com...
> XString::XString(XString& str) :
> _container( str._container )
> {
>
> };
>

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



      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

"Antoun Kanawati" <antounk@comcast.net> wrote in message
news:HLWdnU-uFsmqgsbfRVn-uw@comcast.com...
>       bool operator< (const XString &) const;
>       bool operator< (const XString &);


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

joshua lehrer
factset research systems
NYSE:FDS



      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

jstanforth wrote:

> bool XString::operator<(const XString& str)
> {
> 	return (_container < str._container);
> };

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.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Joshua Lehrer wrote:
> "Antoun Kanawati" <antounk@comcast.net> wrote in message
> news:HLWdnU-uFsmqgsbfRVn-uw@comcast.com...
>
>>      bool operator< (const XString &) const;
>>      bool operator< (const XString &);

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

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. Kanawati
NO.antounk.SPAM@comcast.net

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Joshua Lehrer wrote:
> 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.

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.

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.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

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.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

jstanforth wrote:

> NICE CALL on making the member const!

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/default.asp?url=/library/en-us/vcmfc98/html/_mfc_cstring_comparison_operators.asp


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]