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

Question

以下代码使用与向量和优先级队列相同的比较器函数。然而，两种数据结构产生的顺序是不同的。我希望优先队列的行为方式与向量相同。

我有两个问题

为什么顺序不同？
如何让优先队列的顺序与vector相同？

这是以下代码的输出：

//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

顺序不同，因为 < 关系意味着 std::sort 按升序对值进行排序，而 std::priority_queue 将最大元素放在顶部。这是。

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

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

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

这与 this question 中解释的从 std::less 到 std::greater 完美类比。

您可以使用 lambda，而不是引入单独的函数：

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

Answer 2

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

The comparison function used to determine whether one element is smaller than another element. If Compare(x,y) is true, then x is smaller than y. The element returned by Q.top() is the largest element in the priority queue. That is, it has the property that, for every other element x in the priority queue, Compare(Q.top(), x) is false.

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

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

Difference in order with same comparator in Priority Queue & Vector

c++

vector

priority-queue

comparator