Inserting nodes into a tree

[Steven Schveighoffer]

On Fri, 11 Feb 2011 14:49:41 -0500, Andrej Mitrovic  
<andrej.mitrovich at gmail.com> wrote:

> On 2/11/11, Steven Schveighoffer <schveiguy at yahoo.com> wrote:
>> struct Node
>> {
>>     int id;
>>     string myName;
>>     Node *parent; // only needed if you want to go up the tree.
>>     Node *[] children;
>> }
>>
>> -Steve
>>
>
> What are the benefits of using struct pointers instead of classes in  
> this case?

Classes are more heavyweight (hidden vtable ptr, monitor) and have less  
control over their allocation.  For example, I used to use classes to  
represent tree nodes in dcollections' RBTree (which later became  
std.container.RedBlackTree), but I found structs use up less space and I  
can create custom allocators for them which significantly increase  
performance.

The only real downside is you occasionally have to deal with the pointer  
aspect (but most of the time not, since the dot operator  
auto-dereferences).

Plus, classes are good if you need polymorphism, or want to restrict  
allocation of nodes to the heap.  You don't need polymorphism for tree  
node, and the restriction isn't necessary in all cases.  It might be a  
good idea to make the "tree root" a class, but the nodes work better as  
structs.

-Steve