Undesired behavior when storing object in vector

Question

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;


struct Node {
    string name;
    vector<Node> nodes;
    Node(const string & name) : name(name) {}
    ~Node() {
        cout << "release " << name << endl;
    }
};

Node root {"A"};
unordered_map<string, Node*> m;

void add_child(const string & parent, const string & child) {
    if (!m.count(parent)) return;
    auto & p = *m[parent];
    cout << "add " << parent << endl;
    // Here is the bug
    p.nodes.emplace_back(child);
    m[child] = &p.nodes.back();
    cout << "add done " << parent << endl;
}

int main() {
    m["A"] = &root;
    vector<string> edges {"A", "B", "A", "D", "B", "E"};

    for (int i = 0; i < edges.size(); i += 2) {
        add_child(edges[i], edges[i + 1]);
    }
}

I am building a tree where children nodes are directly stored as object type instead of pointer type.

Whenever I insert into a new node, I use a unordered_map to store the mapping of the name and the pointer to the object.

The program run failed and raise BAD_ACCESS exception when it tries to access the inserted node in add_child function. Finally, it turns out that it's due to the fact that B node has already been deleted. My question is: when does this happen?

The output are:

add A
add done A
add A
release B
add done A
add B
Exception: EXC_BAD_ACCESS (code=1, address=0x100000010)

Answer 1

The address of elements would be changed after the vector auto-expand/reallocate a larger space when calling push_back like functions.

One solution is to store new allocated address in the vector and delete all of them when the parent node gets deconstructed. e.g.

struct Node {
    string name;
    vector<Node*> nodes;
    ~Node() {
        for (auto pch : nodes)
            delete pch;
    }
};

root.nodes.push_back(new Node("child node"));