Strict weak ordering

[bb]

#include <iostream>
#include <map>

using std::cout;
using std::endl;
using std::map;
using std:air;

struct myType {
int m1_;
int m2_;

myType(int m1, int m2) : m1_(m1), m2_(m2) {}
myType(const myType& rhs) : m1_(rhs.m1_), m2_(rhs.m2_) {}

~myType() {}

bool operator<(const myType& rhs) const {
if ((this->m1_ < rhs.m1_) && (this->m2_ < rhs.m2_)) { return true; }
return false;
}
};

int main(int argc, char* argv[]) {
typedef map<myType, int> myMap;

myType ky1(2,3);
myType ky2(3,2);

myMap mymap;

mymap.insert(myMap::value_type(ky1,10));
cout << mymap.size() << endl;

mymap.insert(myMap::value_type(ky2,11)); // updates instead of
inserting a second entry
cout << mymap.size() << endl;
}

In the above code, the objects ky1 & ky2 are obviously not the same.
(at least i do not intend them to be so). However, per strict weak
ordering, stl does assume they are equivalent. Hence, even after the
second insert, mymap.size() returns 1.

Is my operator<() implementation is wrong?

What all should ensure when I use my own type as a key in an
associative container?

Thanks in advance.

 

[AnonMail2005]

#include <iostream>
#include <map>

using std::cout;
using std::endl;
using std::map;
using std:air;

struct myType {
int m1_;
int m2_;

myType(int m1, int m2) : m1_(m1), m2_(m2) {}
myType(const myType& rhs) : m1_(rhs.m1_), m2_(rhs.m2_) {}

~myType() {}

bool operator<(const myType& rhs) const {
if ((this->m1_ < rhs.m1_) && (this->m2_ < rhs.m2_)) { return true; }
return false;
}

};

int main(int argc, char* argv[]) {
typedef map<myType, int> myMap;

myType ky1(2,3);
myType ky2(3,2);

myMap mymap;

mymap.insert(myMap::value_type(ky1,10));
cout << mymap.size() << endl;

mymap.insert(myMap::value_type(ky2,11)); // updates instead of
inserting a second entry
cout << mymap.size() << endl;

}

In the above code, the objects ky1 & ky2 are obviously not the same.
(at least i do not intend them to be so). However, per strict weak
ordering, stl does assume they are equivalent. Hence, even after the
second insert, mymap.size() returns 1.

Is my operator<() implementation is wrong?

What all should ensure when I use my own type as a key in an
associative container?

Thanks in advance.

I think the condition should be:
(this->m1_ < rhs.m1_) || ((this->m1_ == rhs.m1_) && (this->m2_ <
rhs.m2_))

 

[Pete Becker]

bool operator<(const myType& rhs) const {
if ((this->m1_ < rhs.m1_) && (this->m2_ < rhs.m2_)) { return true; }
return false;
}
};


myType ky1(2,3);
myType ky2(3,2);


In the above code, the objects ky1 & ky2 are obviously not the same.
(at least i do not intend them to be so). However, per strict weak
ordering, stl does assume they are equivalent. Hence, even after the
second insert, mymap.size() returns 1.

Your operator< says that they are equivalent, since neither one is less
than the other. If you don't want them to be equivalent you have to
figure out which one is less than the other, and then write operator<
to reflect that design decision.

 

[bb]

I think the condition should be:

(this->m1_ < rhs.m1_) || ((this->m1_ == rhs.m1_) && (this->m2_ <
rhs.m2_))

I do agree. However, if there are going to be more member variables,
then operator< is going to become unreadable. I guess there is a
simpler way?

Currently, am stringifying all the members (kind of object_id) and
using it in operator<. It seems to work... not sure if it is the
proper way.

Thanks anyway.

 

[Pete Becker]

I do agree. However, if there are going to be more member variables,
then operator< is going to become unreadable. I guess there is a
simpler way?

If the comparison involves all the members, then you have to write code
that looks at all the members. It's only unreadable if you write it
that way. <g>

Having said that, if you really do have complex objects that require a
total order, look at tr1's tuple. It does comparisons for you. (It's
also in std for the next standard, but your comiler probably doesn't do
that yet)

#include <tuple>

typedef std::tr1::tuple<int, int> my_type;

my_type obj1(2, 3);
my_type obj2(3, 2);

Now, obj1 < obj2 is well-defined, and obj2 < obj1 is also well-defined.
And that operator< defines a total ordering.

 

[Ben Pfaff]

I do agree. However, if there are going to be more member variables,
then operator< is going to become unreadable. I guess there is a
simpler way?

This kind of comparison chain is pretty readable:

if (lhs.a != rhs.a)
return lhs.a < rhs.a;
else if (lhs.b != rhs.b)
return lhs.b < rhs.b;
else if (lhs.c != rhs.c)
return lhs.c < rhs.c;
else if (lhs.d != rhs.d)
return lhs.d < rhs.d;
else
return false;

 

[bb]

This kind of comparison chain is pretty readable:

if (lhs.a != rhs.a)
return lhs.a < rhs.a;
else if (lhs.b != rhs.b)
return lhs.b < rhs.b;
else if (lhs.c != rhs.c)
return lhs.c < rhs.c;
else if (lhs.d != rhs.d)
return lhs.d < rhs.d;
else
return false;

I realized. Thanks Ben.

 

[bb]

Having said that, if you really do have complex objects that require a

total order, look at tr1's tuple. It does comparisons for you. (It's
also in std for the next standard, but your comiler probably doesn't do
that yet)

#include <tuple>

typedef std::tr1::tuple<int, int> my_type;

my_type obj1(2, 3);
my_type obj2(3, 2);

Now, obj1 < obj2 is well-defined, and obj2 < obj1 is also well-defined.
And that operator< defines a total ordering.

tuple really looks cool. Thanks Pete.