Re: [Boost-users] in-depth iterator

From: David Abrahams (dave_at_[hidden])
Date: 2006-12-14 17:22:49

"Guillaume Chereau" <charlie137_at_[hidden]> writes:

> Hello everyone,
>
> I have a question concerning the boost::iterator library.
> Here is my situation :
> I have a Tree structure that looks like that :
>
> template<class T>
> struct Node : public std::vector<Node<T> >
> {
>     T value;
> };

I don't think that's legal; for any X, instantiating Node<X> requires
instantiating std::vector<...> on an incomplete type (Node<X>).  Using
derivation in this way is highly questionable anyway;  I strongly
suggest that you use aggregation.

> I'd like to create an iterator that would yield all the values of such
> a structure. And also being able to prevent the iterator from going
> into some branches. The interface should look like this :
>
> template<class T>
> struct Policy
> {
>     bool go_inside(const Node& node)
>    {
>         return True;
>    };
> };
>
> Node<int> my_tree;
> ...
>
> depth_iter<int, Policy> iter(my_tree, Policy());
> for (; depth_iter++; depth_iter != my_tree.end())
> {
>     ....
> }
>
> I can't find an easy way to create this "depht_iter" class. 

Hint: your iterator would need some way to get from child to parent
nodes.  That means either storing parent-pointers in your data
structure or maintaining a stack of the current node's ancestors in
the iterator.

> Doesn't the boost::iterator library gives some way to create
> in-depth iterators ?

Nope.  

> Is there a way to use the boost::graph library ?

You can use boost::graph algorithms to traverse your structure, but it
won't give you an iterator that makes such a traversal look linear.

HTH,

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com