Functors vs comparators

Question

I know that a functor is a function object, an overloading of () operator in a structure definition. Also the use of a functor in an algorithm seems pretty straight forward, just call this routine.

However I am not able to get a sense of comparators. Why are they used in the first place in a template argument.

Can someone please elaborate the difference between the two with a possible implementation of a template in STL like map

Edit :

I am looking for the answers to the following specifically

1. Why is that there was a need of comparator instead of a function object ( also comparators are more commonly observed in containers ? )
2. A possible implementation (non STL, i.e. in C++ code) of where a comparator is passed instead of a function object

Answer 1

You are right about the definition of a functor - although the word doesn't exist in the language Standard itself, so there might be some slight variation in how people use it.

There are many function or class templates in the Standard Library that will take some sort of callable object - this might be a functor, or a pointer to a function (really just a function, not a class with operator()).

A comparator is an object of a type that meets the Compare requirements - that is, a function or class object that can be called with two things and returns a bool, and in particular meets some mathematical requirements called strict weak ordering.

Essentially, this means a comparator is a functor that you can use to put some numbers in the right order. (Numbers, std::strings, Customers, whatever else, as long as there is a sensible consistent way to put them in order).

So a trivial example of using a functor might be:

void print(int i)
{
    std::cout << i << '\n';
}
// ...
std::for_each(std::begin(some_ints), std::end(some_ints), print);

but if you wanted to sort some Customers by their customer id, you could do it like this:

struct Customer {
    std::string surname;
    std::string given_name;
    std::uint64_t customer_id;
};
bool compareById(Customer const& first, Customer const& second)
    // this function meets the Compare requirements
{
    return first.customer_id < second.customer_id;
}
// ...
std::sort(std::begin(customers), std::end(customers), compareById);

Let's say you later want to sort the customers by their names - surname first, then given name if the surnames are identical, you could provide a different function:

bool compareByName(Customer const& first, Customer const& second)
{
    // std::tie is an idiomatic way to correctly sort on multiple values
    return std::tie(first.surname, first.given_name)
                < std::tie(second.surname, second.given_name);
}
std::sort(std::begin(customers), std::end(customers), compareByName);

---

I'm struggling to invent an example where you would need your comparator to be a class, but let's suppose you wanted to print out all the comparisons it does to a log file; then that file would need to be state stored by the object:

struct LoggingCustomerComparator {
    std::ostream& logFile;
    LoggingCustomerComparator(std::ostream& logFile) : logFile(logFile) {}
    bool operator()(Customer const& first, Customer const& second)
    {
        // assume we have an operator<< for Customer
        logFile << "Comparing: " << first << " and " << second << '\n';
        return first.customer_id < second.customer_id;
    }
};
// ...
using OrderId = std::uint64_t;
using LCC = LoggingCustomerComparator;
std::map<Customer, OrderId, LCC> latestCustomerOrder(LCC(std::clog));
//                          ^^^ type                 ^^^ construct object with the log file we want

---

The above illustrates how to use function templates that take a functor or comparator, but what if you want to write such a function template? Let's implement Bogosort, in the style of a Standard Library algorithm:

template <typename RandIt, typename Comp>
void bogosort(RandIt first, RandIt last, Comp comp)
{
    std::random_device rd;
    std::mt19937 g(rd());

    while ( !std::is_sorted(first, last, comp) ) {
        std::shuffle(first, last, g);
    }
}

To see how is_sorted might be implemented see here.