Re: recursive iterators

sarah@telergy.com (Sarah Thompson)
31 Mar 2002 23:28:36 -0500

          From comp.compilers

Related articles
recursive iterators alexc@world.std.com (2002-03-09)
Re: recursive iterators rhyde@cs.ucr.edu (Randall Hyde) (2002-03-19)
Re: recursive iterators bear@sonic.net (Ray Dillinger) (2002-03-21)
Re: recursive iterators sarah@telergy.com (2002-03-31)
Re: recursive iterators rhyde@cs.ucr.edu (Randall Hyde) (2002-04-06)
| List of all articles for this month |

From: sarah@telergy.com (Sarah Thompson)
Newsgroups: comp.compilers
Date: 31 Mar 2002 23:28:36 -0500
Organization: http://groups.google.com/
References: 02-03-032
Keywords: C++
Posted-Date: 31 Mar 2002 23:28:36 EST

> To be (lightly) more specific, I have a program where I walk tree
> structures recursively, generating elements of a sequence. The program
> does several of these walks at once, doing different things with the
> elements.
>
> I'd like to express this as loops over tree nodes, but the recursion in
> the iterator doesn't easily fit into C++-style iterators. It works as
> recursive functions, but then the loop bodies become closure-like
> parameters.
>
> I can force this in C and C++, but it's clumsy.
>
> What I'd like is something more like Smalltalk, where the loop iterator
> calls the loop body (or better, one of several alternative bodies).


The C++ Standard Template Library contains a number of classes (e.g.
map, multimap, set, multiset) that are normally constructed as trees
internally, but which provide iterators that work the way you mention.
There is no reason in principle why an AST node class (say) couldn't
offer iterators that make walking subtrees trivially easy, using the
same kind of idea, e.g.:


void walk_my_tree(ast_node *n)
{
      ast_node::preorder_iterator pi = n->begin_preorder();
      ast_node::preorder_iterator piEnd = n->end_preorder();


      while(pi != piEnd)
      {
            ast_node &this_node = *pi;


            // do something with the node...


            ++pi;
      }
}


It is possible to see how (as I've hinted) you could define preorder,
in order and postorder iterators. Note that STL iterators are kind-of
scrunged to 'look like' pointers syntactically, but except in special
cases they are often not implemented as anything remotely like a
pointer.


Sarah


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.