Why Do We Need a Virtual Table

Why do we need a virtual table?

Without virtual tables you wouldn't be able to make runtime polymorphism work since all references to functions would be bound at compile time. A simple example

struct Base {
virtual void f() { }
};

struct Derived : public Base {
virtual void f() { }
};

void callF( Base *o ) {
o->f();
}

int main() {
Derived d;
callF( &d );
}

Inside the function callF, you only know that o points to a Base object. However, at runtime, the code should call Derived::f (since Base::f is virtual). At compile time, the compiler can't know which code is going to be executed by the o->f() call since it doesn't know what o points to.

Hence, you need something called a "virtual table" which is basically a table of function pointers. Each object that has virtual functions has a "v-table pointer" that points to the virtual table for objects of its type.

The code in the callF function above then only needs to look up the entry for Base::f in the virtual table (which it finds based on the v-table pointer in the object), and then it calls the function that table entry points to. That might be Base::f but it is also possible that it points to something else - Derived::f, for instance.

This means that due to the virtual table, you're able to have polymorphism at runtime because the actual function being called is determined at runtime by looking up a function pointer in the virtual table and then calling the function via that pointer - instead of calling the function directly (as is the case for non-virtual functions).

Why does C++ RTTI require a virtual method table?

From a language perspective, the answer is: it doesn't. Nowhere in the C++ standard does it say how virtual functions are to be implemented. The compiler is free to make sure the correct function is called however it sees fit.

So, what would be gained by replacing the vptr (not the vtable) with an id and dropping the vtable? (replacing the vtable with an id doesn't really help anything whatsoever, once you have resolved vptr, you already know the run-time type)

How does the runtime know which function to actually call?

Consider:

template <int I>
struct A {
virtual void foo() {}
virtual void bar() {}
virtual ~A() {}
};

template <int I>
struct B : A<I> {
virtual void foo() {}
};

Suppose your compiler gives A<0> the ... lets call it vid ... 0 and A<1> the vid 1. Note that A<0> and A<1> are completely unrelated classes at this point. What happens if you say a0.foo() where a0 is an A<0>? At runtime a non-virtual function would just result in a statically dispatched call. But for a virtual function, the address of the function-to-call must be determined at runtime.

If all you had was vid 0 you'd still have to encode which function you want. This would result in a forest of if-else branches, to figure out the correct function pointer.

if (vid == 0) {
if (fid == 0) {
call A<0>::foo();
} else if (fid == 1) {
call A<0>::bar();
} /* ... */
} else if (vid == 1) {
if (fid == 0) {
call A<1>::foo();
} else if (fid == 1) {
call A<1>::bar();
} /* ... */
} /* ... */

This would get out of hand. Hence, the table. Add an offset that identifies the foo() function to the base of A<0>'s vtable and you have the address of the actual function to call. If you have a B<0> object on your hands instead, add the offset to that class' table's base pointer.

In theory compilers could emit if-else code for this but it turns out a pointer addition is faster and the resulting code smaller.

Why is a virtual table required only in case of virtual functions?

[If] there is no virtual table (meaning there is no pointer to where the function resides), how would the b.function1() call resolve?

There is a "pointer", inside the compiler as it's parsing and analysing your code. The compiler's the thing that decides where the function will be generated, so it knows how calls to said function should resolve. In concert with the linker, this all happens tidily within the build process.

The only reason that this doesn't work for virtual functions is that which function you call depends on a type known only at runtime; in fact the same function pointers are present verbatim in the virtual table, written there by the compiler. It's just that in this case, there are multiple to choose from, and they cannot be chosen from until long (read: potentially months or even years!) after the compiler ceases to be involved at all.

What is a vtable in C++

V-tables (or virtual tables) are how most C++ implementations do polymorphism. For each concrete implementation of a class, there is a table of function pointers to all the virtual methods. A pointer to this table (called the virtual table) exists as a data member in all the objects. When one calls a virtual method, we lookup the object's v-table and call the appropriate derived class method.

Are virtual tables part of the C++ standard?

No they are not defined by the standard. They are instead implementation concepts, rather like a stack or a heap.

The standard is helpful in permitting the implementation of polymorphism to be carried out in a certain way, for example, the address of the first member variable of a class doesn't need to be the address of an instance of that class if that class is a polymorphic type.

Why use a virtual table instead of function pointers?

Conceptually, it is the very same thing.

The virtual method table is nothing than a list of function pointers. It is not integrated in the object itself because it is static for the class of the object, so it can be shared among instances of the same class (saving computation power during initialization and memory during the objects whole lifetime).

In C++ specifically, each constructor sets the Virtual Method Table pointer to the pointer of the class to which it belongs. Thus, after the outermost constructor ran, the virtual methods resolve to the class of which the object is.

Is the order of the virtual table important?

The order of the vtable is important for things to work properly, but only to the compiler (i.e. you don't need to care because it takes care of it).

If the compiler put it out of order for itself, then yeah, things would break, because functions are looked up by offset (so an offset would yield a random function which would be catastrophic).But the average programmer doesn't need to worry about what order the vtable is in.

Why do we need virtual functions in C++?

Without "virtual" you get "early binding". Which implementation of the method is used gets decided at compile time based on the type of the pointer that you call through.

With "virtual" you get "late binding". Which implementation of the method is used gets decided at run time based on the type of the pointed-to object - what it was originally constructed as. This is not necessarily what you'd think based on the type of the pointer that points to that object.

class Base
{
public:
void Method1 () { std::cout << "Base::Method1" << std::endl; }
virtual void Method2 () { std::cout << "Base::Method2" << std::endl; }
};

class Derived : public Base
{
public:
void Method1 () { std::cout << "Derived::Method1" << std::endl; }
void Method2 () { std::cout << "Derived::Method2" << std::endl; }
};

Base* basePtr = new Derived ();
// Note - constructed as Derived, but pointer stored as Base*

basePtr->Method1 (); // Prints "Base::Method1"
basePtr->Method2 (); // Prints "Derived::Method2"

EDIT - see this question.

Also - this tutorial covers early and late binding in C++.



Related Topics



Leave a reply



Submit