1

我有一个类Node，除了存储数据外，还有一个指向其 parent 的指针Node。我将一些节点存储在 a 中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它们实际上在内存中向上移动并且指针指向 wrong Nodes。这可能吗？

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

如何实现一个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;

或者，对于比较器的更多本地定义，您可以在其中填充 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;

关于指针被“搞砸”，使用对象级存储（与上面的指针存储相反），您的优先级队列可以/将在每次弹出后重新堆积内容时移动元素（以防万一你不是注意，标准库默认使用堆结构作为优先级队列）。

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

于 2012-11-23T19:05:53.957 回答