Boost logo

Boost :

Subject: Re: [boost] [tree] tree cursors and iterators (was: Reviving the tree library)
From: Erik Erlandson (eerlands_at_[hidden])
Date: 2011-05-09 18:40:34


On Fri, 2011-05-06 at 14:38 -0500, Rene Rivera wrote:

>
> > 3) I don't feel like I'm understanding the motivation for cursors versus
> > iterators. Is there an "elevator pitch" for that?
>
> Single sentence:
>
> Cursors provide an abstraction for *all* the possible traversals of
> trees vs. the linear only traversals of iterators in a single object
> making it possible to base the expanse of tree algorithms solely on cursors.
>

I've been trying to sort out the semantics of tree cursors. One thing
seems fairly clear: cursors embody the semantics for what more
traditionally are defined as 'nodes': A cursor has 'begin()' and
'end()' methods that refer to the children of that cursor. The Cursor
concept inherits from the Container concept, since a cursor (like a
"node") is, recursively, a container of cursors.

As far as that goes, it makes sense as an abstraction and seems like a
really useful extension of the STL Concept hierarchy.

Given the above, I get a bit confused about the meaning of methods like
inorder_first(). A cursor, as defined above, seems to not mesh with
any particular traversal mode. And the increment operators '++' seem
to make sense only as 'increment to the next sibling.'

I don't know if this is an ambiguity of the design, or just the
documentation, or my incomplete understanding. Does anybody have
insight?


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