对指针类型的priority_queue元素进行排序

Question

假设我们有一个priority_queue，其中包含一堆声明如下的ListNode对象：

class ListNode {
  int val;
  ListNode *next;
public:
  explicit ListNode(int v) : val(v), next(NULL) {}
  inline bool operator<(const ListNode& rhs) const {
    return val < rhs.val;
  }
};

std::priority_queue<ListNode> pq;

通过重写operator<方法或提供排序函子，我们可以让priority_queue按val的升序保存ListNode对象。

我的问题是，如果priority_queue保存指向ListNode类的指针，我可以对指针进行排序，以便val的指向按升序排列。我怎么做？

std::priority_queue<ListNode *> pq1;

谢谢！

Answer 1

正如您所说，std::priority_queue接受一个必须用来执行比较的比较函子作为第三个模板参数。

只需编写您自己的内容，在比较项目之前取消引用这些项目即可：

template<typename T>
struct PtrLess
{
    bool operator()(const T* left, const T* right)
    {
        return *left < *right;
    }
};


std::priority_queue<ListNode *, std::vector< ListNode * >, PtrLess< ListNode > > pq1;