How to compare structures

Question

I'm having difficulty setting the comparison correctly. Here is an example of my problem when my code mistakenly accepts {1,2} = {2,1}: http://ideone.com/i7huL

#include <iostream> #include <map> using namespace std; struct myStruct { int a; int b; bool operator<(const myStruct& rhs) const { return rhs.a < this->a && rhs.b < this->b; } }; int main() { std::map <myStruct, int> mymap ; myStruct m1={1,2}; myStruct m2={2,1}; mymap.insert(make_pair(m1,3)); std::map<myStruct, int>::iterator it1 = mymap.find(m1); std::map<myStruct, int>::iterator it2 = mymap.find(m2); cout << it1->second << it2->second; // here it1->second=it2->second=3, although I would have expected it2 to be equal to map.end(). } 

I could use || instead of & &, but I'm not sure if this is the right way. I just want the <operator to be implemented in such a way that I can find objects on my map without errors, as is the case with the code I'm associated with.

Thanks.

Answer 1

Yes, this operator implementation does not make much sense. I would recommend:

  bool operator<(const myStruct& rhs) const { return rhs.a < this->a || (rhs.a == this->a && rhs.b < this->b); } 

Answer 2

 bool operator<(const myStruct& rhs) const { if (a < rhs.a) return true; if (a == rhs.a) return b < rhs.b; return false; } 

If you are looking for a generalization for many data members, there is a great example using C ++ 11 std :: tie :

 struct S { int n; std::string s; float d; bool operator<(const S& rhs) const { return std::tie(n, s, d) < std::tie(rhs.n, rhs.s, rhs.d); } }; 

Answer 3

The problem is that your operator does not define a strict weak order . Think about how your example of {1,2} and {2,1} will go down in your statement. Suppose X = {1,2} and Y = {2,1} .

Is X <Y? Is 1 <2 and 2, 1? No, therefore X is not less than Y.

Is Y <x? Is 2 <1 and 1 <2? No, therefore Y is not less than X.

So, if X is not less than Y and Y is not less than X, what remains? They are equal.

You need to choose one of the members of your structure, either a or b , to be the main mapping. If the primary comparison leads to equality, then only you check the secondary comparison. Just as if you are in alphabetical order . First you check the first letter, and only if they are equal, you go to the next. An example of this is Hans Passant.

Here's a more serious example of a problem for your carrier. The one I gave above is not necessarily bad, because maybe you want {1,2} be considered equal to {2,1} . The main problem of crops with a set of such values: consider X = {1,1}, Y = {1,2}, Z = {2,2}

With your operator, X is finally less than Z, because 1 is less than 2. But X comes out equal to Y, and Y comes out equal to Z. To adhere to a strict weak order, if X = Y, and Y = Z, then X must equal Z. But here this is not true.

Answer 4

You asked about a generalization of the four members of int, here is how I would structure such code for maximum clarity.

 bool operator<(const myStruct& rhs) const { if (a < rhs.a) return true; if (a > rhs.a) return false; if (b < rhs.b) return true; if (b > rhs.b) return false; if (c < rhs.c) return true; if (c > rhs.c) return false; if (d < rhs.d) return true; if (d > rhs.d) return false; return false; } 

You can easily extend such code as much as you like.

Answer 5

The simplest solution uses std::tie to compare tuples.

 return std::tie(rhs.a, rhs.b) < std::tie(a, b); 

This very quickly and simply summarizes the data.

Answer 6

I prefer to write this by comparing elements for equality until two different values ​​are found:

 bool operator<(const myStruct& rhs) const { if (a != rhs.a) return a < rhs.a; if (b != rhs.b) return b < rhs.b; return false; // this and rhs are equal. } 

I find this clearer and more extensible than writing a single expression with a mixture of || and && (according to @HansPassant) and more compact than the @jahhaj approach, when each passing test leads to return true; or return false; . The performance is about the same if you do not know something about the distribution of values. There is an argument about avoiding operator==() and just using operator<() , but this only applies if you are trying to write the most generic boilerplate code.

Answer 7

The problem is that you need to know what your structure represents. Otherwise, the definition of <operator will simply become arbitrary. Others will not be able to give you a suitable answer. Take an example when your structure is the mapped coordinate of a point in 2D. In this case, you can define a meaningful ordering operator, such as the distance from the origin for the structure.

ie, distance d1 = this-> a * this-> a + this-> b * this-> b distance d2 = rhs.a * rhs.a + rhs.b * rhs.b if (d1 <d2) return true ; else return false;