Boost logo

Boost :

Subject: Re: [boost] [tree] tree cursors and iterators
From: Erik Erlandson (eerlands_at_[hidden])
Date: 2011-05-10 15:47:31


On Tue, 2011-05-10 at 12:11 -0700, Cromwell Enage wrote:

>
> > 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 couldn't find inorder_first() in the tree proposal. Did you mean inorder::begin(), which is a namespace-level algorithm?

I saw it here:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2101.html#tr.hierarchy.bintree
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2101.html#tr.hierarchy.narytree

It looks like this:

cursor inorder_first();
const_cursor inorder_cfirst() const;
  * Returns: A cursor to the binary_tree's first element in inorder (see
    [tr.order.iterators], §4).

Perhaps it means "if you were going to traverse this tree in-order, here is the cursor that points to the first node you would visit in that traversal"

I'm a little skeptical that such a thing is necessary. If I want in-order traversal, or breadth-first traversal, or any other particular kind of traversal, I'd use an appropriate iterator for that (which might very well be
implemented on top of a cursor).

>
> And yes, it doesn't look like a cursor is meant to be a drop-in replacement for a breadth-first or depth-first iterator, but that both can be defined in terms of cursors.

That is also a semantic that makes sense to me.


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