1

Nodeデータの格納に加えて、その親へのポインタを持つクラスがありますNode。いくつかのノードをに格納し、比較のためpriority_queueに演算子を上書きします。<

class Node {
public:
    string name;
    Node *parent;
    int cost;
};

static bool operator<(const Node& lhs, const Node& rhs) {
    return lhs.cost < rhs.cost;
}

priority_queue<Node> queue;

問題は、親ポインタがめちゃくちゃになっているように見えることです。私の推測では、NodeキューからaをポップするとNodes、実際にはメモリ内で上に移動し、ポインタが間違った方向を指していると思いますNodes。これでいいの？

代わりにpriority_queueofポインターを使用して（そしてそれらをで作成して）、オブジェクト自体ではなく、ポインターのみが並べ替えられるようにしました。これでポインタの問題が修正されたようですが、キューはメモリアドレスで並べ替えられており、のコストではありません。Node*newNodes

priority_queueオブジェクトが相互にポイントしているを実装するにはどうすればよいですか？

4

1 に答える 1

3

Node*キューのカスタムコンパレータを使用します。現在持っているものを使用して、次のことができますが、現在のツールチェーンで利用できる場合は、スマートポインターを使用することをお勧めします。

class Node {
public:
    string name;
    Node *parent;
    int cost;
};

class CompareNodePtr
{
public:
    bool operator ()(const Node*& left, const Node*& right) const
    {
        return left->cost < right->cost;
    }
};

// your priority queue with custom comparator.
std::priority_queue<Node*, std::vector<Node*>, CompareNodePtr> myqueue;

または、コンパレータをよりローカルに定義するNodeために、グローバル名前空間を汚染しないように、compare-my-pointerクラスを詰め込むことができます。

class Node {
public:
    string name;
    Node *parent;
    int cost;

    struct ComparePtr
    {
        bool operator ()(const Node*& left, const Node*& right) const
        {
            return left->cost < right->cost;
        }
    };
};

// your priority queue with custom comparator.
std::priority_queue<Node*, std::vector<Node*>, Node::ComparePtr> myqueue;

ポインタが「混乱」していることに関して、オブジェクトレベルのストレージ（上記のポインタストレージとは対照的に）では、優先キューは、ポップ後にコンテンツを再ヒープするたびに要素を移動できます/移動します（そうでなかった場合）標準のlibは、デフォルトで優先キューにヒープ構造を使用することに注意してください）。

最後に、あるノードの親ポインターがその子のいずれか/一部の前にポップされ、削除され、それによってキューに残っている子への無効なポインターを作成する方法の概念を残しますが、それはあなたはそれが起こり得ることを知っているように聞こえます。

于 2012-11-23T19:05:53.957 に答える