优先级队列和向量中具有相同比较器的顺序差异

Question

以下代码对向量和优先级队列使用相同的比较器功能。但是，两个数据结构产生的顺序是不同的。我希望优先级队列的行为与vector相同。

我有两个问题

1. 为什么顺序不同？
2. 如何使优先级队列的顺序与向量相同？

这是以下代码的输出：

//Please ignore extra header files, I know I don't need them.
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <iterator>
#include <unordered_map>
#include <functional>

using namespace std;

class Solution {
public:
    typedef pair<string, int> PII;
    static bool cmp(const PII& a, const PII& b)
    {
        if (a.second == b.second)
            return a.first < b.first;
        return a.second > b.second;
    }
    void func(vector<string>& words)
    {
        unordered_map<string, int> hMap;
        for (const auto& w : words)
            hMap[w]++;
        std::priority_queue< PII, std::vector<PII>, std::function<bool(PII, PII)> > Q(cmp);
        vector<PII> V;
        for (const auto& e : hMap)
        {
            Q.emplace(e);
            V.emplace_back(e);
        }
        std::sort(V.begin(), V.end(), cmp);

        //Now why does order of elements is different in vector V and priority_queue Q, despite using same comparator function?
        int size = Q.size();
        cout << "Order in priority Queue:" << endl;
        for (int i = 0; i < size; i++)
        {
            PII e = Q.top();
            cout << e.first << ":" << e.second << endl;
            Q.pop();
        }

        cout << "Order in vector:" << endl;
        for (const auto& e : V)
        {
            cout << e.first << ":" << e.second << endl;
        }
    }
};

int main()
{
    Solution s;
    vector<string> words = {"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is" , "we" , "we" , "we" };
    s.func( words );
    return 0;
}

Answer 1

优先级队列和向量使用比较器的方式有所不同。要了解优先级队列的输出，必须了解其工作原理。 Priority Queue实际上是一个堆，根据比较功能，该堆的元素位于顶部。引用boost Priority Queue

用于确定一个元素是否为比另一个元素小。如果Compare（x，y）为true，则x为小于y。 Q.top（）返回的元素是最大的元素在优先级队列中。也就是说，它具有以下特性：优先级队列中的其他元素x，Compare（Q.top（），x）为false。

在您的情况下，更改比较功能以颠倒顺序应该可以解决问题。

Answer 2

顺序是不同的，因为<关系意味着std::sort将值按升序排序，并且std::priority_queue将最大元素放在顶部。这是by design。

如果要颠倒优先级队列中的顺序，则需要另一个交换参数的比较器，

bool cmp2(const T& a, const T& b) {
    return cmp(b, a);
}

//...
std::priority_queue<T, std::vector<T>, decltype(&cmp2)> queue(cmp2);

与std::less中所述的从std::greater到this question的类推非常相似。

代替引入单独的功能，您可以使用lambda：

auto cmp2 = [](const auto& a, const auto& b) { return cmp(b, a); };
std::priority_queue<T, std::vector<T>, decltype(cmp2)> queue(cmp2);