Inserting nodes into a tree

[spir]

On 02/11/2011 09:21 PM, Steven Schveighoffer wrote:
> 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.

I noticed once another overhead, namely time of method call (certainly due to 
runtime lookup of so-called virtual methods). Was significant, about 3x IIRC.

> 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.

...as long as nodes are all of the same type. But isn't it a very common case 
to have a hierarchy of node types (which /must/ have a common supertype to all 
fit into Node* and/or Node*[] slots)?
I started my last app with struct nodes, then switched to class because was to 
much mess to maintain (type annotations and such, manual castings all the way 
down, somewhat like hand-made tag unions).

denis
-- 
_________________
vita es estrany
spir.wikidot.com