why would std::equal_to cause dynamic allocation?

Question

Consider the following simple example, where I am using std::equal_to to compare two std::pair<std::string, unsigned>. The operator new is overloaded so that it prints a message when allocations take place (live code here):

#include <functional>
#include <string>
#include <iostream>

// overloaded to see when heap allocations take place
void* operator new(std::size_t n)
{
    std::cout << "Allocating " << n << std::endl;
    return malloc(n);
}

int main()
{
    using key_type = std::pair<std::string, unsigned>;
    auto key1 = std::make_pair(std::string("a_______long______string______"), 1);
    auto key2 = std::make_pair(std::string("a_______long______string______"), 1);

    std::cout << "Finished initial allocations\n\n" << std::endl;

    std::equal_to<key_type> eq;
    eq(key1, key2); // how can this cause dynamic allocation???
}

The message I am seeing is

Allocating 31
Allocating 31
Finished initial allocations


Allocating 31
Allocating 31

You can see there are two allocations taking place when comparing key1 and key2. But why? std::equal_to's operator takes its arguments by const reference so no allocation should take place... what I am missing? Thanks.

Answer 1

It is because you make copies of the pairs.

The types of keyX are std::pair<std::string, int>. eq has has a function call operator for the arguments const std::pair<std::string, unsigned>&, const std::pair<std::string, unsigned>&. As the types do not match, the references cannot be bound to the arguments directly. However, int is implicitly convertible to unsigned and so given pair is implicitly convertible to the argument pair.

So, you implicitly create a pair of temporary arguments for the comparison. The creation of the temporary strings cause the memory allocation.

---

If you had used std::equal_to<> as the comparison operator, it would have not created copies as it deduces the argument types, and thus wouldn't have caused the conversion.