Sign in to follow this  
MrMark

Using trees in c++

Recommended Posts

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

Share this post


Link to post
Share on other sites
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:


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);

Share this post


Link to post
Share on other sites
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 ?

Share this post


Link to post
Share on other sites
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.)

Share this post


Link to post
Share on other sites
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 * string
let rec traverse (Tree (l,s)) =
List.iter traverse l;
print_string s;;


Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this