Why the constructor of the map allow us to pass a comparator object in the parameter?

Question

#include <map>
#include <string>

class A_comparator
{
public:
    template <typename T>
    bool operator()(const T& lhs, const T& rhs) const
    {
        // Defines a custom ordering for the elements in the map
        // ...
    }
};

int main()
{
    A_comparator camp1;
    std::map<int, std::string, A_comparator> map1(camp1);

    map1[1] = "one";
    map1[2] = "two";
    map1[3] = "three";

    A_comparator camp2;
    std::map<int, std::string, A_comparator> map2(camp2);

    map2[1] = "one";
    map2[2] = "two";
    map2[3] = "three";

    // Prints elements in custom order based on their keys
    for (const auto& [key, value] : map1)
        std::cout << key << ": " << value << std::endl;

    std::cout << std::endl;

    for (const auto& [key, value] : map2)
        std::cout << key << ": " << value << std::endl;

    return 0;
}

In this example, two std::map objects, map1 and map2, are created and each is initialized with a different A_comparator object, camp1 and camp2, respectively. Both map1 and map2 use the A_comparator comparator to compare their keys, so they will both be ordered according to the custom ordering defined by the A_comparator class. using different A_comparator objects with std::map does not affect the behavior of the map.

So why the definition of the map could not be simply like:

....
typedef Compare    key_compare;
key_compare        _comp;
explicit map (): _comp(key_compare(){}
....

the code above will produce the same behavior.

Answer 1

I think the key point here to understand is that the type of the comparator is part of the type of the map. Hence, if you use a different type of comparator, it is a different type of map.

Now, sometimes you want to have the same type of map, but still use different ways of comparing the keys for different instances of the map. You cannot use a different type of comparator for two instances of the same type of map.

But, you can use different instances of the same type of comparator with different instances of the same type of map.

For example:

#include <iostream>
#include <map>

struct cmp {
    bool flipped = false;
    bool operator()(const int& a,const int& b) const { 
        if (flipped) return b < a;
        return a < b;
    }
};

void populate_and_print(std::map<int,int,cmp>& m){
    m[1] = 42;
    m[2] = 102;
    for (const auto& e : m) { std::cout << e.first << "\n"; }
}

int main() {
    auto m = std::map<int,int,cmp>(cmp{});
    populate_and_print(m);
    auto n = std::map<int,int,cmp>(cmp{true});
    populate_and_print(n);
}

Notice how populate_and_print does not need to be a template. m and n are both of the same type std::map<int,int,cmp>. The two instances of the comparator are of the same type cmp, but they compare differently.

If you would write a different comparator cmp2 then std::map<int,int,cmp> and std::map<int,int,cmp2> are two different types.

Also, if you use a plain function as the comparator, you must provide an instance. Consider:

  bool cmp1(const int& a,const int& b) { return a < b; }
  bool cmp2(const int& a,const int& b) { return b < a; }

The type of both functions is bool (const int&,const int&). You cannot default construct a free function. You need to pass a function pointer to the map's constructor.