Home > Software engineering >  Cannot find a key of a std::map with customized compare function
Cannot find a key of a std::map with customized compare function

Time:04-01

#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 then comp(b,a)==false
  • if comp(a,b)==true and comp(b,c)==true then comp(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.

  • Related