I am trying to build tree where each node can have infinite children, and propagate some values from root down the tree. I tried multiple ways to achieve that. First was by allocation of each individual node on heap. Then i tried to create vector of Nodes (not pointers to Nodes ) and build tree with Node pointers pointing to elements of that vector. This was faster solution, because I stored nodes in one block of memory I guess. This solution works great but if vector resizes I have to rebuild whole tree again. Third option was to use build tree using indices instead of pointers. Only time index is invalidated is when I remove element from vector, but it is only one node so it is no big deal ( swap last element with removed one ). This solution is the slowest one on my machine, in debug mode ( using visual studio 2019) other two solutions perform a lot better in debug mode. But when i switch to release mode with optimization, this solution perform similiar to the solution where i used pointers to elements of vector. I read that compiler might use pointers directly instead of indices when optimization is on. But I can not really answer that. So my question is what is really going on? And can I assume that speed of code using indices will be almost same all the time?
Node using pointers:
struct Node
{
void SetParent(Node* parent)
{
Parent = parent;
NextSibling = parent->FirstChild;
parent->FirstChild = this;
}
void Propagate(float x,float y)
{
Node* tmp = this;
while (tmp)
{
tmp->X += x;
tmp->Y += y;
if (tmp->FirstChild)
tmp->FirstChild->Propagate(tmp->X,tmp->Y);
tmp = tmp->NextSibling;
}
}
float X, Y;
std::string Name;
Node* Parent = nullptr;
Node* FirstChild = nullptr;
Node* NextSibling = nullptr;
}
Node using indices:
struct Node
{
void SetParent(std::vector<Node>& list,int parent)
{
Parent = parent;
NextSibling = list[parent].FirstChild;
list[parent].FirstChild = Index;
}
void Propagate(std::vector<Node>& list, int index, float x, float y)
{
while (index != -1)
{
list[index].X += x;
list[index].Y += y;
if (list[index].FirstChild != -1)
{
list[list[index].FirstChild].Propagate(list, list[index].FirstChild, list[index].X,
list[index].Y);
}
index = list[index].NextSibling;
}
}
float X, Y;
std::string Name;
int Index = -1;
int Parent = -1;
int FirstChild = -1;
int NextSibling = -1;
};