c++ - std::set 带有自定义比较器的操作

Question

我有一个问题。当我使用带有自定义比较器的 std::set 时，删除或计数等其他操作无法正常工作。例如:

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

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

因此，特别是 std::set 中的每个 a 都必须是 comp(a, a) == false。

使用比较器，每个 a 都有 comp(a, a) == true。

无论如何:这仅在 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));
  }
};

或类似的东西。