为什么我不能将比较器放在节点内？

Question

我正在使用 priority_queue 来解决问题。我打算通过以下方式声明我的节点。

struct node{
         int x, y, val;
         node(int _x, int _y, int _val){
             x = _x;
             y = _y;
             val = _val;
         }
         bool operator < (const node& rhs) const{
             return val > rhs.val;
         }
     };

并按以下方式使用它：

priority_queue<node, vector<node>, node> queue;

但是没用。

然后，我换一种方式。有效。

struct node{
         int x, y, val;
         node(int _x, int _y, int _val){
             x = _x;
             y = _y;
             val = _val;
         }

     };
struct com{
    bool operator () (const node& lhs, const node& rhs) const{
             return lhs.val > rhs.val;
         }
};
priority_queue<node, vector<node>, com> queue;

我不知道为什么会有差异。任何建议都会很棒。

鉴于以下答案，我尝试了不同的方法运行我的代码，它们有效：

版本 1

struct node{
         int x, y, val;
         node(int _x, int _y, int _val){
             x = _x;
             y = _y;
             val = _val;
         }
         node(){}

        bool operator () (const node& lhs, const node& rhs) const{
         return lhs.val > rhs.val;
     }
 };

priority_queue<node, vector<node>, node> queue;

版本 2：

struct node{
         int x, y, val;
         node(int _x, int _y, int _val){
             x = _x;
             y = _y;
             val = _val;
         }
    bool operator < (const node& rhs) const{
         return val > rhs.val;
     }

 };
priority_queue<node, vector<node>, less<node>> queue;
//or
//priority_queue<node, vector<node>> queue;
//or
//priority_queue<node> queue;

Answer 1

node 不是默认可构造的，它没有 operator()

由于您使用的是 operator<，因此无需指定比较器，因为默认值为 std::less<T>，如果可用则使用它。如果您不需要指定比较器，则没有理由指定容器，因为 std::vector<T> 已经是默认值。

priority_queue<node, vector<node>, less<node>> queue; 
// same as
priority_queue<node, vector<node>> queue;
// also same as
priority_queue<node> queue;

Answer 2

priority_queue 在其求值过程中直接调用 com(arg1, arg2)。

该函数需要作为函数对象（在您的示例中有效）、静态函数或 lambda 提供。您的第一个 struct 有 none 个。

Answer 3

在第一种情况下，node 是一个 not 比较器——相反，它为 operator< 提供了一个重载，所以你应该使用这个:

priority_queue<node, vector<node>> queue;

没有任何第三个参数。那应该有用。

请注意，比较器 可以调用为：

cmp(x,y)

所以从这个意义上说，您的 class node 不支持这一点 — 但是，它支持这一点：

x < y

这是不同的东西，因此，可以与默认比较器 std::less<T> 一起使用，由 std::priority_queue 使用。

Answer 4

因为第三个模板参数只接受 compareFunction( objA, objB ) 格式。默认情况下，它是 class Compare = std::less<typename Container::value_type>，std::less 调用运算符 <()。

下面的代码应该可以工作

std::priority_queue<node, std::vector<node>> queue;

为什么我不能将比较器放在节点内？

Why can't I put the comparator inside the node?

c++

priority-queue