Я довольно плохо знаком с общими указателями и пытаюсь удалить узел из графика. Когда я удаляю узел, входящие и исходящие ребра, сохраненные в этом узле, будут удалены. Однако мне также необходимо удалить исходящие и входящие ребра (которые являются входящим и исходящим ребрами удаленного узла соответственно) узла, который ранее был подключен к удаленному узлу, который я называю узлом связи.
Код ниже показывает мои объявления класса Graph:
template <typename N, typename E> class Graph {
private:
struct Node;
struct Edge;
struct Node {
N val_;
int numEdges_;
int numIncomingEdges_;
std::set<std::shared_ptr<Edge>> edges_;
std::set<std::shared_ptr<Edge>> incomingEdges_;
Node() {}
Node(const N x) : val_{x} { numEdges_=0; }
void printNode(N n);
~Node();
void update();
};
struct Edge {
std::weak_ptr<Node> orig;
std::weak_ptr<Node> dest;
E val_;
Edge(std::shared_ptr<Node> o, std::shared_ptr<Node> d, E x);
Edge() {};
void printEdge();
~Edge();
};
..... Some code for node and edge iterators
private:
std::map< N, std::shared_ptr<Node> > nodes_;
};
Чтобы класс удалил узел:
template <typename N, typename E>
void Graph<N, E>::deleteNode(const N& node) noexcept {
auto findNode = nodes_.find(node);
if (findNode != nodes_.end()) {
// find the node which has incoming edges into the deleted node and delete its edges
for (auto edge: findNode->second->incomingEdges_) { // for each edge in node's incomingEdges_
// get the origin node of incoming edge to deleted node through dest.lock()
auto originNodeOfIncomingEdge = edge->dest.lock();
auto nodeVal1 = originNodeOfIncomingEdge->val_;
std::cout << "Print out value of origin node of incoming edge to deleted node: " << nodeVal1 << std::endl;
auto findLinkingNode1 = nodes_.find(nodeVal1);
std::cout << "size of edges_ in linking node before deleting its outgoing edge (which is the incoming edge of deleted node): " << findLinkingNode1->second->edges_.size() << std::endl;
auto findEdge = findLinkingNode1->second->edges_.find(edge);
findLinkingNode1->second->edges_.erase(findEdge);
std::cout << "size of edges_ in linking node after deleting its outgoing edge (which is the incoming edge of deleted node): " << findLinkingNode1->second->edges_.size() << std::endl;
--findLinkingNode1->second->numEdges_;
}
... similar code to above for deleting the node that has outgoing edges from deleted node going into it
findNode->second.reset(); // deletes managed object of the shared_ptr
nodes_.erase(findNode); // removes the node from the map container
}
}
Поэтому главное, что меня смущает, — это часть, где я пытаюсь удалить ребро из цикла for, чтобы удалить ребро в связанном узле.
auto findEdge = findLinkingNode1->second->edges_.find(edge);
findLinkingNode1->second->edges_.erase(findEdge);
Но я продолжаю получать ошибки, связанные с shared_ptr. Первый связан с указателем:
test8c(2863,0x7fff78df2000) malloc: *** error for object 0x7ffda2403350: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
Abort trap: 6
Ранее мой код для этой части findLinkingNode1->second->edges_.erase(edge);
без findEdge. Я смог собрать без каких-либо ошибок, но край не был удален.
Кто-нибудь может подсказать мне, как я могу успешно удалить ребро из граней_? dge_ объявляется как std::set<std::shared_ptr<Edge>> edges_;
как показано в классе Graph.
То, как все устроено, не очень эффективно. Ваш Node
С деструктором нужно будет:
Итерировать по каждому из Edge
в Node
быть уничтоженным.
Для каждого Edge
get()
другой Node
,
Найти то же самое Edge
в этом другом Node
и удалите его.
Если это частая операция, я бы предложил следующий рефакторинг:
Ваш Edge
держать shared_ptr
с вашим Node
s.
Ваш Node
держать weak_ptr
с вашим Edge
s.
Следовательно, чтобы удалить Node
вы перебираете узел Edge
и удалите их. В конце концов Edge
все удаляется shared_ptr
с Node
s выходят из области видимости, и узел уничтожается.
Если это нецелесообразно, менее радикальный редизайн будет:
Назначьте уникальный идентификатор, какой-то, каждому Edge
, Подойдет простой инкрементный счетчик, и это может быть возможно в Edge
конструктор, автоматически.
Обратитесь ко всем вашим Edge
с использованием их уникального идентификатора, а вместо std::set
из shared_ptr
с Edge
s, заменить его на std::map
идентификаторов, к shared_ptr
для этого Edge
, Это сделает тривиальным удаление каждого Edge
от другого Node
при уничтожении определенного Node
,
Вместо того, чтобы реализовывать дискретный идентификатор, с некоторой осторожностью можно использовать необработанные указатели на Edge
с, с std::less<Edge *>
как их строгий компаратор слабого порядка, как импровизированный уникальный идентификатор для каждого ребра.
Других решений пока нет …