C++优先队列中自定义比较器类的复制构造函数过度调用问题

问题场景与代码 #

我声明了一个带有包含vector属性的自定义比较器的priority_queue，完整代码如下：

#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;
}

异常输出结果 #

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!

问题疑问 #

为何复制构造函数会被如此频繁调用，甚至每次push、pop操作都会触发？此外，仅声明priority_queue而不执行push或pop时，复制构造函数也被调用了4次。这是为什么？priority_queue不是应该存储比较器对象并在需要比较时才使用吗？

原因分析与解决方案 #

1. 初始化阶段的多次复制 #

当你用临时对象Compare(vec)初始化priority_queue时，STL容器的实现会多次拷贝这个比较器：

• 首先，临时对象会被复制到priority_queue内部存储的比较器实例中；
• 部分STL实现（比如GCC的libstdc++）在初始化底层vector容器时，内部辅助逻辑会额外触发几次比较器的拷贝，这是实现层面的细节。

2. push/pop操作触发复制的根源 #

priority_queue的push和pop需要维护堆结构（上浮、下沉），这些操作依赖比较器的operator()。你的STL实现可能每次调用比较器时都会拷贝一份对象，而非直接使用容器内存储的实例。这种设计早期是为了避免线程安全问题或简化逻辑，并非所有STL实现都会这样，但你的环境恰好采用了这种方式。

3. 优化方案：减少复制次数 #

• 让比较器持有vector引用：避免每次复制比较器时拷贝整个vector，同时要保证原vector的生命周期长于priority_queue；
• 添加移动构造函数：允许比较器被移动而非复制，降低开销；
• 用std::ref传递比较器：让priority_queue存储比较器的引用，彻底避免复制。

修改后的示例代码：

#include <bits/stdc++.h>

using namespace std;

class Compare
{
private:
    const vector<int>& vec; // 改为引用，避免vector拷贝

public:
    // 用初始化列表构造
    Compare(const vector<int>& vec) : vec(vec) {}

    // 提供移动构造函数
    Compare(Compare&& obj) noexcept : vec(obj.vec) {
        cout << "Move Constructor Called!\n";
    }

    // 禁用复制构造（引用类型的复制可能引发悬空引用）
    Compare(const Compare&) = delete;

    // operator()标记为const，符合STL对比较器的要求
    bool operator()(const int& left, const int& right) const
    {
        return vec[left] > vec[right];
    }
};

int main(void)
{
    vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    // 用std::ref传递比较器，避免复制
    priority_queue<int, vector<int>, Compare> pq{std::ref(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;
}

内容的提问来源于stack exchange，提问作者Neeraj-Kumar-Coder