我有一个类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
有指向彼此的对象?
最佳答案
为您的队列使用 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;
关于指针被“搞乱”,使用对象级存储(与上面的指针存储相反),您的优先级队列可以/将在每次弹出后重新堆放内容时移动元素(以防您不知道,标准库默认使用堆结构作为优先级队列)。
最后,我留下了一个概念,即如何处理某个节点的父指针在其任何/某些子节点之前被弹出,被删除,从而创建指向队列中剩余的任何子节点的无效指针,但听起来您知道这可能会发生。
关于c++ - 指向彼此的对象的 priority_queue,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13534526/