Using trees in c++
Author
I want to use a tree of pointers to represent the parent-child relationships between the set of windows displayed on the screen. The tree is only used to store this information; anytime it the nodes in the tree is changed the tree is walked through and a sorted vector containing windows is created.
However STL doesn't have a tree container as apparently there are lots of different tree data structures all suited to solve different problems. My graph theory is a little rusty but all I need to do is a depth first iteration to get the desired result (on paper at least). Which would be I believe a fairly basic function of a tree library.
I've found the boost graph library, but it looks a little complicated but seems fairly powerful. Can anyone comment on the quality of the boost graph library ? Or does anyone know of any other graph / tree libraries I should take a look at ?
Cheers
As far as I can see, a class containing a boost::ptr_vector of itself would make a fine tree. Traversing the tree is extremely simple with std::for_each. For instance, outputting in postfix fashion:
A more generic version:
struct Tree { boost::ptr_vector<Tree> children; std::string data;};void traversal(const Tree& t) { std::for_each(t.children.begin(), t.children.end(), traversal); std::cout << data << " ";}A more generic version:
template <typename T> struct Tree { boost::ptr_vector< Tree<T> > children; T data;};template <typename T, typename F> class PostfixTraverser { F functor;public: PostfixTraverser(const F &f) : functor(f) {} void operator()(const Tree<T> &t) const { std::for_each(t.children.begin(), t.children.end(), *this); functor(t.data); }};void print(int i) {std::cout << i << " ";}Tree the_tree;PostfixTraverser(print)(the_tree);
Author
Thanks for your reply.
I'm not familiar with boost::ptr_vector, how is it different from std::vector<Tree*> ? Also how does your code work lol, I don't see how it traverses the tree, is it a recusive function calling traversal each time ?
I'm not familiar with boost::ptr_vector, how is it different from std::vector<Tree*> ? Also how does your code work lol, I don't see how it traverses the tree, is it a recusive function calling traversal each time ?
I did something similar for a GUI I wrote a few years ago. Each GUIComponent object contains an STL list of GUIComponent pointers. So, for instance, the Draw() method for GUIComponent calls a virtual OnDraw() method and then calls the Draw() method for each GUIComponent in the list. Each child class would implement it's own OnDraw() method. This allows you to recursively draw the entire GUI in a single call to the root component (desktop, XWindow, etc.)
Quote:Original post by MrMark
I'm not familiar with boost::ptr_vector, how is it different from std::vector<Tree*> ?
It handles deallocation on its own, so you don't have to write a destructor or use smart pointers. Also, its value type is T, not T*, which makes using for_each easier.
Quote:Also how does your code work lol, I don't see how it traverses the tree, is it a recusive function calling traversal each time ?
Tree traversal is inherently recursive. My code was actually a direct translation from the equivalent OCaml code:
type tree = Tree of tree list * stringlet rec traverse (Tree (l,s)) = List.iter traverse l; print_string s;;
Quote:Original post by MrMark
I want to use a tree of pointers to represent the parent-child relationships between the set of windows displayed on the screen.
I think the reason there is no tree in the standard library is because people often mistake the need to arrange their data in a tree for needing an explicit tree structure to contain that data. Generally making the tree implicitly out of the data is all you need.
To extend/disfigure the example already given:
class Window { // other stuff removed boost::ptr_vector<Window> child_windows; // render windows and then their contents void render() { render_this(); for (boost::ptr_vector<Tree>::const_iterator ci = child_windows.begin(); ci != child_windows.end(); ++ci) { ci->render(); } }};Replacing the explicit loop with a for_each and presumably boost::bind to convert the member function to a simple callable is just slightly beyond me on a Friday afternoon, unfortunately.
If you're familiar with STL then you might fancy a peek at the Tree Container Library. I'm using it at the moment but haven't come to many conclusions - it seems perfectly functional for my purposes and integrates nicely with STL.
Author
After poking around Boost Graph Library and the Tree Container Library, I think I'm just going to go for the simple make-it-yourself tree. I've started to implement the code, but I'm a bit confused on the traversal function.
traversal has one parameter const tree& t, but in std::for_each there's no function call operator or parameters. So then does std::for_each call traversal(t) ? If I say wanted to include another parameter, a vector to store the pointer of each node as we traverse it, how would I modify the function diffention. I think it would be something like;
void traversal(const Tree& t, boost::ptr_vector<Tree>& pRecord)
{
std::for_each(t.children.begin(), t.children.end(), traversal);
std::cout << data << " ";
pRecord.insert(pRecord.end(), this);
}
But then how does traversal know what to stick in pRecord in each recursion.
Quote:Original post by ToohrVyk
struct Tree {
boost::ptr_vector<Tree> children;
std::string data;
};
void traversal(const Tree& t) {
std::for_each(t.children.begin(), t.children.end(), traversal);
std::cout << data << " ";
}
traversal has one parameter const tree& t, but in std::for_each there's no function call operator or parameters. So then does std::for_each call traversal(t) ? If I say wanted to include another parameter, a vector to store the pointer of each node as we traverse it, how would I modify the function diffention. I think it would be something like;
void traversal(const Tree& t, boost::ptr_vector<Tree>& pRecord)
{
std::for_each(t.children.begin(), t.children.end(), traversal);
std::cout << data << " ";
pRecord.insert(pRecord.end(), this);
}
But then how does traversal know what to stick in pRecord in each recursion.
Quote:Original post by MrMark
traversal has one parameter const tree& t, but in std::for_each there's no function call operator or parameters. So then does std::for_each call traversal(t) ?
Functional programming [smile] std::for_each(b,e,f) calls f(*i) for every iterator i between b (included) and e (excluded). So, in essence, only one-argument functions would work.
Quote:If I say wanted to include another parameter, a vector to store the pointer of each node as we traverse it, how would I modify the function diffention.
You couldn't, and nor should you. The function describes a traversal process, which should remain independent from the actual operation performed during traversal. So, you'd use the traversal functor I provided, using a closure which appends to a vector:
int main() { Tree<int> tree; std::vector<const Tree<int>*> record; struct { std::vector<const Tree<int>*> &record void operator()(const Tree<int>& t) { record.push_back(&t); } } functor = { record }; PostfixTraverser(functor)(tree);}The equivalent OCaml code would be:
let _ = let tree = whatever () in let record = ref [] in postfix_traverser (fun t -> record := t :: !record) tree;;Where the anonymous function here is represented by the anonymous structure functor in the example above.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
