使用自定义比较器的std :: set操作

Question

我有个问题.当我使用带有自定义比较器的std :: set时,其他操作(如erase或count)无法正常工作.例如:

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

输出将是:

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

我如何使用std :: set和自定义比较器,所有操作都正常工作？提前致谢.

Answer 1

尝试改变

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

同

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

(第一个)问题是比较器必须施加严格的弱排序.

所以,特别是,必须comp(a, a) == false为每一a个人std::set.

使用你的比较器你可以满足comp(a, a) == true每一个a.

无论如何:这只有在a != b暗示的情况下有效s(a) != s(b); 如果不是这样......好吧......我想你可以试试

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

或类似的东西.