使数组的最小优先级队列c ++

Question

我想要一个最小优先级队列，它不包含整数，而是存储数组。每个元素的优先级是数组中的第一个元素。

priority_queue<array<int, 6>, vector<int>, greater<int>> pq;
array<int, 6> arr = {a, b, c, d, e, f};
pq.push(arr);
array<int, 6> popArr = pq.pop();

当我这样做时，出现以下与推送相关的错误：

no matching function for call to ‘std::priority_queue<std::array<int, 6>, std::vector<int>, std::greater<int> >::push(std::array<int, 6>&)’
 pq.push(arr);

以及以下与弹出相关的内容：

conversion from ‘void’ to non-scalar type ‘std::array<int, 6>’ requested
 array<int, 6> popArr = pq.pop();

如何修复这些错误？

Answer 1

首先优先队列的数据结构类型是array，所以vector应该写成vector>。

现在第三个参数是比较器。所以让我们创建一个比较器：

struct Compare{
    bool operator()(array<int,6> a,array<int,6> b){
    return a[0]>b[0];
}
};

现在声明如下：

priority_queue<array<int,6>, vector<array<int,6>, Compare > pq;

另外，pq.pop() return类型是void，所以应该是pq.top() 然后写 pq.pop() 从优先级队列中删除元素。

Answer 2

来自[container.adaptors]

The first template parameter T of the container adaptors shall denote the same type as Container::value_type.

您需要 std::priority_queue<std::array<int, 6>, std::vector<std::array<int, 6>>, greater_first>，其中 greater_first 是具有 bool operator()(const std::array<int, 6> &, const std::array<int, 6> &) 的类型，例如

struct greater_first {
    bool operator()(const std::array<int, 6> & lhs, const std::array<int, 6> & rhs) const {
        return lhs[0] > rhs[0];
    }
};

另外，pop returns void，所以在popping

之前必须取第一个元素

auto popArr = pq.top();
pq.pop();

使数组的最小优先级队列c ++

Make min priority queue of arrays c++

c++

arrays

priority-queue

data-structures