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

或类似的东西。

Answer 2

根据cppreference.com：

A binary predicate that takes two arguments of the same type as the elements and returns a bool. The expression comp(a,b), where comp is an object of this type and a and b are key values, shall return true if a is considered to go before b in the strict weak ordering the function defines.

你的比较器没有这样做。

Answer 3

关于事物理论方面的更多信息：

根据 documented requirements for std::set's comparator (and every other "less-than comparator" in the standard library), it needs to establish a strict weak ordering:

所有 a、comp(a,a) == false
如果comp(a,b) == true那么comp(b,a) == false
如果 comp(a,b) == true 和 comp(b,c) == true 那么 comp(a,c) == true

为了简短起见，我省略了不可比性要求的传递性，它由 cppreference 文档中的 equiv 表达式处理，但请注意，以上三个还不够。

您可以将比较视为提问 "Must a come before b?" 实施假设这是比较所问的问题，并且对相等元素的回答是否定的，一个不能出现在另一个之前。您的比较器未通过前两个测试：

comp(0,0) returns true
comp(1,2)returnstrue，但是comp(2,1)returnsfalse

这不是任意的。为简单起见，想象一个朴素的排序数组。您有 3 1 并想要插入 2。从头开始，您检查 comp(2,1)。它 returns true 因为两者具有相同的位数，所以你已经完成了，现在你有 2 3 1。显然，这是不正确的。这并不是说 std::set 与排序数组相同，但它需要 something 来确定放置和查找元素的位置。严格的弱排序使这个过程保持一致。

您真正想要的降序 popcount 排序是严格大于比较。因此，更改是微不足道的：

return sz(a) > sz(b);

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

std::set operations with custom comparator

c++

std

stdset

c++11