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

From: Terje Slettebø (tslettebo_at_[hidden])
Date: 2002-10-11 08:13:23

>From: "Larry Evans" <jcampbell3_at_[hidden]>

>>>From: "Terje Slettebø" <tslettebo_at_[hidden]>
>>>
>>>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?
>>
>>Sorry, it will be possible, just not very efficient, as it has to traverse
>>the tree for it. So it's a space/time tradeoff.

>Couldn't you implement the iterator as pointing to the previous node and
the
>deref operator simply do 2 derefs instead of 1 to get to the actual node?

Yes. You would then save a pointer, at the expense of some slower
dereferencing.

>Also, couldn't a stack<node*> be used instead of the node* parent to
>traverse the list; thereby saving one node*?  Again, a space/time tradeoff.

I'm not sure what you mean, here, could you elaborate?

As I understand, you need the parent pointer for example if you delete the
first child, so the parent has to be adjusted to have its first_child
pointer point to the next sibling of the deleted child (now the first
child).

Regards,

Terje