Type error in C++ when instantiating a priority_queue of int pairs with a custom comparator (to implement a min heap)

Question

Currently working through a leetcode problem for which I need a min Heap of pairs.
I am trying to use a priority_queue with int pairs and a custom compare type.
Attempts of implementation of the same have failed with the following error:

In file included from prog_joined.cpp:1: In file included from ./precompiled/headers.h:55: In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/queue:64: /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_queue.h:467:7: error: static_assert failed due to requirement 'is_same<int, std::pair<int, int>>::value' "value_type must be the same as the underlying container" static_assert(is_same<_Tp, typename _Sequence::value_type>::value, ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Line 9: Char 67: note: in instantiation of template class 'std::priority_queue<int, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int>>>, std::greater>' requested here priority_queue<int, vector<pair<int, int>>, greater> pq;

Here's the code with which I'm trying to implement the heap:

#include <queue>
#include <utility>
using namespace std;
//...
priority_queue<int, pair<int, int>, greater<int>> pq;

That code does not agree with the error message. Is your copy-and-paste broken? — molbdnilo
– molbdnilo, Commented Sep 6, 2022 at 7:38
There's more to the code but this is where the error message is pointing to. — Hemant Sharma
– Hemant Sharma, Commented Sep 6, 2022 at 7:43
A priority queue of pairs of int would begin std::priority_queue<std::pair<int, int>, ... and requires a comparator for such pairs. — molbdnilo
– molbdnilo, Commented Sep 6, 2022 at 7:43

wohlstad · Accepted Answer · 2022-09-10 16:31:06Z

2

As you can see in the std::priority_queue documentation:

The 1st template argument is the data type (should be pair<int,int> in your case).
The 2nd template argument should be the underlying container type used for the queue.
The 3rd should be the compare type.

For example if you want a priority_queue of int pairs that use std::vector as a container, you need:

std::priority_queue<std::pair<int, int>,                  // data type
                    std::vector<std::pair<int,int>>,      // container type
                    std::greater<std::pair<int,int>>> pq; // compare type

Note: as you can see here the std::pair implementation for comparison operators which are used by std::greater is:

Compares lhs and rhs lexicographically by operator<, that is, compares the first elements and only if they are equivalent, compares the second elements.

If this is not what you need you can implement your own compare type for std::pair<int,int>.

A side note: it is better to avoid using namespace std. See here: Why is "using namespace std;" considered bad practice?.

edited Sep 10, 2022 at 16:31

answered Sep 6, 2022 at 7:17

wohlstad

36k18 gold badges79 silver badges112 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Hemant Sharma Over a year ago

While searching the internet I came across an instance where a heap was implemented with priority_queue<pair<int, int>> and it seemed to work, according to the post. Any reason why that worked? Link to the post: geeksforgeeks.org/priority-queue-of-pairs-in-c-ordered-by-first

wohlstad Over a year ago

The default container is std::vector anyway. But the default compare type is std::less, so it should not behave as std::greater (if indeed what you need is std::greater).

Hemant Sharma Over a year ago

Hi, I really appreciate the help, I have another question: Tried implementing a min heap as shown below, but am still getting a compilation error. Is there something fundamental that I'm missing when trying to create a heap? priority_queue<pair<double, vector<int>>, pair<double, vector<int>>, greater<pair<double, vector<int>>>> pq;

wohlstad Over a year ago

The 2nd is the container type, so you need (with vector as container): priority_queue<pair<double, vector<int>>, vector<pair<double, vector<int>>>, greater<pair<double, vector<int>>>> pq;

wohlstad Over a year ago

@HemantSharma You should not modify your question after you've got a valid answer, so I will roll it back. If my last comment above did not help please post a new question.

|

Deepanshu Pandey · Accepted Answer · 2023-09-18 05:58:58Z

0

for this , If you are trying to implement a minheap and that to in pair using this might solve your problem as solving a leetcode problem i also faced similar issues

priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>>pq;

answered Sep 18, 2023 at 5:58

Deepanshu Pandey

1

Collectives™ on Stack Overflow

Type error in C++ when instantiating a priority_queue of int pairs with a custom comparator (to implement a min heap)

2 Answers 2

7 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

7 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related