0

假设我们有一个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;

谢谢！

4

2 回答 2

5

如您所说，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;
于 2012-08-06T22:11:20.640 回答
3

指向的指针ListNode就像一个日常指针。您不能在两个指针之间重载运算符。

但是，您可以覆盖比较运算符以实现priority_queue. 它会是这样的：

struct ListNodePtrLess {
    bool operator()(const ListNode* a, const ListNode* b) {
        return a->val < b->val;
    }
};

typedef std::priority_queue<ListNode*, std::vector<ListNode*>, ListNodePtrLess> MyPriorityQueue;

（另外：您需要与交ListNodePtrLess朋友ListNode，或让它val以某种不同的方式访问该字段）

于 2012-08-06T22:13:08.897 回答