std::set operations with custom comparator

Question

I have a question. When I'm using a std::set with custom comparator, other operations like erase or count doesn't work properly. For example:

int sz(int const & n) {
  return __builtin_popcount(n);
}

struct comp {
  bool operator()(int const & a, int const & b) const {
    return sz(a) >= sz(b);
  }
};

void solve() {
  set<int, comp> s;

  for (int i = 0; i < 10; ++i)
    s.insert(i);

  for (int x : s)
    cerr << x << " ";

  cerr << "\n";

  for (int i = 0; i < 10; ++i)
    cerr << s.count(i) << " ";
}

Output will be:

7 9 6 5 3 8 4 2 1 0
0 0 0 0 0 0 0 0 0 0

How I might use std::set with custom comparator, that all operations work properly? Thanks in advance.

Answer 1

Try changing

struct comp {
  bool operator()(int const & a, int const & b) const {
    return sz(a) >= sz(b);
  }
};

with

struct comp {
  bool operator()(int const & a, int const & b) const {
    return sz(a) > sz(b);
  }  // ---------^ 
};

The (first) problem is that a comparator must impose a strict weak ordering.

So, in particular, must be comp(a, a) == false for every a in the std::set.

With your comparator you have comp(a, a) == true for every a.

Anyway: this works only if a != b imply s(a) != s(b); if this isn't the case... well... I suppose you can try with

struct comp {
  bool operator()(int const & a, int const & b) const {
    return (sz(a) > sz(b)) || ((sz(a) == sz(b)) && (a > b));
  }
};

or something similar.