// ntree.h
#include <iostream>
#include <list>
#include <vector>
#include <deque>
using namespace std;
template <typename V,template <typename T,class A> class C=list>
class ntree{
private:
ntree(){}
protected:
public:
typedef typename C<ntree *, allocator<ntree *> >::iterator iterator;
C<ntree *,allocator<ntree *> > children;
ntree *parent;
V data;
void recurse(void (V::*f)()){
iterator it;
iterator e=children.end();
(data.*f)();
for (it=children.begin();it!=e;++it){
(*it)->recurse(f);
}
}
void push_back(V v){
ntree *nt;
nt=new ntree(v);
nt->parent=this;
children.push_back(nt);
}
ntree(V v){
data=v;
parent=0;
}
};
//
//
// ntreetest.cc
#include "ntree.h"
struct inttest{
int n;
inttest(int inn){
n=inn;
}
inttest(){
n=0;
}
void print(){
cout << n << endl;
}
};
int main(){
ntree<inttest,vector> testtree(inttest(1));
testtree.push_back(inttest(2));
testtree.push_back(inttest(3));
testtree.push_back(inttest(4));
testtree.recurse(&inttest::print);
}
Self referencing templates
Author
Hello again everyone,
As part of my learning to use templates more effectively, I wanted to write up a templated n-tree [1 parent, arbitrary children]. I also wanted to allow the user to specify what container class to use for the 'arbitrary children' part.
Anyways, I finally got it to compile, thanks in large part to this site. But it still seems as though things are... out of place it seems. Even a somewhat simple class like this isn't coming quickly or naturally. Patience I guess.
Anyways, I'd like to post the code for others trying to do similar things, and to allow others to critique it, and perhaps explain why some of it is awkward, or better, more natural, ways to use the language feature.
Which should compile, and print the expected 1,2,3,4 all on their own line.
Author
So, a problem with this arises when the templated data V is a pointer. data.*f() in recurse() should at that point be data->*f()
Now, I wagered this sort of thing could be solved via functor magic. Research though seems to indicate that functor magic isn't as arbitrarily magical as I guessed.
What are others' ideas regarding the 'correct' way to choose between data.*f() and data->*f()? Is placing a bool in the template class declaration and require the user to set it true if V is a pointer 'good enough'? Am I just missing some crafty solution?
Now, I wagered this sort of thing could be solved via functor magic. Research though seems to indicate that functor magic isn't as arbitrarily magical as I guessed.
What are others' ideas regarding the 'correct' way to choose between data.*f() and data->*f()? Is placing a bool in the template class declaration and require the user to set it true if V is a pointer 'good enough'? Am I just missing some crafty solution?
Author
Quote:Original post by Fruny
Do you have Boost installed?
Not currently, every time I've tried to look into the library [looking into lexical cast, regex, and any if I remember correctly], I've gotten as far as the documentation before quitting. Partly because it went over my head, partly because it seems to avoid actually providing practical use. SGI's documentation on the STL is much the same way, though the STL has more user-made tutorials.
Anyways, this is all a learning experience, and I don't particularly need to get this working. If the correct answer is the use of boost::bind or somesuch, that would be greatly helpful in providing a concrete example of how boost handles some of the stl's shortcomings, and why I should spend more time trying to fight through their documentation.
Quote:Original post by Telastyn
Not currently, every time I've tried to look into the library [looking into lexical cast, regex, and any if I remember correctly], I've gotten as far as the documentation before quitting.
Well, even if you don't have it, you can do something like:
template<class T> T& maybe_dereference(T* ptr) { return *ptr; }template<class T> T& maybe_dereference(T& ref) { return ref; }...(maybe_dereference(data).*f)();Won't work on VC6 (no partial template specialization support).
Quote:If the correct answer is the use of boost::bind or somesuch, that would be greatly helpful in providing a concrete example of how boost handles some of the stl's shortcomings, and why I should spend more time trying to fight through their documentation.
The answer wouldn't so much be boost::bind itself as the kind of tricks used in its implementation (also, look at boost::mem_fn). Though, if you made your recurse() a function template... then you would be able to pass boost::function objects to it, and all sorts of other things like it.
STL's approach is to assume that your functor all accept the f(data) syntax, and to pass adapted objects, rather than modify the function's internals.
Anyway, I was asking you if you were using boost because it provides type traits like boost::is_pointer<T> which you can use to dispatch to the appropriate function depending on the nature of T.
#include <iostream>#include <functional>#include <list>#include <vector>template <typename Element, template <class,class> class Sequence=std::list, template <class> class Allocator = std::allocator>class ntree{ typedef Allocator<ntree*> allocator; typedef Sequence<ntree*, allocator> children_t; children_t children; ntree* parent; Element data;public: ntree() : data(), parent(0) {} ntree(Element e) : data(e), parent(0) {}private: ntree(Element e, ntree* p) : data(e), parent(p) {}public: template<class Func> void recurse(Func f) { children_t::iterator itor; children_t::iterator end = children.end(); f(data); for (itor=children.begin();itor!=end;++itor) (*itor)->recurse(f); } void push_back(Element e) { ntree *nt = new ntree(e,this); children.push_back(nt); }};struct inttest{ int n; inttest() : n(0) {} inttest(int inn) : n(inn) {} void print() { std::cout << n << std::endl; }};int main(){ ntree<inttest,std::vector> testtree(inttest(1)); testtree.push_back(inttest(2)); testtree.push_back(inttest(3)); testtree.push_back(inttest(4)); testtree.recurse(std::mem_fun_ref(&inttest::print));}Using STL's std::mem_fun_ref and a templated member function.
Of course, you should probably expose an appropriate ntree::preorder_iterator which you would be able to use with an STL algorithm instead of having a recurse member function, but ...
Author
Well, I am not opposed to changing the recurse function into a templated function. In fact, I'd guessed that something like that would be necissary, but I couldn't really wrap my head around how to actually impliment something like that without making assumptions or requirements that defeated the purpose.
My searching lead me to boost::is_pointer(), but the implimentation seemed as though it tested if the parameter was a pointer of the templated argument, not if the templated argument itself was a pointer...
Erm, for my example, it seemed to test if something was a V* rather than a V, not if V was a inttest* rather than an inttest.
Perhaps I was incorrect?
My searching lead me to boost::is_pointer(), but the implimentation seemed as though it tested if the parameter was a pointer of the templated argument, not if the templated argument itself was a pointer...
Erm, for my example, it seemed to test if something was a V* rather than a V, not if V was a inttest* rather than an inttest.
Perhaps I was incorrect?
Quote:Original post by Telastyn
Erm, for my example, it seemed to test if something was a V* rather than a V, not if V was a inttest* rather than an inttest.
If V is inttest* then boost::is_pointer<V>::value will be true.
If V is inttest then boost::is_pointer<V>::value will be false.
Author
Quote:Original post by Fruny
Of course, you should probably expose an appropriate ntree::preorder_iterator which you would be able to use with an STL algorithm instead of having a recurse member function, but ...
Hah! That lead to a very interesting search. I'm barely handling container templates, and designing my own iterator seems daunting [before looking what's involved of course...]. All I was concerned about was eliminating the redundant for(x=children;...){stuff} that permiates my current non-templated tree structures.
Thank you very much. Examples like that [edit: like saying it should be done via the preorder_iterator, not the actual example] are nearly non-existant in tutorials and documentation it seems, and makes it very difficult to really learn the stuff. [edit: because it never would've occured to me to use a tree's range with the algorithms, and it's fairly pointless to learn the language if you don't use it well]
is_pointer is evaluated at compile and has a pretty simple definition you can write it yourself (remember the type traits we discussed before [smile]):
Some other type traits are not so simple/obvious how-ever [grin]
template < typename Tp > struct is_pointer { static const bool value = false; };//partial specialization, for all pointer typestemplate < typename Tp > struct is_pointer<Tp*> { static const bool value = true; };Some other type traits are not so simple/obvious how-ever [grin]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
