std::priority_queue 包含带仿函数的结构

Question

我想使用仿函数将结构 HeapNode 添加到 std::priority_queue。

#include <iostream>
#include <queue>
#include <algorithm>   

using namespace std;

struct HeapNode
{
    bool operator()(const struct HeapNode &a,const struct HeapNode &b) const 
    {  
        return b.c>=a.c;  
    } 
    double c;     
    double v;     
}h;

int main()
{
    priority_queue<struct HeapNode,vector<struct HeapNode>,h> H;
    struct HeapNode a={1,2};
    struct HeapNode b={3,2};
    struct HeapNode c={6,2};
    H.push(a);
    H.push(b);
    H.push(c);
}

但有错误：

queue.cpp: In function ‘int main()’:
queue.cpp:19:65: error: type/value mismatch at argument 3 in template parameter list for ‘template<class _Tp, class _Sequence, class _Compare> class std::priority_queue’
  priority_queue<struct HeapNode,vector<struct HeapNode>,heapnode> H;
                                                                 ^
queue.cpp:19:65: note:   expected a type, got ‘heapnode’
queue.cpp:23:4: error: request for member ‘push’ in ‘H’, which is of non-class type ‘int’
  H.push(1);
    ^
queue.cpp:24:4: error: request for member ‘push’ in ‘H’, which is of non-class type ‘int’
  H.push(2);
    ^
queue.cpp:25:4: error: request for member ‘push’ in ‘H’, which is of non-class type ‘int’
  H.push(3);
    ^

我已经研究了参考资料，但我仍然对 std::priority_queue 感到困惑。

Answer 1

priority_queue 模板实例化的第三个参数是全局变量，而不是类型。您声明了 struct HeapNode，然后将全局变量 h 声明为 struct HeapNode 类型。在模板实例化中将 h 替换为 struct HeapNode。

此外，我认为最好有一个单独的比较器-class，而不是重复使用您的节点class。这是因为 priority_queue 将创建一个 struct HeapNode 的实例来拥有比较器。

Answer 2

h 指定一个具有静态存储期限的对象。 priority_queue 模板需要类型。这个错误很明显：

error: type/value mismatch at argument 3 in template parameter list

现在，您使用类型本身作为函子来比较它有点奇怪（而且效率低下）⁽¹⁾。我建议拆分它：

struct HeapNode
{
    double c;     
    double v;     
};

struct HeapNodeCompare
{
    bool operator()(const struct HeapNode &a,const struct HeapNode &b) const 
    {  
        return b.c>=a.c;  
    } 
};

现在您的队列可以简单地定义为：

priority_queue<HeapNode, vector<HeapNode>, HeapNodeCompare> H;

(1) 我说低效是因为必须默认构造仿函数才能使用。您的类型具有占用存储空间的有意义的状态。如果将类型本身用作仿函数，那就有点浪费了。分离类型没有状态，占用的存储空间最少。

std::priority_queue 包含带仿函数的结构

std::priority_queue contain struct with functor

c++

std

data-structures