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

Time:03-11

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.

CodePudding user response:

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).

  •  Tags:  
  • c
  • Related