473,320 Members | 1,766 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Selef-cleaning trees

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
Jul 22 '05 #1
3 1361
Dave wrote:

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.

--
Regards,
Buster.
Jul 22 '05 #2
Buster wrote:
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.

--
Regards,
Buster.
Jul 22 '05 #3

"Dave" <be***********@yahoo.com> wrote in message
news:10*************@news.supernews.com...
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


Jul 22 '05 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

6
by: TPI | last post by:
I wrote application wich i working on IntPtr. Whole thing is using Marshal.ReadInt32 and Marshal.WriteInt32. And sometimes the application shuts down with out any wornings and exceptions. With...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.