0

以下のように宣言された一連の ListNode オブジェクトを保持する priority_queue があるとします。

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 に ListNode オブジェクトを val の昇順で保持させることができます。

私の質問は、priority_queue が ListNode クラスへのポインターを保持している場合、代わりにポインターをソートして、val が指す値が昇順になるようにすることができるかどうかです。それ、どうやったら出来るの？

std::priority_queue<ListNode *> pq1;

ありがとう！

4

2 に答える 2

5

あなたが言ったように、std::priority_queue3 番目のテンプレート パラメーターとして、比較を実行するために使用する必要がある比較ファンクターを受け入れます。

アイテムを比較する前に、アイテムを逆参照する独自のコードを作成するだけです。

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は、日常のポインターのようなものです。2 つのポインター間の演算子をオーバーロードすることはできません。

ただし、目的のために比較演算子をオーバーライドできます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 に答える