用自定义比较器设置操作STD ::设置操作

Question

我有一个问题。当我使用具有自定义比较器的std ::设置时，其他操作（例如擦除或计数）无法正常工作。例如：

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 ::与自定义比较器的设置，所有操作都可以正常工作？预先感谢。

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

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

根据std::set的比较器的记录要求（以及标准库中的所有其他"比较不相比"），它需要建立一个严格的弱点：

• 对于所有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与排序的数组相同，但是在弄清楚放置在哪里和找到元素时，它需要某些东西。严格的较弱的订购使这一过程保持一致。

您真正追求的下降爆米花订购是严格的比较。因此，更改是微不足道的：

return sz(a) > sz(b);

Answer 3

根据cppreference.com：

一个二进制谓词，该谓词采用了与元素相同类型的两个参数并返回bool。表达式comp（a，b），其中comp是这种类型的对象，而a和b是钥匙值，如果考虑a在严格的弱排序中的b之前，应返回true。

您的比较器不执行此操作。