<set> with custom struct contains duplicates

Question

I've been learning c++. I am stuck with this problem.

I have set that contains a custom struct that contains two long int's a & b. I have a custom comparer struct that compares the numbers and returns true if either a or b is different.

typedef long int li;

struct number {
    number(li a1,li b1): a(a1), b(b1) {}
    li a, b;
};

struct compare {
    bool operator() (const number &lhs, const number& rhs) const{
        return lhs.a != rhs.a || lhs.b != rhs.b;
    }
};

int main() {
    set<number, compare> nums;
    nums.insert(number(1, 2));
    nums.insert(number(1, 1));
    nums.insert(number(2, 1));
    nums.insert(number(1, 2));
    for (auto &i : nums) {
        cout << i.a << " " << i.b << endl;
    }
    return 0;
}

The output here is

1 2

2 1

1 1

1 2

It has two entries of 1 2. Any clarification would be appreciated.

Answer 1

Your comparison function should return whether some element is smaller than another, not whether or not they are equal. (More formally, it must define a "Strict weak ordering" on the elements of your set.)

Use something like

struct compare {
    bool operator() (const number &lhs, const number& rhs) const{
        return std::tie(lhs.a, lhs.b) < std::tie(rhs.a, rhs.b);
    }
};

If you don't care about ordering, you may want to define a suitable hash function for your type and use std::unordered_set.

To avoid future problems like this, make sure to read the docs. They clearly explain what your comparison function is supposed to do.

For reference: std::tie as used above constructs tuples of references to its arguments which can then be compared lexicographically with <. This is an easy, generic and fast way to build some ordering for collections of less-than-comparable stuff.

Answer 2

Your comparison function needs to meet strict/weak ordering requirements.

(I actually prefer the answer using std::tie, but this may be more illustrative for newcomers)

bool compare(const number& lhs, const number& rhs)
{
   if(lhs.a < rhs.a)
      return true;
   else if(lhs.a > rhs.a)
      return false;
   else
      return lhs.b < rhs.b;
}