Re: [Boost-users] in-depth iterator

"Guillaume Chereau" 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 { 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 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