C++11 using smart pointers but get invalid pointer

Question

I'm using unique_ptr and shared_ptr in this C++ assignment, the code works fine until the end it says

free(): invalid pointer
Aborted (core dumped)

I can't figure out how does it happen.

The code parses file "resource.txt" and construct a graph. Each word is a node, and each line implies dependency between two words. resource.txt

handgun bullets
bullets ore
bombs ore
turret bullets

Below is my output and code:

output of ./main

adding edge: 'handgun' --> 'bullets'
adding edge: 'bullets' --> 'ore'
adding edge: 'bombs' --> 'ore'
adding edge: 'turret' --> 'bullets'
graph now has nodes:
bombs-->
        ore
ore-->
turret-->
        bullets
handgun-->
        bullets
bullets-->
        ore
=======
graph destructor
destructor of node: bombs
destructor of node: turret
destructor of node: handgun
destructor of node: bullets
destructor of node: turret
free(): invalid pointer
Aborted (core dumped)

you can see that each destructor was called, and I am using smart pointers but I still got invalid pointer error.

main.cpp

#include "graph.h"
#include <memory>

int main(int argc, char const *argv[])
{
    unique_ptr<graph> g(new graph("./resource.txt"));
    g->dispay();
    cout << "=======" << endl;
    return 0;
}

graph.h

#ifndef Tan_Li_Graph_Head_
#define Tan_Li_Graph_Head_

#include "node.h"
#include <unordered_map>
#include <memory>
#include <iostream>
#include <string>
using namespace std;

class graph
{
  private:
    /* data */
  public:
    unordered_map<string, shared_ptr<node>> nodes;
    graph(string resourceFileName);
    bool addEdge(string from, string to);
    void delNode(string name);
    void dispay();
    ~graph();
};

#endif

graph.cpp

#include "graph.h"
#include <fstream>
#include <utility>
using namespace std;

graph::graph(string fileName)
{
    ifstream file(fileName);
    string str;
    while (getline(file, str))
    {

        if (str.back() == '\r')
        {
            str.pop_back();
        }

        auto space_loc = str.find(" ");
        string from = str.substr(0, space_loc);
        string to = str.substr(space_loc + 1);
        this->addEdge(from, to);
    }
}

bool graph::addEdge(string from, string to)
{
    cout << "adding edge: '" << from << "' --> '" << to << "\'" << endl;

    if (this->nodes.count(from) == 0)
    {
        shared_ptr<node> node_from = make_shared<node>(from);
        this->nodes.insert(make_pair(from, node_from));
    }

    if (this->nodes.count(to) == 0)
    {
        shared_ptr<node> node_to = make_shared<node>(to);
        this->nodes.insert(make_pair(to, node_to));
    }

    return this->nodes[from]->addChild(this->nodes[to]);
}

void graph::delNode(string name)
{
    auto node_to_del = this->nodes[name];

    for (auto parent : node_to_del->parents)
    {
        parent.second->delChild(node_to_del);
    }

    for (auto child : node_to_del->children)
    {
        node_to_del->delChild(child.second);
    }
}

void graph::dispay()
{
    cout << "graph now has nodes: " << endl;
    for (auto node_to_display : this->nodes)
    {
        // cout << node_to_display.second->name << ": " << (node_to_display.second->useable ? "usable" : "NOT usable")
        //      << " ;" << endl;
        cout << node_to_display.second->name << "-->" << endl;
        for (auto child : node_to_display.second->children)
        {
            cout << '\t' << child.second->name << endl;
        }
    }
}

graph::~graph()
{
    cout << "graph destructor" << endl;
}

node.h

#ifndef Tan_Li_Node_Head_
#define Tan_Li_Node_Head_
#include <string>
#include <unordered_map>
#include <memory>
#include <iostream>
using namespace std;

class node
{
  private:
    /* data */
  public:
    string name;
    bool useable;
    unordered_map<string, shared_ptr<node>> children;
    unordered_map<string, shared_ptr<node>> parents;
    node(string name);
    bool addChild(shared_ptr<node> child);
    bool addChild(string name);
    bool delChild(shared_ptr<node> child);
    bool delChild(string name);
    ~node();
};

#endif

node.cpp

#include "node.h"
#include <utility>
using namespace std;

node::node(string name)
{
    this->name = name;
    this->useable = true;
}

bool node::addChild(shared_ptr<node> child)
{
    string child_name = child->name;

    if (child_name.compare(this->name) == 0)
    {
        cout << "Node " << this->name << " can't add itself to children" << endl;
        return false;
    }

    if (this->children.count(child_name) == 0)
    {
        this->children.insert(make_pair(child_name, child));
        child->parents.insert(make_pair(this->name, this));
    }
    else
    {
        cout << "Node " << child_name << " is already in the child of node " << this->name << endl;
        return false;
    }

    return true;
}

bool node::addChild(string name)
{
    if (name.compare(this->name) == 0)
    {
        cout << "Node " << this->name << " can't add itself to children" << endl;
        return false;
    }

    shared_ptr<node> child = make_shared<node>(name);
    this->addChild(child);
}

bool node::delChild(shared_ptr<node> child)
{
    string child_name = child->name;

    if (this->children.count(child_name) == 0)
    {
        cout << "Node " << child_name << " is NOT the child of node " << this->name << endl;
        return false;
    }
    else
    {
        child->parents.erase(this->name);
        this->children.erase(child_name);
    }

    this->useable = false;

    return true;
}

bool node::delChild(string name)
{
    if (this->children.count(name) == 0)
    {

        cout << "Node " << name << " is NOT the child of node " << this->name << endl;
        return false;
    }
    else
    {
        this->children[name]->parents.erase(this->name);
        this->children.erase(name);
    }

    this->useable = false;

    return true;
}

node::~node()
{
    cout << "destructor of node: " << this->name << endl;
}

for (auto parent : node_to_del->parents) { parent.second->delChild(node_to_del); } This is a problem - delChild has a side effect of modifying node_to_del->parents just as you are iterating over it. Chances are, the program is using an invalidated iterator, and therefore exhibits undefined behavior. — Igor Tandetnik
There must be more to the code you are actually running than the code you've shown. You are creating circular dependencies - just letting graph die won't automatically destroy nodes as they all refer to each other. You are likely doing something in ~graph() that you are not showing. — Igor Tandetnik
Code Review: graph::delNode(string name) should first check if the node exists before trying to delete it. The operator [] will create an empty one (nullptr) if it did not exist, which will cause "node_to_del->parents" to crash (this is not your issue, but worth fixing) — CJCombrink

bashrc bashrc · Accepted Answer · 2019-01-08T06:01:41

The problem is most likely this line:

    child->parents.insert(make_pair(this->name, this));

What you are doing is implicitly creating a shared_ptr from this pointer.

See this for a smaller repro of your problem.

shared_ptr is an unbreakable vow. Once a pointer is managed by a shared_ptr its lifecycle may not be controlled by any another class/wrapper. The memory for this pointer was already created and hence is managed by a different instance of shared_ptr. By (implicitly) creating another instance of shared_ptr using this you are breaking the contract.

There are several ways to fix the problem. One way would be to keep raw pointers for any backedges (for example raw pointer for parents). That way a parent controls the cycle of the child. The other way is to use

unordered_map<string, weak_ptr<node>> parents;

You will have to derive node from enable_shared_from_this and then do:

    child->parents.insert(make_pair(this->name, weak_from_this()));

weak_from_this

Note that you can keep using shared_ptr for both parent and child, but then it would be circular reference and you would be leaking memory.

C++11 using smart pointers but get invalid pointer

1 Answers