使用自定义比较器的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));
  }
};

或类似的东西。

Answer 2

更多关于理论方面的事情：

根据documented requirements的std::set比较器（以及标准库中的所有其他“小于比较器”），它需要建立一个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表达式处理的，但请注意，上述三个还不够。

你可以把这个比较想象为“必须a来到b之前？”实现假设这是比较要求的问题，并且相等元素的答案是否定的，一个不能出现在另一个之前。您的比较器未通过前两个测试：

• comp(0,0)返回true
• comp(1,2)返回true，但comp(2,1)返回false

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

对于下降的popcount排序，你真正想要的是一个严格大于比较。因此，改变是微不足道的：

return sz(a) > sz(b);

Answer 3

根据cppreference.com：

一个二元谓词，它接受与元素相同类型的两个参数并返回一个bool。表达式comp（a，b），其中comp是此类型的对象，a和b是键值，如果a被认为在函数定义的严格弱排序中的b之前，则返回true。

您的比较器不会这样做。