Memory issues (stomping?) within C++

Question

I'm trying to build a 3d tree structure PhotonMap which I can add Nodes to.

Node :

class Node
{
    public:
        Node(Photon);
        Node();
        virtual ~Node();
        Node *left = nullptr;
        Node *right = nullptr;
        Photon self;
    protected:
    private:
};

With the constructor being what you'd imagine

PhotonMap :

class PhotonMap
{
    public:
        PhotonMap();
        virtual ~PhotonMap();
        void insert(Node);
        Node *root = nullptr;
        vector<Node> nodes;
        bool first = true;
    protected:
    private:
        Node * insertMain(Node *node, Node *newNode, int depth);
};

void PhotonMap::insert(Node node) {
    nodes.push_back(node);

    if (first) {
        root = &nodes.back();
        first = false;
    }
    else {
        insertMain(root, &nodes.back(), 0);
    }
}

Node * PhotonMap::insertMain(Node *node, Node *newNode, int depth) {
    cout << endl;
    if (node == nullptr) {
            node = newNode;
        return newNode;
    }

    int dimNo = depth % 3;
    switch (dimNo) {
    case 0:

        if (newNode -> self.position.x >= node -> self.position.x) {
            cout << "R : " << (node -> right == nullptr);
            node -> right = insertMain(node -> right, newNode, ++depth);
        }
        else {
                cout << "L : " << (node -> left == nullptr);
            node -> left = insertMain(node -> left, newNode, ++depth);
        }
        break;
    case 1:
        if (newNode -> self.position.y >= node -> self.position.y) {
                cout << "R : " << (node -> right == nullptr);
            node -> right = insertMain(node -> right, newNode, ++depth);
        }
        else {

                cout << "L : " << (node -> left == nullptr);
            node -> left = insertMain(node -> left, newNode, ++depth);
        }
        break;
    case 2:
        if (newNode -> self.position.z >= node -> self.position.z) {
                cout << "R : " << (node -> right == nullptr);
            node -> right = insertMain(node -> right, newNode, ++depth);
        }
        else {

                cout << "L : " << (node -> left == nullptr);
            node -> left = insertMain(node -> left, newNode, ++depth);
        }
        break;
    }
    return node;
}

Additionally there's Photon which holds 3 vectors: energy, direction and position.

Clearly, any Node should have both left and right a nullptr until it's set within the insert function. When I run the following:

PhotonMap pm;
Photon p;
p.position = Vertex(1.0f, 0.0f, -1.0f);
Photon p2;
p2.position = Vertex(-1.0f, 0.0f, 0.0f);
Node node(p);
Node node2(p2);
pm.insert(node);
pm.insert(node2);

I would expect that the initial node will be stored locally in the vector nodes and set the root pointer to the address of node in nodes, after which node2 should:

Have its photon's x position value checked against node's x position

See that its x value is lower

Print "L : 1" (since node's left and right should both be nullptr).

However, I get

L : 0
L : 0
R : 0
L : 0

So it appears as if neither of node's left or right are nullptr despite not being changed?! Since neither are nullptr, the program follows the trail of garbage pointers until it crashes. I was getting std::bad_alloc earlier on but now I'm not. I have a feeling that there may be some memory stomping issue where the pointers left and right are getting overwritten by something. It doesn't appear as if the entirety of the initial node is being overwritten as it's still possible to print its position.

Thanks for any and all help :)

When you add items to a `vector` you may trigger a reallocation of the storage used to get more space, invalidating all of the pointers you have stored. The left and right pointers point to memory that USED to be owned by the `vector`. See [Iterator invalidation rules](https://stackoverflow.com/questions/6438086/iterator-invalidation-rules) for more information. — user4581301, Dec 08 '19 at 18:22
That makes sense! Thank you! Is there any way to work around this? Scalable storage is an absolute must for this tree (I can't precalculate the size) but I also need the random access speed. Vector was looking perfect for this (though apparently not, now) — Jimmy Diddler, Dec 08 '19 at 18:28
If you never remove items from or re-order the `vector` you can turn left and right into `size_t` and store the index in the `vector` rather than the pointers. — user4581301, Dec 08 '19 at 18:37

Memory issues (stomping?) within C++

0 Answers0