Quad tree recursive retrieve

Question

I am creating a quadtree and I get in some trouble with the retrieve function. This function gets down to the nodes that store objects and puts the objects in a vector called relevantObjects. After this, it returns the relevantObjects vector. But, when it tries to do this, I see in the debugger that the vector gets wiped of its elements (goes from 4 to 0).

I don't see where I am wrong.

std::vector<PTR> Tree::retrieveObjects(PTR p, std::vector<PTR> relevantObjects) {

int quadrant = getQuadrant(p);

if (quadrant != -1 && nodes[0] != nullptr)
{
    nodes[quadrant]->retrieveObjects(p, relevantObjects);
}

relevantObjects.insert(relevantObjects.end(), storedObjects.begin(), storedObjects.end());


return relevantObjects; }

Answer 1

In your recursive function std::vector<PTR> Tree::retrieveObjects(PTR p, std::vector<PTR> relevantObjects), you pass parameter relevantObjects by value; with each call of nodes[quadrant]->retrieveObjects(p, relevantObjects), a copy of vector relevantObjects is made, an the function then operates on the copy.

Within you function, you do not make use of the result of [quadrant]->retrieveObjects(p, relevantObjects), such that the operations on the respective copy of relevantObjects get lost; Your function will return a copy of the very first input to relevantObjects after having executed relevantObjects.insert(relevantObjects.end(), storedObjects.begin(), storedObjects.end());.

To solve the problem, simply make parameter relevantObjects a "call by reference", i.e. change your signature to std::vector<PTR> Tree::retrieveObjects(PTR p, std::vector<PTR> &relevantObjects), and it should work.

BTW: if you pass the vector by reference, it is unnecessary to return the result; a signature like void Tree::retrieveObjects(PTR p, std::vector<PTR> &relevantObjects) is sufficient.