#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;
}
the output of codes above is
1
0
which implies can't find the key 4 of M1, while 4 can be found in M2. But everything looks fine when I use an iterator to iterate M1 like
for ( auto &x: M1) cout << x.first << " " << x.second << endl;
it outputs
0 1
1 1
2 1
3 1
4 1
it seems to be caused by compare function, but why and how?
CodePudding user response:
Given two elements a
and b
the comparator is used to decide if a
should come before b
. If comp(a,b) == true
then a
comes before b
.
The same element cannot be placed before itself. Though, your comparator requires that, because mycomp(a,a) == true
.
More specifically the comparator must impose a strict weak ordering. The constraints are listed here: https://en.cppreference.com/w/cpp/named_req/Compare
It says:
- For all
a
,comp(a,a)==false
- If
comp(a,b)==true
thencomp(b,a)==false
- if
comp(a,b)==true
andcomp(b,c)==true
thencomp(a,c)==true
Your comparator violates the first two. Note that the comparator and sorting do not care at all about equality. Certainly a==a
, but even if this was not the case (because your elements have some odd operator==
) comp(a,a)
must return false
.
Using a comparator for sort
or for a std::map
that does not adhere to the requirements listed in the page linked above results in undefined behavior.