Pair equal operator overloading for inserting into set

Question

I am trying to add a pair<int,int> to a set. If a pair shares the same two values as another in the set, it should not be inserted.

Here's my non-working code:

typedef  std::pair<int, int> PairInt;

template<>
bool std::operator==(const PairInt& l, const PairInt& r) 
{
    return (l.first == r.first && l.second == r.second) ||
           (l.first == r.second && l.second == r.first);
}

int main()
{
    std::set<PairInt> intSet;
    intSet.insert(PairInt(1,3));
    intSet.insert(PairInt(1,4));
    intSet.insert(PairInt(1,4));
    intSet.insert(PairInt(4,1));
}

At the moment, the (4,1) pair gets added even though there is already a (1,4) pair. The final contents of the set are:

(1 3)
(1 4)
(4 1)

and I want it to be

(1 3)
(1 4)

I've tried putting breakpoints in the overloaded method, but they never get reached. What have I done wrong?

Answer 1

Sets are based on operator< (an ordering/equivalence relationship), not operator== (which is an equality relationship).

To do the thing that you are trying to do, use a custom comparator:

#include <set>
#include <utility>
#include <cassert>
typedef std::pair<int, int> PairInt;
PairInt normalize(const PairInt& p) {
    return p.second < p.first ? PairInt(p.second, p.first) : p;
}
struct Comparator {
    bool operator()(const PairInt& l, const PairInt& r) const {
        //Compare canonical forms of l and r.
        return normalize(l) < normalize(r);
    }
};

int main()
{
    std::set<PairInt, Comparator> intSet;
    intSet.insert(PairInt(1,3));
    intSet.insert(PairInt(1,4));
    intSet.insert(PairInt(1,4));
    intSet.insert(PairInt(4,1));
    assert(intSet.size() == 2);
}

Answer 2

You will need to provide a comparison function for seeing of one item is less than the other, not for determining if they are equal. Here is a complete example:

#include <utility>
#include <algorithm>
#include <set>
#include <iostream>

typedef  std::pair<int, int> PairInt;
typedef bool Compare(const PairInt &,const PairInt &);

bool compare(const PairInt &l,const PairInt &r)
{
  int lfirst = std::min(l.first,l.second);
  int rfirst = std::min(r.first,r.second);
  if (lfirst<rfirst) return true;
  if (rfirst<lfirst) return false;
  return std::max(l.first,l.second)<std::max(r.first,r.second);
}

int main()
{
  typedef std::set<PairInt,Compare*> IntSet;
  IntSet intSet(compare);
  intSet.insert(PairInt(1,3));
  intSet.insert(PairInt(1,4));
  intSet.insert(PairInt(1,4));
  intSet.insert(PairInt(4,1));
  for (IntSet::const_iterator i=intSet.begin(); i!=intSet.end(); ++i) { 
    std::cerr << i->first << "," << i->second << "\n";
  } 
}

Output:

1,3
1,4