Re: [boost] [tree] tree cursors and iterators

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.