Boost logo

Boost :

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



Boost list run by bdawes at, gregod at, cpdaniel at, john at