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?

Please provide a [mcve] as required, [`#include `](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h?r=Saves_AllUserSaves) automatically defeats that. — πάντα ῥεῖ, Apr 11 '23 at 16:32
[Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — Jesper Juhl, Apr 11 '23 at 16:35
Maybe replace your `#include ` with the more acceptable `#include ` to prevent further downvotes (and even maybe reverse the existing ones). — Adrian Mole, Apr 11 '23 at 17:04
`#include #include ` -- You have just included every single header in the C++ standard. Compared to `#include #include `, which includes two headers. Get used to knowing what headers to include -- if you rely solely on throwing everything into the mix by using `#include `, you really did not learn C++ properly, as the correct headers (at least most of them), should be known by rote if your goal is to be a C++ programmer worth anything. — PaulMcKenzie, Apr 11 '23 at 17:12
@PaulMcKenzie Sir I am very new to C++, so if I have to include various datatypes such as maps and vectors in my program then including them separately like `#include` or `#include` is a better practise than using `#include` ? — Chinmay Agarwal, Apr 11 '23 at 17:33
That's a huge yes. The more you include in a program the greater the possibility that you'll reuse a name and suffer for it. Either you get an ambiguity error when compiling or you run the risk of the wrong identifier being used and get unexpected behaviour at runtime. Normally this is mitigated by the `std` namespace, but you disable this protection with `using namespace std;`. The other downside is the more you include, the longer it takes to compile a file. Often bits/stdc++.h slows the build by about an order of magnitude, quickly chipping away at the time saved by only typing one include. — user4581301, Apr 11 '23 at 17:42
The `priority_queue` has no comparison operator, this for a good reason. `priority_queue` are usually implemented as a heap. At each access the heap rearrange its contents. So 2 heaps can have different orders, and finally can return the same sequence. Trying to effectively compare them would be a pain. — dalfaB, Apr 11 '23 at 18:49

Adrian Mole · Accepted Answer · 2023-04-13T08:22:54.457

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

Time complexity will be that of the underlying container's `==` operator. [I'm assuming `std::vector](https://en.cppreference.com/w/cpp/container/vector/operator_cmp#Complexity) — user4581301, Apr 11 '23 at 17:24
The underlying vector is a linear representation of a partially ordered tree, so order of storage is not unique for a given set of elements. Consequently, two PQ vectors can be valid representations the same priority queue while storing the elements at different indices. For example, [10, 9, 8] and [10, 8, 9] are both legitimate representations of a max-PQ containing the elements {8, 9, 10}. The actual internal order depends on the order of entries and deletions. — pjs, Apr 13 '23 at 05:20
@pjs Interesting (and valid) point. I'll need to think about this and see if there is a (relatively) easy way to correct my comparison function. — Adrian Mole, Apr 13 '23 at 07:56
@pjs - See edit. (I left the original, incorrect, version as a cautionary tale. But it may also be of *some* use in specific cases.) — Adrian Mole, Apr 13 '23 at 08:25

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

1 Answers1