Разница в порядке с тем же компаратором в Приоритетной очереди и векторе - PullRequest
Новая
       92

Разница в порядке с тем же компаратором в Приоритетной очереди и векторе

0 голосов
/ 29 апреля 2020

В следующем коде используется та же функция компаратора с векторной и приоритетной очередью. Однако порядок, создаваемый обеими структурами данных, различен. Я бы хотел, чтобы приоритетная очередь работала так же, как вектор.

У меня есть два вопроса

  1. Почему порядок отличается?
  2. Как я могу сделать порядок приоритетной очереди быть таким же, как вектор?

Вот вывод следующего кода:

enter image description here

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

Ответы [ 2 ]

0 голосов
/ 29 апреля 2020

Приоритетные очереди и векторы используют компараторы по-разному. Чтобы понять вывод очереди с приоритетами, вы должны понимать, как она работает. Очередь приоритетов фактически представляет собой кучу с элементом сверху, в зависимости от функции сравнения. Цитировать из повысить приоритетную очередь

Функция сравнения, используемая для определения, является ли один элемент меньше другого. Если Compare (x, y) истинно, то x меньше, чем y. Элемент, возвращаемый Q.top (), является самым большим элементом в очереди с приоритетами. То есть он обладает свойством, что для каждого другого элемента x в очереди с приоритетами Compare (Q.top (), x) имеет значение false.

В вашем случае изменение функции сравнения на обратное заказ должен решить проблему.

0 голосов
/ 29 апреля 2020

Порядок отличается, поскольку отношение < подразумевает, что 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);

Это в Совершенная аналогия с переходом от std::less к std::greater, как описано в этого вопроса .

Вместо введения отдельной функции вы можете использовать лямбду: 

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