Linked list/Tree using iterators?

[Amit Bhatia]

User-Agent: OSXnews 2.081
Xref: number1.nntp.dc a.giganews.com comp.lang.c++:8 17435
Hi,
I searched online to see if this is valid or not (since my classes are
still very incomplete, I am unable to check it using compilation) but
did not find anything that answers my question.
I am trying to implement a tree as a doubly linked list.

So, I have a class Node,

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

Node &parent_node ; // I want to avoid copying. ??
vector< list<Node>::ite rator child_nodes; // ??
};

class Tree
{
//again ctors, dtors, and some other stuff;
list< Nodetreeofnodes ;
};

So are the above declarations correct? I don't have a default ctor for
the Node class so am not sure if above would work.
One more question(if above WORKS):

can is do something like this:

list<Node &treeofnodes ; //??

The advantage that I see in this is that I won't have to waste time
copying an instance of class Node when I insert it into the list..
If none of this is supposed to work, then I guess I have no other
option but to resort to pointers and use
class Node
{
// some stuff ctors, dtors, etc, BUT NO Default ctor;

Node *parent_node; //
vector< Node * child_nodes; //
};

class Tree
{
//again ctors, dtors, and some other stuff;
list< Node*treeofnode s;
};

thanks,
--a.

[Victor Bazarov]

Amit Bhatia wrote:

I searched online to see if this is valid or not (since my classes are
still very incomplete, I am unable to check it using compilation) but
did not find anything that answers my question.
I am trying to implement a tree as a doubly linked list.

So, I have a class Node,

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

Node &parent_node ; // I want to avoid copying. ??
vector< list<Node>::ite rator child_nodes; // ??
};

class Tree
{
//again ctors, dtors, and some other stuff;
list< Nodetreeofnodes ;

I think it would be easier if you just make a simple assumption: a Tree
is represented by its root Node (and every node of a Tree is just another
Tree, only smaller), so in that sense you ought to make your 'Node'
a special (extended) form of Tree, the one that has a parent. At least
I probably would make it that way (if you have to use a reference for
the parent). Otherwise, you could just make 'parent_node' a pointer to
a node and keep it null for the root node of a Tree.

Another note: with your current scheme a subtree cannot be pruned/grafted
on another tree.

};

So are the above declarations correct? I don't have a default ctor for
the Node class so am not sure if above would work.

It doesn't need a default c-tor. Besides, it probably can't have it,
since your 'Node' objects cannot move, once attached to a tree.

One more question(if above WORKS):

can is do something like this:

list<Node &treeofnodes ; //??

No, you cannot have a list of references. References are not objects.

The advantage that I see in this is that I won't have to waste time
copying an instance of class Node when I insert it into the list..
If none of this is supposed to work, then I guess I have no other
option but to resort to pointers and use
class Node
{
// some stuff ctors, dtors, etc, BUT NO Default ctor;

Node *parent_node; //
vector< Node * child_nodes; //
};

class Tree
{
//again ctors, dtors, and some other stuff;
list< Node*treeofnode s;
};

In that case you just need to do

class Tree : public Node {
public:
Tree() : Node(NULL) {} // no parent
};

(assuming you have a c-tor that attaches a Node to another one).

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask