Arup - 1 year ago 89

C++ Question

i Have been playing around with STL containers and the compare function/functors they supports, however i found priority_queue doesn't follow the usual strict weak ordering , i am trying to understand what might be the reason but not able to figure it out, any pointers would be helpful.

It also mentioned in this blog that priority_queue doesnt follow strict weak ordering. enter link description here

`#include "STL.h"`

#include "queue"

#include "vector"

#include "iostream"

#include "functional"

using namespace std;

typedef bool(*func)(const int& val1 , const int& val2);

bool strict_weak_order_function(const int& val1 , const int& val2){

return val1 > val2;

}

bool comparer_function(const int& val1 , const int& val2){

return !strict_weak_order_function(val1 , val2);

}

struct Compaper_functor{

bool operator()(const int& val1 , const int& val2){

return !strict_weak_order_function(val1 , val2);

}

};

void runPriorityQueue(void){

//priority_queue<int , vector<int> , func > pq(comparer_function);

priority_queue<int , vector<int> , Compaper_functor > pq;

int size;

cin >> size;

while(size--){

int val;

cin >> val;

pq.push(val);

}

while(!pq.empty()){

cout <<'\n'<< pq.top() << '\n';

pq.pop();

}

}

Answer Source

The problem is that the negation of your `strict_weak_order`

(that uses `>`

) is `<=`

and that is not a strict weak order. A strict weak order `R`

has to satisfy `x R x == false`

for all `x`

. However, `R`

equal to `<=`

yields `(x <= x) == true`

.

You need to reverse the order of arguments (which corresponds to `<`

) instead.

```
bool comparer_function(const int& val1 , const int& val2){
return strict_weak_order_function(val2 , val1);
}
struct Compaper_functor{
bool operator()(const int& val1 , const int& val2){
return strict_weak_order_function(val2 , val1);
}
};
```

Note however that a `std::priority_queue`

has a `std::less`

as default comparator, but **that gives a max-heap** (i.e. `[5, 4, 3, 2, 1]`

output from the same input), so to get a min-heap (i.e. with output `[1, 2, 3, 4, 5]`

from input `[5, 4, 3, 2, 1]`

) you need to pass `std::greater`

, see e.g. this:

```
#include <queue>
#include <iostream>
int main()
{
auto const v = std::vector<int> { 5, 4, 3, 2, 1 };
// prints 5 through 1
for (auto p = std::priority_queue<int> { v.begin(), v.end() }; !p.empty(); p.pop())
std::cout << p.top() << ',';
std::cout << '\n';
// prints 1 through 5
for (auto p = std::priority_queue<int, std::vector<int>, std::greater<int>> { v.begin(), v.end() }; !p.empty(); p.pop())
std::cout << p.top() << ',';
std::cout << '\n';
}
```