Excessive Invocation of Copy Constructor for Custom Comparator Class in C++ Priority Queue

Question

I had declared a priority_queue with custom comparator having a vector property in it. Below is the full code for it:

CODE

#include <bits/stdc++.h>

using namespace std;

class Compare
{
private:
    vector<int> vec;

public:
    Compare(const vector<int> &vec) { this->vec = vec; }

    Compare(const Compare &obj)
    {
        this->vec = obj.vec;
        cout << "Copy Constructor Called!\n";
    }

    bool operator()(const int &left, const int &right)
    {
        return vec[left] > vec[right];
    }
};

int main(void)
{
    vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    priority_queue<int, vector<int>, Compare> pq{Compare(vec)};

    cout << "Pushing 1\n";
    pq.push(1);
    cout << "Pushed 1\n";
    cout << "Pushing 2\n";
    pq.push(2);
    cout << "Pushed 2\n";

    while (!pq.empty())
    {
        cout << "Popped = " << pq.top() << '\n';
        pq.pop();
    }
    return 0;
}

But the output is strange!!

OUTPUT

Copy Constructor Called!
Copy Constructor Called!
Copy Constructor Called!
Copy Constructor Called!
Pushing 1
Copy Constructor Called!
Copy Constructor Called!
Copy Constructor Called!
Pushed 1
Pushing 2
Copy Constructor Called!
Copy Constructor Called!
Copy Constructor Called!
Pushed 2
Popped = 1
Copy Constructor Called!
Copy Constructor Called!
Copy Constructor Called!
Copy Constructor Called!
Copy Constructor Called!
Popped = 2
Copy Constructor Called!

Why the copy constructor is called so many times, for every push and pop operation?

Also without any push or pop operation, when I just declared the priority_queue, the copy constructor is called 4 times

Why is this occurring? Isn't it correct that the priority_queue stores the comparator class object and utilizes it whenever comparisons are needed?

Answer 1

std::make_heap takes the comparator by value see, and so do numerous internal functions in the libstdc++ implementation of make_heap. libc++ does less passing by value, but it does some.

Comparators are supposed to be cheap to copy. If they need external data, make them store a pointer to external data.