找不到具有自定义比较功能的 std::map 的键

Question

#include <cstdio>

#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct mycmp {
      bool operator()(const int &a, const int  &b) const {
          return abs(a) <= abs(b);
      }
};

int main(){
  map<int, int, mycmp> M1;
  map<int, int> M2;
  for(int i = 0; i < 5; i++) {
    M1[i]++;
    M2[i]++;
  }
  cout << (int)(M1.find(4) == M1.end()) << endl;
  cout << (int)(M2.find(4) == M2.end()) << endl;
  return 0;
}

以上代码的输出是

1
0

表示找不到M1的key 4，而M2可以找到4。但是当我使用迭代器像

一样迭代 M1 时，一切看起来都很好

for ( auto &x: M1) cout << x.first << " " << x.second << endl;

它输出

这似乎是由比较功能引起的，但为什么以及如何？

Answer 1

给定两个元素 a 和 b，比较器用于决定 a 是否应该在 b 之前。如果 comp(a,b) == true 则 a 出现在 b.

之前

同一元素不能放在其自身之前。但是，您的比较器需要这样做，因为 mycomp(a,a) == true.

更具体地说，比较器必须强加严格的弱排序。此处列出了限制条件：https://en.cppreference.com/w/cpp/named_req/Compare

它说：

For all a, comp(a,a)==false

If comp(a,b)==true then comp(b,a)==false

if comp(a,b)==true and comp(b,c)==true then comp(a,c)==true

你的比较器违反了前两个。请注意，比较器和排序根本不关心相等性。当然a==a，但即使不是这样（因为你的元素有一些奇数operator==）comp(a,a)也必须return false.

对 sort 或 std::map 使用不符合上面链接页面中列出的要求的比较器会导致未定义的行为。

找不到具有自定义比较功能的 std::map 的键

Cannot find a key of a std::map with customized compare function

c++

std