c++ - 指向彼此的对象的 priority_queue

Question

我有一个类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 时从队列中，Nodes实际上在内存中向上移动并且指针指向错误 Nodes .会是这样吗？

我尝试使用 priority_queue的 Node*而不是指针(并使用 new 创建它们)，这样只有指针被重新排序，而不是对象本身。这似乎解决了指针问题，但是现在队列是按内存地址排序的，而不是 Nodes 的成本。 .

我如何实现 priority_queue有指向彼此的对象？

Answer 1

为您的队列使用 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;

或者，对于比较器的更多本地定义，您可以将 compare-my-pointer 类填充到 Node 中，以免污染全局命名空间:

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;

关于指针被“搞乱”，使用对象级存储(与上面的指针存储相反)，您的优先级队列可以/将在每次弹出后重新堆放内容时移动元素(以防您不知道，标准库默认使用堆结构作为优先级队列)。

最后，我留下了一个概念，即如何处理某个节点的父指针在其任何/某些子节点之前被弹出，被删除，从而创建指向队列中剩余的任何子节点的无效指针，但听起来您知道这可能会发生。