Prev: Reusing user data block in (de)allocator
Next: User defined copy constructors
From: jorka2 on 8 Apr 2008 07:53
Hi
Let say that I wanted to do a filesystem browser. The filesystem is a
tree structure, so my idea was to make an general tree browser that
could browse anything that implemented the ITreeStructure interface.
Now I want to make a generic container class that is a tree and can
hold any data type.
The declarations for this look like this:

template<typename T>
class Tree : public ITreeStructure
{
typedef unsigned int size_type;
typedef std::vector<Tree>::iterator iterator;
typedef const std::vector<Tree>::iterator const_iterator;

bool is_leaf() = 0;
ITreeStructure& parent() = 0;
iterator children_begin() = 0;
iterator children_end() = 0;
T get_value(void) = 0;
};

class TreeBrowser : public IWindowControl
{
public:
TreeBrowser();
TreeBrowser(ITreeStructure& tree);
void BrowseTree(ITreeStructure& tree);

private:
ITreeStructure* m_treep;
};

Now the question is how to define the ITreeStructure interface?
I would like to define it like this
class ITreeStructure
{
public:
virtual bool is_leaf() = 0;
virtual ITreeStructure& parent() = 0;
virtual std::vector<ITreeStructure>::iterator children_begin() = 0;
virtual std::vector<ITreeStructure>::iterator children_end() = 0;
template<typename T> virtual T get_value(void) = 0;
};

The problem is the get_value method since templated virtual functions
are not allowed.
I could have parameterized the whole interface like this
template<typename T>
class ITreeStructure
{
public:
virtual bool is_leaf() = 0;
virtual ITreeStructure& parent() = 0;
virtual std::vector<ITreeStructure>::iterator children_begin() = 0;
virtual std::vector<ITreeStructure>::iterator children_end() = 0;
virtual T get_value(void) = 0;
};
But that defeats the whole purpose of having an interface, since I
want to decouple the TreeBrowser from any implementation of a tree
structure. If the whole interface is parameterized so must the
TreeBrowser class be.

So my questions are:
1. Why isn't templated virtual functions allowed in C++?
2. Is there an reasonably simple way around this? Or can I change my
design some way and have both decoupling and still be able to have an
parameterized implementation of a tree structure?

Thanks in advance
/JK

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: cxxguy on 8 Apr 2008 12:43
{ Please format the text in 70 columns or so, definitely less than 80,
to avoid unintended line breaks or horizontal scrolling that make it
very hard to read. The text has been manually reformatted. -mod }


> So my questions are:
> 1. Why isn't templated virtual functions allowed in C++?

