Templatized Virtual function

Question

We know that C++ doesn't allow templated virtual function in a class. Anyone understands why such restriction?

Answer 1

Short answer: Virtual functions are about not knowing who called whom until at run-time, when a function is picked from an already compiled set of candidate functions. Function templates, OTOH, are about creating an arbitrary number of different functions (using types which might not even have been known when the callee was written) at compile-time from the callers' sides. That just doesn't match.

Somewhat longer answer: Virtual functions are implemented using an additional indirection (the Programmer's General All-Purpose Cure), usually implemented as a table of function pointers (the so-called virtual function table, often abbreviated "vtable"). If you're calling a virtual function, the run-time system will pick the right function from the table. If there were virtual function templates, the run-time system would have to find the address of an already compiled template instance with the exact template parameters. Since the class' designer cannot provide an arbitrary number of function template instances created from an unlimited set of possible arguments, this cannot work.

Answer 2

How would you construct the vtable? Theoretically you could have an infinite number of versions of your templated member and the compiler wouldn't know what they might be when it creates the vtable.

Answer 3

The other answers have already mentionned that virtual functions are usually handled in C++ by having in the object a pointer (the vptr) to a table. This table (vtable) contains pointer to the functions to use for the virtual members as well as some other things.

The other part of the explanation is that templates are handled in C++ by code expansion. This allow explicit specialization.

Now, some languages mandate (Eiffel -- I think it is also the case of Java and C#, but my knowledge of them is not good enough to be authoritative) or allow (Ada) an shared handling of genericity, don't have explicit specialization, but would allow virtual template function, putting template in libraries and could reduce the code size.

You can get the effect of shared genericity by using a technique called type erasure. This is doing manually what compilers for shared genericity language are doing (well, at least some of them, depending on the language, other implementation techniques could be possible). Here is a (silly) example:

#include <string.h>
#include <iostream>

#ifdef NOT_CPP
class C
{
public:
    virtual template<typename T> int getAnInt(T const& v) {
        return getint(v);
    }
};
#else
class IntGetterBase
{
public:
    virtual int getTheInt() const = 0;
};

template<typename T>
class IntGetter: public IntGetterBase
{
public:
    IntGetter(T const& value) : myValue(value) {}
    virtual int getTheInt() const
    {
        return getint(myValue);
    }
private:
    T const& myValue;
};

template<typename T>
IntGetter<T> makeIntGetter(T const& value)
{
    return IntGetter<T>(value);
}

class C
{
public:
    virtual int getAnInt(IntGetterBase const& v)
    {
        return v.getTheInt();
    }
};
#endif

int getint(double d)
{
    return static_cast<int>(d);
}

int getint(char const* s)
{
    return strlen(s);
}

int main()
{
    C c;
    std::cout << c.getAnInt(makeIntGetter(3.141)) + c.getAnInt(makeIntGetter("foo")) << '\n';
    return 0;
}

Answer 4

I think it's so that compilers can generate vtable offsets as constants (whereas references to non-virtual functions are fixups).

When you compile a call to a template function, the compiler usually just puts a note in the binary, effectively telling the linker "please replace this note with a pointer to the correct function". The static linker does something similar, and eventually the loader fills in the value once the code has been loaded into memory and its address is known. This is called a fixup, because the loader "fixes up" the code by filling in the numbers it needs. Note that to generate the fixup, the compiler doesn't need to know what other functions exist in the class, it just needs to know the munged name of the function it wants.

However with virtual functions, the compiler usually emits code saying "get the vtable pointer out of the object, add 24 to it, load a function address, and call it". In order to know that the particular virtual function you want is at offset 24, the compiler needs to know about all the virtual functions in the class, and what order they're going to appear in the vtable. As things stand, the compiler does know this, because all the virtual functions are listed right there in the class definition. But in order to generate a virtual call where there are templated virtual functions, the compiler would need to know at the point of the call, what instantiations there are of the function template. It can't possibly know this, because different compilation units might instantiate different versions of a function template. So it couldn't work out what offset to use in the vtable.

Now, I suspect that a compiler could support virtual function templates by emitting, instead of a constant vtable offset, an integer fixup. That is, a note saying "please fill in the vtable offset of the virtual function with this munged name". Then the static linker might fill in the actual value once it knows what instantiations are available (at the point where it removes duplicate template instantiations in different compilation units). But that would impose a serious burden of work on the linker to figure out vtable layouts, which currently the compiler does by itself. Templates were deliberately specified to make things easier on implementers, in the hope that they might actually appear in the wild some time before C++0x...

So, I speculate that some reasoning along these lines led the standards committee to conclude that virtual function templates, even if implementable at all, were too difficult to implement and therefore could not be included in the standard.

Note that there's a fair bit of speculation in the above even before I try to read the minds of the committee: I am not the writer of a C++ implementation, and nor do I play one on television.