Re: [boost] Re: any interest in a 'tree' container?

From: Terje Slettebø (tslettebo_at_[hidden])
Date: 2002-10-11 05:53:30

>From: "Kasper Peeters" <peekas_at_[hidden]>

> > I have only briefly looked over the documentation. Are you using a
> > quad-linked structure to avoid link allocations (i.e. the links are
embedded
> > in the nodes)?
>
> Yes, the nodes are
>
>   template<class T>
>   struct tree_node_ {
>     tree_node_<T> *parent;
>     tree_node_<T> *first_child, *last_child;
>     tree_node_<T> *prev_sibling, *next_sibling;
>     T data;
>   };
>
> For very small-size objects 'T' this is of course a lot of overhead,
> and perhaps a singly linked list would be preferable in this case (I
> guess this is one of the reasons why Herve wants the class to be
> templated over the container class in which the children are stored,
> right?).

Well, if you have only a single linked list (removing parent and
prev_sibling), then it won't be possible to delete nodes, will it? So that
may not be that useful. If you only need a tree you can add nodes to, but
not delete, you can use that, though.

As I understand, the last_child link is used to provide O(1) appending
(instead of O(N), N=number of children).

Regards,

Terje