c++ - 对定义自定义优先级队列和使用 C++ 中的 make_heap 等方法初始化堆之间的区别感到困惑

Question

我试图解决一个编码问题，该问题需要我使用堆按特定顺序获取项目。当我尝试同时使用自定义 priority_queue 和 make_heap 来实现解决方案时，我发现我们传入自己的比较器的方式不同且令人困惑。

c++.com 说:

priority_queue (const Compare& comp = Compare(), const Container& ctnr = Container());

Comp 是用于对堆进行排序的比较对象。这可能是一个函数指针或函数对象，能够通过比较它的两个参数来执行严格的弱排序。

void make_heap (RandomAccessIterator first, RandomAccessIterator last,
              Compare comp );

这里的 comp 是一个二元函数，它接受范围内的两个元素作为参数，并返回一个可转换为 bool 的值。这可以是函数指针或函数对象。

我对这里使用 2 comp 的区别感到困惑，当我尝试实现我的代码时:

// first I define a functor and a static function, both used to be passed as the comp argument;
class isGreater {
    public:
        isGreater() {}
        inline bool operator() (const ListNode* l1, const ListNode* l2) const {
            return l1->val >= l2->val;
        }
}; 

static bool isLarger(const ListNode* l1, const ListNode* l2) {
    return l1->val >= l2->val;    
}

// then I tried several ways to define a custom pq and heap:

// correct
priority_queue<ListNode*, std::vector<ListNode*>, isGreater> p;

// wrong, error: data member instantiated with function type 
// 'value_compare'(aka 'isGreater ()')
priority_queue<ListNode*, std::vector<ListNode*>, isGreater()> p;

// wrong, passing a function pointer like this is not allowed
// error: template argument for template type parameter must be a type
priority_queue<ListNode*, std::vector<ListNode*>, isLarger> p;

// correct
make_heap(v.begin(), v.end(), isGreater());

// correct, here passing a function pointer like this is allowed
make_heap(v.begin(), v.end(), isLarger); 

// wrong, the "()" is needed, different from how we define priority queue
make_heap(v.begin(), v.end(), isGreater);

我对我们将 comp 作为参数传递的方式的差异感到困惑。有人可以帮我解决这个难题吗？

Answer 1

为了理解发生了什么，您需要理解 isGreater 和 isGreater() 之间的区别

• isGreater 是类型的名称。它可以到达类型可以到达的地方，即进入模板参数(三角括号)和声明。
• isGreater() 是一个构造函数调用，它生成一个类型为 isGreater 的对象。它可以出现在表达式可以出现的任何地方，例如它可以用作函数参数。

现在错误应该很清楚了:不允许使用类型名称 isGreater 代替对象表达式 isGreater() ，反之亦然。