Jump to content
  • Advertisement
Sign in to follow this  
Telastyn

Self referencing templates

This topic is 4908 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.
// 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);
}

Which should compile, and print the expected 1,2,3,4 all on their own line.

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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


template < typename Tp > struct is_pointer { static const bool value = false; };

//partial specialization, for all pointer types
template < typename Tp > struct is_pointer<Tp*> { static const bool value = true; };


Some other type traits are not so simple/obvious how-ever [grin]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!