Selef-cleaning trees

[Dave]

Hello all,

Suppose you need to create an n-ary tree in memory. I'm trying to come up
with an elegant scheme to have all of the memory for the tree deallocated
automatically. i.e. I don't want to have to do any dynamic memory
management myself. However, I don't want to go through all sorts of
ridiculous contortions either to avoid the use of pointers / dynamic memory
management. The solution should cost less than what I'm trying to avoid!

If I represent a node as a std::vector of smart pointers to nodes (and of
course the ancillary data held at the node), it would seem that the root
node being destroyed would result in the whole tree of arbitrary width /
depth / branching characteristic being destroyed.

It would seem that this scheme would be a good candidate for being made
generic (the generic parameterization would be for the user-defined
ancillary data associated with each node).

Is there anything wrong with my scheme? Can anybody offer a superior
alternative?

Thanks,
Dave

 

[Buster]

Suppose you need to create an n-ary tree in memory. I'm trying to come up
with an elegant scheme to have all of the memory for the tree deallocated
automatically. i.e. I don't want to have to do any dynamic memory
management myself. However, I don't want to go through all sorts of
ridiculous contortions either to avoid the use of pointers / dynamic memory
management. The solution should cost less than what I'm trying to avoid!

If I represent a node as a std::vector of smart pointers to nodes (and of
course the ancillary data held at the node), it would seem that the root
node being destroyed would result in the whole tree of arbitrary width /
depth / branching characteristic being destroyed.

It would seem that this scheme would be a good candidate for being made
generic (the generic parameterization would be for the user-defined
ancillary data associated with each node).

Is there anything wrong with my scheme? Can anybody offer a superior
alternative?

I don't think there's any problem with this. I wrote a class wrapping
a ternary search tree. The node class has three auto_ptr members. This
gives one fewer layers of indirection, but can't cope with an n-ary tree
if different nodes have different numbers of children.

It is a shame to use shared_ptr since, as every node has at most one
parent, the reference count will only ever briefly be greater than 1.
The allocation of the reference count seems wasteful. But of course you
can't put an auto_ptr in a standard container. An alternative is to use
a vector of raw pointers - back to square one.

What about a dynamically allocated array of auto_ptrs? That way a simple
delete [] in the node destructor ought to suffice.

 

[Buster]

What about a dynamically allocated array of auto_ptrs? That way a simple
delete [] in the node destructor ought to suffice.

If you use boost::scoped_array, the implicit destructor might be enough.
The catch is, changing the size of this array would be quite hard. Not
as hard as managing a vector of raw pointers, though.

Your std::vector <boost::shared_ptr <node_type> > approach is still the
simplest, but it has costs.

 

[John Harrison]

Hello all,

Suppose you need to create an n-ary tree in memory. I'm trying to come up
with an elegant scheme to have all of the memory for the tree deallocated
automatically. i.e. I don't want to have to do any dynamic memory
management myself. However, I don't want to go through all sorts of
ridiculous contortions either to avoid the use of pointers / dynamic memory
management. The solution should cost less than what I'm trying to avoid!

If I represent a node as a std::vector of smart pointers to nodes (and of
course the ancillary data held at the node), it would seem that the root
node being destroyed would result in the whole tree of arbitrary width /
depth / branching characteristic being destroyed.

It would seem that this scheme would be a good candidate for being made
generic (the generic parameterization would be for the user-defined
ancillary data associated with each node).

Is there anything wrong with my scheme? Can anybody offer a superior
alternative?

The only real problem is pointer cycles. If for instance you had each node
containing a pointer to its parent then each child would keep its parent
alive and each parent would keep its children alive, so nothing would get
destroyed.

Pointer cycles are difficult to deal with in general (requiring full blown
garbage collection) but this case has a simple solution. Use a regular
pointer for the child to parent pointer and smart pointers elsewhere.

john