Checking for null pointer

Hello, I’ve an error that happens rarely, but when it happens my app crashes.
I’ve a loop like this:

    for (auto b:branches) {
        if(b!= nullptr && b->count > 0){
            auto newDir = b->direction / float(b->count);
            shared_ptr<Branch> nextBranch(new Branch(newDir));
            nextBranch->setParent(b);
            nextBranch->move(newDir * branch_length);
            branches.push_back(nextBranch);
        }
        if(b!= nullptr){
           b->reset();
        }
    }

As you see in the loop I’m already checking for a nullptr. But the entry point of my debugger is at the line:

for (auto b:branches) {

One line before my first check for null pointer

How can I avoid this?

The whole app is here https://github.com/edap/testSpaceColonization , and works 99% of the cases.

This bug looks gone if I change the previous loop to a version that does not use auto, but traditional iterators. I do not know why

    for (int i = 0; i<branches.size(); i++) {
        if(branches[i]!= nullptr && branches[i]->count > 0){
            auto newDir = branches[i]->direction / float(branches[i]->count);
            shared_ptr<Branch> nextBranch(new Branch(newDir));
            nextBranch->setParent(branches[i]);
            nextBranch->move(newDir * branch_length);
            branches.push_back(nextBranch);
        }
        if(branches[i]!= nullptr){
           branches[i]->reset();
        }
    }

the problem is you are iterating over a vector and modifying it at the same time so the iterators become invalid if the vector moves in memory. when a vector’s reserved memory is full it will move all it’s elements to a new location if needed to keep all memory contiguous.

a vector iterator as used by for(auto & element: vec) is just a pointer that is incremented to the enxt adress with every loop cycle so if the vector moves the pointer becomes invalid

using an integer to access the vector instead avoids the crash but in general modifying a vector while iterating through it is problematic.

a possible solution is to put the new elements in a different container while creating them and then after add them all at once to the definitive vector after the loop like:

    vector<shared_ptr<Branch>> newBranches;
    for (auto & b:branches) {
        if(branches[i]!= nullptr && branches[i]->count > 0){
            auto newDir = branches[i]->direction / float(branches[i]->count);
            shared_ptr<Branch> nextBranch(new Branch(newDir));
            nextBranch->setParent(branches[i]);
            nextBranch->move(newDir * branch_length);
            newBranches.push_back(nextBranch);
        }
        // the null check here isn't really necessary
        branches[i]->reset();
    }
    branches.insert(branches.end(), newBranches.begin(), newBranches.end());

also not sure what you are doing but you seem to be reseting every branch to null anyway at the end of the loop so instead of pushing a new element in the vector you might just replace the old one avoiding the vector from growing which would also be faster:

    for (auto & b:branches) {
        if(branches[i]!= nullptr && branches[i]->count > 0){
            auto newDir = branches[i]->direction / float(branches[i]->count);
            shared_ptr<Branch> nextBranch(new Branch(newDir));
            nextBranch->setParent(branches[i]);
            nextBranch->move(newDir * branch_length);
            branches[i] = nextBranch;
        }
    }
1 Like

I see. The thing is that I need to modify some elements in the vector, and also I do not know the final size of the vector.

branches[i]->reset(); is not resetting the branch to null, but changing some attributes of the branch object.
I can not put the new elements in a new container and add them at the end of the loop as you suggest, because later i want to add new vertices to a mesh every time a new branch is added. If I put all the new branches at the end, the grow effect will be less smooth.

The code is super slow, around 10fps. The javascript version is way faster, I’m for sure making some mess when adding new elements. I’m looking at this code as main reference http://www.jgallant.com/procedurally-generating-trees-with-space-colonization-algorithm-in-xna/

Well, i was wrong. Adding the new branches at the end as you were suggesting is not making the growth process less “smoother”. It’s making it faster :wink: The javascript version is still faster, probably a vector of ofVec3f instead ofNode will be faster, but for now is ok. Thanks!
Here the edited code:

//Generate the new branches
vector<shared_ptr<ofxSpaceColonizationBranch>> newBranches;
for (int i = 0; i<branches.size(); i++) {
    if(branches[i]!= nullptr){
        if(branches[i]->count > 0){
            auto newDir = branches[i]->direction / (float(branches[i]->count));
            shared_ptr<ofxSpaceColonizationBranch> nextBranch(new ofxSpaceColonizationBranch(newDir));
            nextBranch->setParent(branches[i]);
            nextBranch->move(newDir.normalize() * branch_length);
            addBranchToMesh(nextBranch);
            newBranches.push_back(nextBranch);
        }
        branches[i]->reset();
    }
}
branches.insert(branches.end(), newBranches.begin(), newBranches.end());

yeah ofNode is not specially fast and if you only need translation i would definitely use a vector instead. even with that you must be doing something weird with memory or something like that for the js version to be faster, i can imagine you can create and multiply a 4x4 matrix in c++ at more or less the same speed than adding up a couple of vectors in js

All the branches are parented to a previous one, and I add more or less 1500 during the “grow” part of the algorithm, and in the meantime i edit some of them. If when I edit an iterator the whole vector become invalid, and the memory has to be re-allocated, maybe all the nodes parented to that branch has to be moved to. Maybe a different datastructure, like:

Branch(){
    ofVec3f position;
    ofVec3f parent_position;
}

is faster. I will give a try and let you know
An example of the current implementation is here https://github.com/edap/ofxSpaceColonization

When the grow process is finished, the fps are back to 60.

also if you need to add branches all the time perhaps a list will be faster since that wouldn’t move anything in memory.

also in your first example:

for (int i = 0; i<branches.size(); i++) {
        if(branches[i]!= nullptr && branches[i]->count > 0){
            auto newDir = branches[i]->direction / float(branches[i]->count);
           ...
          branches.push_back(nextBranch);

you were also iterating through any new added branch so that would have been really slow if not enter in an infinite loop

I did not get this last part. I’m not iterating through every new branch, I’m adding them all together as you were suggesting, and this has improved the initial performances:

vector<shared_ptr<ofxSpaceColonizationBranch>> newBranches;
for (int i = 0; i<branches.size(); i++) {
     // lot of things happening here
     newBranches.push_back(nextBranch);
 }
 branches.insert(branches.end(), newBranches.begin(), newBranches.end());

yeah i meant only in the original code you posted at the beginning,