Creating tree of objects w/o using pointers.

[Amit Bhatia]

Hi,
I have posted this post also for the thread "vector of lists" but since
it is about something else (though related) I am posting it again under
new thread.
I want to make a tree of nodes as follows, but am not sure now if it
will work:
In node.h

class Node
{
// some stuff ctors, dtors, etc;
//Default ctor;

Node &parent_node; // Could use pointer here but want to avoid it if
possible. vector< Node & > child_nodes; //Could use pointer here but
want to avoid it if possible.};

In tree.h

class Tree
{
//again ctors, dtors, and some other stuff;
list< Node &> treeofnodes;
};


I don't want to create duplicate copies of nodes, and want everything to
point correctly to elements in the global list treeofnodes.
I am not sure though if above can be done, as there needs to be some
kind of default ctor required and I am using references also..
thanks,
--a.

--

 

[Amit Bhatia]

I just figured that if I also want to delete elements from the tree I
am going to need something like pointers and storing references as below
will not work probably. (??)
However, can I use iterators instead? And then when I want to delete
some of them can I just pass the iterator to the erase function of the list
w/o any problems?

Hi,
I have posted this post also for the thread "vector of lists" but since
it is about something else (though related) I am posting it again under
new thread.
I want to make a tree of nodes as follows, but am not sure now if it
will work:
In node.h

class Node
{
// some stuff ctors, dtors, etc;
//Default ctor;

Node &parent_node; // Could use pointer here but want to avoid it if
possible. vector< Node & > child_nodes; //Could use pointer here but
want to avoid it if possible.};

In tree.h

class Tree
{
//again ctors, dtors, and some other stuff;
list< Node &> treeofnodes;
};


I don't want to create duplicate copies of nodes, and want everything to
point correctly to elements in the global list treeofnodes.
I am not sure though if above can be done, as there needs to be some
kind of default ctor required and I am using references also..
thanks,
--a.

--

 

[Chen shuSheng]

Note: "Node &" is not a pointer type define instead it stands for reference
variable.
"Node *" is a pointer type define.

 

[Bo Persson]

Hi,
I have posted this post also for the thread "vector of lists" but
since
it is about something else (though related) I am posting it again
under
new thread.
I want to make a tree of nodes as follows, but am not sure now if it
will work:
In node.h

class Node
{
// some stuff ctors, dtors, etc;
//Default ctor;

Node &parent_node; // Could use pointer here but want to avoid it if
possible. vector< Node & > child_nodes; //Could use pointer here but
want to avoid it if possible.};

You cannot have a vector of references. The vector must be able to
copy and assign to the elements. That doesn't work for references.

In tree.h

class Tree
{
//again ctors, dtors, and some other stuff;
list< Node &> treeofnodes;
};


I don't want to create duplicate copies of nodes,

Why? Are they *extremely* expensive to copy?

and want everything to
point correctly to elements in the global list treeofnodes.
I am not sure though if above can be done, as there needs to be some
kind of default ctor required and I am using references also..
thanks,
--a.

I think you try to do this more complicated that it actually has to
be. The general rule is to go ahead and use the standard containers,
until you see that your program runs way too slow. Then it is time to
look into exactly where it takes too much time. Most often you will
never have to.

If you store your Nodes by value in a vector, or a list, the container
will take care of all the problems of ownership and destruction. Using
prewritten library code saves you a lot of work.


Bo Persson

 

[Amit Bhatia]

You cannot have a vector of references. The vector must be able to
copy and assign to the elements. That doesn't work for references.

I guess then that I should use pointers. so it would be something like

Node{
//; ;
Node *parent_node;
list<Node*> child_nodes;
};

Tree{
//; ;
list<Node *> treeofnodes;
};

OR (NOT SURE IF THIS WOULD WORK?)

Node{
//; ;
Node *parent_node;
list<Node*> child_nodes;
};

Tree{
//; ;
list<Node> treeofnodes;
};


But here is another potential problem that I don't want. When I want to
delete a particular Node, I can just use free on its pointer or
something. But, if I want this pointer entry to be also deleted from the list
"treeofnodes" in tree class above, there doesn't seem to be an easy way to
do it. (?)
However, I am just wondering if I could use iterators in place of
pointers above. Stl Lists do have function called erase which takes an
iterator argument to remove it from the list. And iterators are not
invalidated if I remove some other ones from the list.So,

Node{
//; ;
Node &parent;
list< list<Node>:: iterator > child_nodes;
};

Tree{
//; ;
list<Node > treeofnodes;
};

But the question is: is this allowed?

Why? Are they *extremely* expensive to copy?


I think you try to do this more complicated that it actually has to
be. The general rule is to go ahead and use the standard containers,
until you see that your program runs way too slow. Then it is time to
look into exactly where it takes too much time. Most often you will
never have to.

If you store your Nodes by value in a vector, or a list, the container
will take care of all the problems of ownership and destruction. Using
prewritten library code saves you a lot of work.


Bo Persson

--