How does std::map know when two keys are equal when using a custom comparator?

Question

struct StrCmp {
   bool operator()(char const *a, char const *b) const
   {
      return std::strcmp(a, b) < 0;
   }
};
    
// StrCmp specified in map declaration
map<const char *, int, StrCmp> strMap;
char p[] = "Test";
strMap[p] = 5;
cout << strMap["Test"];

In the code above the output is 5... How does the map know that the strings are equal ? The comparator only gives information that the strcmp value is greater.

When neither value is greater (or less) than the other, the `std::map` can assume that they are eqivalent. — Drew Dormann, Mar 10 '22 at 20:37
And this is why your comparator must provide [strict weak ordering](https://stackoverflow.com/questions/979759/operator-and-strict-weak-ordering). If it doesn't, `std::map` will get confused. — Paul Sanders, Mar 11 '22 at 00:09

score 2 · Accepted Answer · answered Mar 10 '22 at 21:18

Per the std::map documentation on cppreference.com:

std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare. Search, removal, and insertion operations have logarithmic complexity. Maps are usually implemented as red-black trees.

Everywhere the standard library uses the Compare requirements, uniqueness is determined by using the equivalence relation. In imprecise terms, two objects a and b are considered equivalent (not unique) if neither compares less than the other: !comp(a, b) && !comp(b, a).

How does std::map know when two keys are equal when using a custom comparator?

1 Answers1