Is there any way of comparing two different priority Queues in C++?

Question

I tried using the "==" operator but it didn't work; it works for a normal queue so why isn't working for priority queue?

My code is:

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

This is giving the error:

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

So, is there any way of doing it; and, if there is, what will be it's time complexity?

Answer 1

As you have discovered, the std::priority_queue container doesn't have an == operator … but its underlying container (a std::vector<int>, in your case) does have that operator. I think other potential underlying container classes will also have that operator (std::deque, the other 'common' one, does have it).

In your priority_queue, that underlying container will be the data member, c; however, it is a protected member, so cannot be directly accessed from your main function.

What you could do, here, is make a very simple 'wrapper class' derived from std::priority_queue (which will be able to access the .c member) and write a friend comparison operator for that wrapper. The time complexity of this operator==() will be that of the operator for the underlying container; for a std::vector or std::deque, that will be linear (in the size of the container) if the two containers have the same size.

Here's a short example and demo:

#include <iostream>
#include <queue>

template <typename T>
class pq_wrapper : public std::priority_queue<T> {
public:
    template<typename U>
    friend bool operator==(const pq_wrapper<U>& lhs, const pq_wrapper<U>& rhs);
};

template<typename U>
bool operator==(const pq_wrapper<U>& lhs, const pq_wrapper<U>& rhs)
{
    return lhs.c == rhs.c;
}

int main()
{
    pq_wrapper<int> q1; q1.push(1); q1.push(2);
    pq_wrapper<int> q2; q2.push(3); q2.push(2);
    pq_wrapper<int> q3; q3.push(3); q3.push(2);
    std::cout << (q1 == q2 ? "true" : "false") << "\n"; // "false"
    std::cout << (q3 == q2 ? "true" : "false") << "\n"; // "true"
    return 0;
}

---

Related Q/A on other ways of accessing the .c member: Is there a way to access the underlying container of STL container adaptors?

Note: It is not normally a good idea to derive classes or templates from STL containers; however, in this case, it is a very trivial derived class and is unlikely to cause other issues.

---

EDIT: As pointed out in the comment from pjs, the underlying container of a priority queue need only be partially ordered. Thus, for a max-sorted example with the elements, 8, 9 and 10, both [10, 9, 8] and [10, 8, 9] are valid representations – depending on the order of insertion.

Thus, using the trivial comparison operator I have defined above, the following code will output false:

int main()
{
    pq_wrapper<int> q1; q1.push(10); q1.push(9); q1.push(8);
    pq_wrapper<int> q2; q2.push(10); q2.push(8); q2.push(9);
    std::cout << (q1 == q2 ? "true" : "false") << "\n";
    return 0;
}

To fix this to make the comparison more strictly correct, you will need to sort the underlying container. Here is a version of the operator==() that does that (after first making a trivial size-equality check):

#include <algorithm>
template<typename U>
bool operator==(const pq_wrapper<U>& lhs, const pq_wrapper<U>& rhs)
{
    if (lhs.size() != rhs.size()) return false; // Different sizes: not equal!
    decltype(lhs.c) l = lhs.c;  std::sort(l.begin(), l.end(), std::less<U>());
    decltype(rhs.c) r = rhs.c;  std::sort(r.begin(), r.end(), std::less<U>());
    return l == r;
}