Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk