Search code examples
c++graphiterationshared-ptrstdset

Deleting an edge from edges_ that is declared as std::set<std::shared_ptr<Edge>> edges_;

I'm new to std::shared_ptr and std::set. For the following code, I want to know how I can delete the edge from edges_.

edges_ is declared as std::set<std::shared_ptr<Edge>> edges_; and I want to delete the edge referenced by the shared pointer stored in the std::set. My code for the part is here, but there seems to be problem.

auto findEdge = findLinkingNode1->second->edges_.find(edge);
findLinkingNode1->second->edges_.erase(findEdge);

Error:

test8c(3034,0x7fff78df2000) malloc: *** error for object 0x7f8553403350: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
Abort trap: 6

How can I delete the edge from edges_, which is managed through shared pointers, considering that the shared pointers are stored in a std::set?

Solution

  • It's just guessing, but given the code you provide ...

    auto findEdge = findLinkingNode1->second->edges_.find(edge);
findLinkingNode1->second->edges_.erase(findEdge);

    ... I'd say your issue is that you're erasing edges_.end() which is not allowed (probably undefined behavior):

    The iterator pos must be valid and dereferenceable. Thus the end() iterator (which is valid, but is not dereferencable) cannot be used as a value for pos.

    The variable findEdge will be equal to edges_.end() if the given edge was not found in the set. To find an element, std::set uses a Compare object whose type is defined via the second template parameter ...

    std::set<std::shared_ptr<Edge>> edges_;

    ... which you didn't specify, thus it's defaulting to std::less<std::shared_ptr<Edge>> which in turn calls the operator< of the shared pointer, which ...

    Note that the comparison operators for shared_ptr simply compare pointer values; the actual objects pointed to are not compared.

    ... does not compare the objects but only the pointers. Therefore, if the pointers used for inserting and searching are not pointing to exactly the same (as in identical, not only "equal") object, you've signed up for trouble.

    The above was a guess, but given your comment ...

    findOrig->second->edges_.insert(std::make_shared<Edge>(Edge (findOrig->second, findDest->second, val) ));

    ... makes it a fact, as there's (almost) no way to get hold of the pointer returned by make_shared.

    Solution: Implement a compare class for your set that compares the actual Edge objects. (Getting rid of the pointers isn't that straightforward because you said that Edge is polymorphic)

    Morale: Always test for possible error conditions.