Member function templates cannot be declared virtual - From Addison Wesley: C++ Templates

Question

From Addison Wesley: C++ Templates

Member function templates cannot be declared virtual. This constraint is imposed because the usual implementation of the virtual function call mechanism uses a fixed-size table with one entry per virtual function. However, the number of instantiations of a member function template is not fixed until the entire program has been translated.

Does the above quote mean that templates have static binding and virtual functions have dynamic binding, that's the reason there cannot be virtual function templates? Please see if a explanation in layman's language is possible.

Weigle

Depends on what you mean by binding. You can implement a virtual method by calling a member template. As long as you inline it, any compiler with tail-call optimization will eliminate the overhead – Premonish

Against SO's terms, just wanted to say this is a damn good question. – Stingy

Answer 1

Consider:

struct X
{
    template <typename T>
    T incr(const T& t)
    {
        return t + 1;
    }
};

As incr() is applied to different T types, new functions are generated. Say inside app.c++ you have:

X x;
x.incr(7);        // incr<int>()
x.incr(7.0);      // incr<double>()
x.incr("hello");  // incr<const char*>()

Then as it's compiling app.c++, it sees 3 functions that - if incr were allowed to be virtual - it could make space for the three instantiations above in the virtual dispatch table for X. Then say it loads a shared library at run-time, and the code for that library had 2 instantations of X::incr for uint32_t and std::string::const_iterator. dlopen() would need to grow the existing virtual dispatch table for the already created objects to make space for two new functions. Doesn't sound too horrible, but consider:

• each bit of code calling virtual functions must know if the address of those functions was bumped along by some offset at run-time (due to dynamic loading of extra instantiations), so there's extra memory and performance cost in every virtual dispatch

• when there's multiple inheritance, or a derived class is itself derived from, the compiler may want to create a single virtual dispatch table for the total set of virtual functions (one option, there are many for implementing virtual dispatch): in this case, the new virtual functions would either displace other classes' virtual functions or need to be disjoint from the existing ones. Again, more run-time overheads in any scheme to manage this.

So, the very rare occasions when this might be useful aren't worth compromising and complicating the more common case of non-templated virtuals.

Evaporate

Answer 2

Yes, and no.

The most popular method to resolve virtual function calls is to use a table ("vtable"), where each virtual function maps to an index in the table. This more or less requires that you know the size of the table.

With templates, new functions will be created as needed in different modules. You would then either have to convince the linker to build the table after figuring out the final number of functions, or use some kind of runtime structure to search for available functions at runtime.

On many systems, the linker is part of the OS and knows nothing about C++, so that option is limited. A runtime search would of course affect the performance negatively, perhaps for all virtual functions.

So, in the end, it was decided that it just was not worth the trouble of introducing virtual templates into the language.

Bathhouse

Thanks for bothering, You said "With templates, new functions will be created as needed in different modules.", I know I am missing some point, isn't that we use templates because we do NOT want to create different functions, we want to use the same function with random parameters? You meant something else, I know, please clarify. – Weigle

doh: now I have read @Tony 's post below and he seems to clarify my above point :) – Weigle

Answer 3

Does the above quote mean that templates have static binding and virtual functions have dynamic binding, that's the reason there cannot be virtual function templates?

Basically, yes. More specifically, the static binding causes a problem when the code is being generated to support dynamic binding.

When the compiler compiles the base class, it finds a virtual function and decides to make a virtual function table - this will be used to implement dynamic binding: when a virtual function is called on a derived instance, the compiled code follows a pointer in the instance to the virtual function table for the derived class, then a pointer in that table to the implementation of the virtual function. This table has to include every possible virtual function that could be called. Now, suppose we made a templated virtual function. The function table would need an entry for every instantiation of the template, because any of those functions could conceivably be called at runtime. But the information about what types the template is instantiated with, cannot (in general) be gathered at the time that the virtual function table is generated. (At least, not without playing around with the C++ compilation model.)

Eyecatching

thanks, your reply was easier to understand, Question: The vtable is created by the compiler, so when you say that binding is done at the run time, it means, that at run time the linker refers to the table to see which function is where, it is correct? – Weigle

and in the case of templates, we can't know at the compile time that which instance of a template is going to get called, so we can't place them in the virtual table, is this what you mean? – Weigle

The linker does nothing at run time. It is part of the compilation process. At compile time, the compiler generates some code. At run time, that code refers to the table. – Eyecatching

Answer 4

virtual functions and templates still work fine together, there is just a small special case which is not implmented.

template<class T>
class A { virtual void f()=0; }; // works fine

class A { template<class T> virtual void f(T t)=0; }; // does not work

Lindeberg

Answer 5

Depends on what you mean by binding.

You can implement a virtual method by calling a member template. As long as you inline it, any compiler with tail-call optimization will eliminate the overhead

Premonish

Answer 6

Sorta.

You can't really "override" an uninstantiated template because it doesn't even exist in the compiled application. If you instantiate it, then you're not overriding a template, but just another ordinary function. :-)

Denial