Почему priority_queue в STL не следует строгому слабому упорядочению?
Я поиграл с контейнерами STL и функцией сравнения / функторами, которые они поддерживают, однако я обнаружил, что priority_queue не следует обычному строгому слабому порядку, я пытаюсь понять, в чем может быть причина, но не в состоянии выяснить это, любой указатели были бы полезны.
В этом блоге также упоминается, что priority_queue не следует строгому слабому упорядочению. введите описание ссылки здесь
#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();
}
}
Решение
Проблема в том, что отрицание вашего strict_weak_order (который использует >) является <= и это не строгий слабый порядок. Строгий слабый порядок R должен удовлетворить x R x == false для всех x, Тем не мение, R равно <= доходность (x <= x) == true,
Вам необходимо изменить порядок аргументов (что соответствует <) вместо
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);
}
};
Обратите внимание, что std::priority_queue имеет std::less в качестве компаратора по умолчанию, но это дает максимальную кучу (Т.е. [5, 4, 3, 2, 1] выход с одного и того же входа), чтобы получить минимальную кучу (т.е. с выводом [1, 2, 3, 4, 5] от ввода [5, 4, 3, 2, 1]) тебе нужно пройти std::greaterсм. например этот:
#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';
}
Другие решения
Других решений пока нет …