C++中如何比较两个priority_queue？为何==运算符不可用？

问题描述 #

尝试使用==运算符比较两个std::priority_queue时编译报错，但该运算符对普通std::queue有效。相关代码及报错信息如下：

测试代码 #

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    priority_queue<int> q1;
    priority_queue<int> q2;
    q1.push(1);
    q1.push(2);
    q2.push(3);
    q2.push(2);
    if(q1 == q2) cout<<"true";
    else cout<<"false";
    return 0;
}

编译报错 #

error: no match for ‘operator==’ (operand types are ‘std::priority_queue’ and ‘std::priority_queue’)

原因分析 #

std::queue默认以std::deque作为底层容器，标准库为std::queue重载了==运算符，直接调用底层容器的比较逻辑，因此可以直接使用。

但std::priority_queue的核心是维护堆结构，仅保证顶部元素优先级最高，内部元素的存储顺序不固定。标准库没有为其提供==等比较运算符重载，因为"相等"的定义存在歧义：是堆的存储结构完全一致？还是包含的元素集合完全相同？

可行的比较方法 #

如果需求是判断两个priority_queue包含的元素集合完全相同（数量、元素值均一致），可以采用以下可靠方法：

方法：复制队列后逐一弹出比较 #

复制原队列，循环弹出两个队列的顶部元素进行比较，直到其中一个队列为空。若所有弹出元素都相等，且最终两个队列都为空，则判定相等。

示例代码：

#include <iostream>
#include <queue>

using namespace std;

bool arePriorityQueuesEqual(priority_queue<int> q1, priority_queue<int> q2) {
    while (!q1.empty() && !q2.empty()) {
        if (q1.top() != q2.top()) {
            return false;
        }
        q1.pop();
        q2.pop();
    }
    return q1.empty() && q2.empty();
}

int main() {
    priority_queue<int> q1;
    priority_queue<int> q2;
    q1.push(1);
    q1.push(2);
    q2.push(2);
    q2.push(1);
    
    cout << (arePriorityQueuesEqual(q1, q2) ? "true" : "false") << endl;
    return 0;
}

时间复杂度 #

上述方法的时间复杂度为O(n log n)：复制队列需要O(n)时间（复制底层容器），每次弹出操作的时间复杂度是O(log n)，共执行n次弹出，总时间复杂度为O(n log n)。

内容的提问来源于stack exchange，提问作者Chinmay Agarwal