Существует ли приоритетная очередь приоритетных очередей? - PullRequest
Новая
       53

Существует ли приоритетная очередь приоритетных очередей?

0 голосов
/ 15 марта 2020

Я пытаюсь что-то с priority_queues и застрял в следующем случае. 

(1, 4) (2, 4) (3, 4)
(9, 4) (8, 4) (7, 4)
(4, 4) (6, 4) (5, 4)

Я хочу сохранить данные такого типа: Итак, я попытался priority_queue<priority_queue<pair<int, int>>> A, и эта строка скомпилирована хорошо (без ошибок). Поэтому я предполагаю, что это должен быть допустимый тип.

Зачем мне это нужно?

Я хочу получить доступ к этим целым числам в порядке убывания как 9,9,9,9, 8,8,8,8, 7,7,...
Таким образом, каждое целое число должно быть доступно столько раз, сколько оно упомянуто (целое число, количество раз) .

Теперь я не уверен, как мне вводить значения в этой структуре.

Что я пытаюсь получить, это ошибка 

    for (unsigned int i = 0; i < rows; i++) {
        priority_queue<pair<int, int >> temp;
        for (unsigned int j = 0; j < cols; j++) {
            temp.push(make_pair(i, 0));
        }
        A.push(temp);
    }

Буду признателен за любую помощь

Ответы [ 2 ]

1 голос
/ 15 марта 2020

Вы должны передать пользовательские компараторы в приоритетные очереди, которые позволят вам сравнивать элементы и сортировать их. 

#include <map>
#include <queue>
#include <iostream>

struct less_pair_first : public std::less<less_pair_first> {
    constexpr bool operator ()(
                const std::pair<int, int>& a, 
                const std::pair<int, int>& b
            ) const {
        return a.first < b.first;
    }
};

using inner_priority_queue = std::priority_queue<
    std::pair<int, int>, 
    std::vector<std::pair<int, int>>,
    less_pair_first
>;

struct less_inner_priority_queue : public std::less<inner_priority_queue> {
    bool operator ()(
                const inner_priority_queue& a,
                const inner_priority_queue& b
            ) const {
        // I think `inner_priority_queue::value_compare` could be used here in std++17
        return less_pair_first()(a.top(), b.top());
    }
};

using my_priority_queue = std::priority_queue<
    inner_priority_queue,
    std::vector<inner_priority_queue>,
    less_inner_priority_queue
>;

int main() {
    my_priority_queue A;

    unsigned rows = 3, cols = 4;
    for (unsigned int i = 0; i < rows; i++) {
        decltype(A)::value_type temp;
        for (unsigned int j = 0; j < cols; j++) {
            temp.push(std::make_pair(i, 0));
        }
        A.push(std::move(temp));
    }

    for (decltype(A)::value_type i; i = A.top(), !A.empty(); A.pop()) {
        for (decltype(i)::value_type j; j = i.top(), !i.empty(); i.pop()) {
            std::cout << j.first << " " << j.second << "|";
        }
        std::cout << "\n";
    }
}

Проверено в Godbolt .

1 голос
/ 15 марта 2020

Элементы в std::priotity_queue необходимо сравнить, чтобы определить их порядок. По умолчанию элементы сравниваются на std::less, но вы можете предоставить собственное сравнение, если оно обеспечивает строгий слабый порядок .

К сожалению, std::priority_queue не предоставляет оператора сравнения , Поскольку вы не можете сравнить две очереди с приоритетами для упорядочивания, я не думаю, что они могут быть вложены так, как вы хотите.

...