A template, since each instance has it's own signature, is not really
a function, it is more of a family of functions. This would be a problem
when you went to build your virtual table. This is an array of function
pointers, one for each virtual function in the class, and one for the typeid
object (not a function, I know, but under the covers it's all assembly).

When your compiler compiles a call to a virtual function, it notes that
at run time, it will have to look at the actual target, follow it's "virtual
pointer" to find it's virtual table, and find (e.g.) the 4th function there,
and that is it's target. It can do this only because the layout of the entire
virtual table can be gleaned by looking at the static type of the pointer
or reference in question, and of it's base types.

A virtual template, however, would have an unbounded number of instances, and
one would have to use a very differant method for lookup. It is not impossible,
I can imagine an implementation where rather than an array of function pointers,
you have a hash table, where the key is akin to the mangled name of the instance
you are calling and the value is a pointer to a function.

Your get_value() function, however, would present still another function ...
you want to overload it on it's return type. The problem is that if the calling
code does not know whether it will get a structure, a double, a float, an int,
or a bool, how does it know how much space to allocate to receive it's reward?
And once it has it, it can't use it's virtual table to deal with it ... it might
not have one. And it can't deal with it as a template, where this sort of thing
has to be known at compile time.

> 2. Is there an reasonably simple way around this? Or can I change my
> design some way and have both decoupling and still be able to have an
> parameterized implementation of a tree structure?

One solution to your problem with get_value would be to return a boost::variant, which
would allow you to specify a bounded set of types to accept, or a boost::any, which
would allow you to return (as it's name implies), any type at all. If you're not hip
to the boost library, I suggest you find it, learn it, and love it.

Another solution would be a variation no the visitor pattern, where rather than
taking a value as a return value, you would send an object in to get it for you.

Imagine this object:

class acceptor_t {
public:
template<typename T> void accept(const T &);
};


class ITreeStructure
{
public:
virtual bool is_leaf() = 0;
virtual ITreeStructure& parent() = 0;
virtual std::vector<ITreeStructure>::iterator children_begin() = 0;
virtual std::vector<ITreeStructure>::iterator children_end() = 0;
// template<typename T> virtual T get_value(void) = 0;
virtual void come_and_take_it(acceptor_t &);
};


Inside this function, you must know what you will be passing to the acceptor,
so the compiler will as well, and can generate the proper instance of accept<>.

I would tend to prefer the first two solutions to the last one.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Bart van Ingen Schenau on 9 Apr 2008 04:19
jorka2(a)hotmail.com wrote:

> Hi
> Let say that I wanted to do a filesystem browser. The filesystem is a
> tree structure, so my idea was to make an general tree browser that
> could browse anything that implemented the ITreeStructure interface.
> Now I want to make a generic container class that is a tree and can
> hold any data type.
> The declarations for this look like this:
>
> template<typename T>
> class Tree : public ITreeStructure
> {
> typedef unsigned int size_type;
> typedef std::vector<Tree>::iterator iterator;
> typedef const std::vector<Tree>::iterator const_iterator;
>
> bool is_leaf() = 0;
> ITreeStructure& parent() = 0;
> iterator children_begin() = 0;
> iterator children_end() = 0;
> T get_value(void) = 0;
> };
>
> class TreeBrowser : public IWindowControl
> {
> public:
> TreeBrowser();
> TreeBrowser(ITreeStructure& tree);
> void BrowseTree(ITreeStructure& tree);
>
> private:
> ITreeStructure* m_treep;
> };
>
> Now the question is how to define the ITreeStructure interface?
> I would like to define it like this
> class ITreeStructure
> {
> public:
> virtual bool is_leaf() = 0;
> virtual ITreeStructure& parent() = 0;
> virtual std::vector<ITreeStructure>::iterator children_begin() = 0;
> virtual std::vector<ITreeStructure>::iterator children_end() = 0;
> template<typename T> virtual T get_value(void) = 0;
> };
>
> The problem is the get_value method since templated virtual functions
> are not allowed.
> I could have parameterized the whole interface like this
> template<typename T>
> class ITreeStructure
> {
> public:
> virtual bool is_leaf() = 0;
> virtual ITreeStructure& parent() = 0;
> virtual std::vector<ITreeStructure>::iterator children_begin() = 0;
> virtual std::vector<ITreeStructure>::iterator children_end() = 0;
> virtual T get_value(void) = 0;
> };
> But that defeats the whole purpose of having an interface, since I
> want to decouple the TreeBrowser from any implementation of a tree
> structure. If the whole interface is parameterized so must the
> TreeBrowser class be.
>
> So my questions are:
> 1. Why isn't templated virtual functions allowed in C++?

The problem is that a function template is not a function at all.
Rather, it is a recipe for generating a number of similar functions.
A typical way of implementing virtual functions is to have a table of
function pointers (a so called v-table). So, how many slots would I
have to reserve in my v-table for the instantiations of your virtual
template function?

> 2. Is there an reasonably simple way around this? Or can I change my
> design some way and have both decoupling and still be able to have an
> parameterized implementation of a tree structure?

I would use an extra, intermediate, base-class.

class ITreeStructure
{
public:
virtual bool is_leaf() = 0;
virtual ITreeStructure& parent() = 0;
virtual std::vector<ITreeStructure>::iterator children_begin() = 0;
virtual std::vector<ITreeStructure>::iterator children_end() = 0;
};

template <typename T>
class ITreeValue : public ITreeStructure
{
public:
virtual T get_value(void) = 0;
};

In the navigation code, you can work exclusively in terms of
ITreeStructure. When you then need to retrieve the value, you cast to
ITreeValue<MyT> (with a dynamic_cast), and call its get_value member.

>
> Thanks in advance
> /JK
>
Bart v Ingen Schenau
--
a.c.l.l.c-c++ FAQ: http://www.comeaucomputing.com/learn/faq
c.l.c FAQ: http://c-faq.com/
c.l.c++ FAQ: http://www.parashift.com/c++-faq-lite/

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Sean Hunt on 9 Apr 2008 04:12
On Apr 8, 4:53 pm, jor...(a)hotmail.com wrote:
> So my questions are:
> 1. Why isn't templated virtual functions allowed in C++?

Because of templates work. When a template is instantiated, the
compiler basically generates a completely separate class with its own
type, its own set of members, and its own storage. The compiler
creates a separate version for each and every different type - this is
where C++ templates overpower constructs in many other languages. But
imagine the following:

// Header
class Base
{
template <typename T>
virtual T foo (T);
virtual ~Base();
}

// In some source file somewhere:

void bar (Base& base)
{
base.foo(42);
}

// In some other file:

void bar (Base& base);

class Derived : Base
{
template <typename T>
virtual T foo (T);
}

void baz ()
{
Derived d;
bar(d);
}

In this example, the compiler can't know what to call. If the
implementation of Derived::foo is in some file somewhere else, then it
can't instantiate the template. Even if the header is available, it
has no clue what derived class will get passed to bar - it would have
to instantiate them for every class - even the ones that it doesn't
now about. And since the instantiation of the class doesn't know what
functions it will get passed to, it's a catch-22.

> 2. Is there an reasonably simple way around this? Or can I change my
> design some way and have both decoupling and still be able to have an
> parameterized implementation of a tree structure?

I would highly recommend looking at Boost.Any
(http://www.boost.org/doc/libs/1_35_0/doc/html/any.html). It should
suit your purposes.

> Thanks in advance
> /JK

No problem!

Sean Hunt

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Pavel Minaev on 9 Apr 2008 04:16
On Apr 9, 2:53 am, jor...(a)hotmail.com wrote:

> Let say that I wanted to do a filesystem browser. The filesystem is a
> tree structure, so my idea was to make an general tree browser that
> could browse anything that implemented the ITreeStructure interface.
> Now I want to make a generic container class that is a tree and can
> hold any data type.
> The declarations for this look like this:
>
> template<typename T>
> class Tree : public ITreeStructure
> {
> typedef unsigned int size_type;
> typedef std::vector<Tree>::iterator iterator;
> typedef const std::vector<Tree>::iterator const_iterator;
>
> bool is_leaf() = 0;
> ITreeStructure& parent() = 0;
> iterator children_begin() = 0;
> iterator children_end() = 0;
> T get_value(void) = 0;
>
> };
>
> class TreeBrowser : public IWindowControl
> {
> public:
> TreeBrowser();
> TreeBrowser(ITreeStructure& tree);
> void BrowseTree(ITreeStructure& tree);
>
> private:
> ITreeStructure* m_treep;
>
> };
>
> Now the question is how to define the ITreeStructure interface?
> I would like to define it like this
> class ITreeStructure
> {
> public:
> virtual bool is_leaf() = 0;
> virtual ITreeStructure& parent() = 0;
> virtual std::vector<ITreeStructure>::iterator children_begin() = 0;
> virtual std::vector<ITreeStructure>::iterator children_end() = 0;
> template<typename T> virtual T get_value(void) = 0;
>
> };
>
> The problem is the get_value method since templated virtual functions
> are not allowed.
> ...
> 2. Is there an reasonably simple way around this? Or can I change my
> design some way and have both decoupling and still be able to have an
> parameterized implementation of a tree structure?

As declared (assuming your interface would be valid C++), it implies
that I can use an arbitrary T in get_value and expect it to work. I.e.
I can do get_value<int> on some node, then get_value<float> on the
same node, etc. This is probably not what you have in mind here, since
your implementation class restricts get_value for a particular T for
the entire tree.

Now then, how would you use the interface you've written? Let's say
you have a function that takes an argument of type ITreeStructure*;
now what? You don't know what T you can give to get_value so that it
actually works. You could take it as a template parameter, of course,
but then you could just as well ask for ITreeStructure<T>*. The only
point in having your generic interface is to use methods other than
get_value - i.e., as long as you only want to traverse the tree, but
not retrieve the values, the interface is the same regardless of type
of values.

Therefore, the answer is: split your interface into two: a base
ITreeStructureBase, non-template, which contains all functions except
for get_value; and a template ITreeStructure<T>, deriving from
ITreeStructureBase, and containing virtual get_value<T>.

> So my questions are:
> 1. Why isn't templated virtual functions allowed in C++?

Because that would require the ability to instantiate templates at run-
time, which effectively amounts to linking a full-featured C++
compiler into every program, and embedding the source code from the
definition context of your virtual templates (and all known
specializations thereof) in the executable. It is technically doable,
but very complicated in practice, would result in high size and
performance costs, and is certainly not worth the effort.



--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 |  Next  |  Last
Pages: 1 2
Prev: Reusing user data block in (de)allocator
Next: User defined copy constructors