priority_queue объектов, которые указывают друг на друга
У меня есть класс 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;
Что касается указателей, которые «перепутались», с хранилищем на уровне объектов (в отличие от хранилища указателей, как указано выше), ваша очередь приоритетов может / будет перемещать элементы каждый раз, когда она повторно накапливает содержимое после всплывающего окна (в случае, если вы не были помните, что стандартная библиотека по умолчанию использует структуру кучи для очереди с приоритетами).
Наконец, я оставляю понятие о том, как обращаться с указателем родителя некоторого узла, который извлекается перед удалением какого-либо / некоторых из его дочерних элементов, и тем самым создает недопустимый указатель на все дочерние элементы, оставленные в очереди, но это Похоже, вы знаете, что может произойти.
Другие решения
Других решений пока нет …