Losing reference to object in vector on resize?

Question

I'm trying to populate a tree as below. m is the number of inputs and s is the data for the head node. c is the head node and the inputs that follow are parent-child nodes. Each node has a list of children.

Now, calling addNode to always start from the top of the tree is slow for what I'm doing. Instead, I make addNode return a reference to the to node that it adds to the tree. I maintain a map iNode of to - TreeN so that I can pass a reference to the from node to addNode instead of passing it the head node.

I think what happens is when a TreeN's vector resizes, the objects in it are copied to a new vector in memory and the reference to the nodes I had in iNode are to now deallocated memory. I'm not sure though, fairly new to Cpp.

How would I get this to work the way I want it to?

class TreeN {
public:
    int d;
    vector<TreeN> chld;

    bool operator==(const TreeN &o) {
        return o.d == d;
    }
};

TreeN& addNode(TreeN &root, int &from, int &to) {
    cout << "f: " << from << " t: " << to << " p: " << root.d << endl;
    if (root.d == from) {
        root.chld.push_back(TreeN{to});
        return root.chld[root.chld.size() - 1];
    }
    else {
        for(auto &c : root.chld) {
            return addNode(c, from, to);
        }
    }
}

int main(int argc, const char** argv) {
    int m, s;
    cin >> m >> s;
    TreeN c = {s, vector<TreeN>{}};
    map<int, TreeN&> iNode;
    iNode.insert(pair<int, TreeN&>(c.d, c));
    while (m--) {
        int a, b;
        cin >> a >> b;
        map<int, TreeN&>::iterator itA = iNode.find(a);
        map<int, TreeN&>::iterator itB = iNode.find(b);
        if (itA != iNode.end()) {
            cout << "here " << itA->first << endl;
            TreeN &n = addNode(itA->second, a, b);
            cout << n.d << endl;
            if (itB == iNode.end()) iNode.insert(pair<int, TreeN&>(b, n));
        } else {
            iNode.insert(pair<int, TreeN&>(b, addNode(c, a, b)));
        }
    }
    printTree(c);
}

Input:

This code fails and gives the following output:

here 1
f: 1 t: 2 p: 1
2
here 1
f: 1 t: 3 p: 1
3
here 2
f: 2 t: 3 p: 0 (should say 2)
Segmentation fault (core dumped)

@Areeb Take a look at [How to debug small programs?](https://ericlippert.com/2014/03/05/how-to-debug-small-programs) — L. F., Jul 24 '19 at 09:43
*I think what happens* - I think you're absolutely right. Simple solution would be to store indexes not references in your map. Indexes will still be meaningful after a vector resize. — john, Jul 24 '19 at 09:52
Yes, resizing a `std::vector` invalidates all iterators, as well as pointers or references to elements of that vector. Which means, any time you resize the vector, it is necessary to obtain all needed iterators, pointers, and references to elements again. Not doing so gives undefined behaviour. If resizing only happens due to adding elements to the end, you can use indices to refer to elements - but that isn't possible if, for example, an element is added at the beginning or in the middle of the vector, since that changes indices of subsequent elements. — Peter, Jul 24 '19 at 11:02

Marek R · Accepted Answer · 2019-07-24T11:12:38.733

I will not try understood what your code does and how.
By using references in strange places you made it hard to read and understand. In this code it is hard to track if lifetime of variable exceeds lifetime of reference which is points to that variable.

If you are beginner use references only as a function argument.

Anyway I see undefined behavior here:

TreeN& addNode(TreeN &root, int &from, int &to) {
    cout << "f: " << from << " t: " << to << " p: " << root.d << endl;
    if (root.d == from) { // consider this false
        root.chld.push_back(TreeN{to});
        return root.chld[root.chld.size() - 1];
    }
    else {
        for(auto &c : root.chld) {// root.chld is empty
            return addNode(c, from, to); // this is weird and wrong - but not a source of crash
        }
    }
    // then you can reach this place and there is no return statement
    // leading to UB
    // I'm pretty sure compilers warns you about this problem.
}

Also this last loop has no sense. First iteration will terminate loop execution. This defensively wasn't intended.

I think what happens is when a TreeN's vector resizes, the objects in it are copied to a new vector in memory and the reference to the nodes I had in iNode are to now deallocated memory. I'm not sure though, fairly new to Cpp.

It is possible. Vector allocates some reserve (see its capacity) and when size is becomes larger then capacity new memory is allocated and values are copied/moved to new buffer. This can make references to items on vector invalid.
BUT: form what I see you are not storing those references for longer then next possible resize so this is not the issue.

Regardless of whether execution could fall off the function, that `for`/`return` is strange-looking to say the least. — Quentin, Jul 24 '19 at 10:52

Losing reference to object in vector on resize?

1 Answers1