priority_queue of priority_queues存在吗？

Question

我正在使用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);
    }

如能提供任何帮助，将不胜感激。

Answer 1

需要比较std::priotity_queue中的元素以确定它们的顺序。默认情况下，元素由std::less进行比较，但您可以提供自己的比较，只要它提供严格的弱排序。

不幸的是，std::priority_queue没有提供任何比较运算符。由于不能比较两个优先级队列的顺序，所以我不认为它们可以按照您想要的方式嵌套。

Answer 2

您必须将自定义比较器传递给优先级队列，以便比较元素并对它们进行排序。

#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";
    }
}

在哥德波特测试。