CODEWITHSUNDEEP
c++
NaomiJO
NaomiJO

Reputation: 343

how to compare structs

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.

Upvotes: 6

Views: 29804

Answers (7)

Brangdon
Brangdon

Reputation: 667

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

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 mix of || and && (as per @HansPassant), and more compact than @jahhaj's approach of having each passing test lead to a return true; or return false;. Performance is about the same, unless you know something about the distribution of values. There is an argument for avoiding operator==() and just using operator<(), but that only applies if you are trying to write maximally generic template code.

Upvotes: 1

Benjamin Lindley
Benjamin Lindley

Reputation: 103693

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.

Upvotes: 5

juanchopanza
juanchopanza

Reputation: 227390

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);
    }
};

Upvotes: 8

Puppy
Puppy

Reputation: 146910

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.

Upvotes: 1

PermanentGuest
PermanentGuest

Reputation: 5331

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;

Upvotes: 0

jahhaj
jahhaj

Reputation: 3119

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.

Upvotes: 3

Hans Passant
Hans Passant

Reputation: 941327

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);
  }

Upvotes: 8

Related Questions