how to compare structs

Question

I am having difficulties to set up the comparison correctly. Here is an example of my problem, where my code wrongly assumes {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 this is the correct way either. I just want to have operator< implemented in such a way that I am able to find objects in my map, without making any errors, as is the case in the code I linked to.

Thanks.

Answer 1

The problem is that your operator does not define a strict weak ordering. Think through your how your example of {1,2} and {2,1} would go down in your operator. Assume 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's left? They're equal.

You need to pick one of the members of your struct, either a or b to be the primary comparison. If the primary comparison results in equality, only then do you check the secondary comparison. Just like when you alphabetize something. First you check the first letter, and only if they are equal do you go on to the next. Hans Passant has provided an example of this.

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

With your operator, X is definitively less than Z, because 1 is less than 2. But X comes out equal to Y, and Y comes out equal to Z. In order to adhere to strict weak ordering, if X = Y, and Y = Z, then X should equal Z. But here that is not the case.

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

Yes, this operator implementation doesn't make much sense. I'd recommend:

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

Answer 4

You asked about generalising to four int members, here's 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 for as many data members as you wish.

Answer 5

Problem is that you need to know what your structure represents. Otherwise defining a < operator would just become arbitrary. Others won't be able to give you a fitting answer. Take an example where when your structure represents a cartisian coordinate of a point in 2D. In this case you could define a meaningful ordering operator such as the distance from the origin for the structure.

i.e, 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;

Answer 6

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

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

This generalizes very quickly and simply to more data members.