A virtual method table, virtual function table, or vtable , is a mechanism used in Programming languages to support dynamic polymorphism (computer science), i.e., run-time method binding.

Suppose a program contains several classes in an inheritance hierarchy: a superclass, Cat, and two subclasses, Tiger and HouseCat. Class Cat defines a method named speak but provides no implementation. Instead, its subclasses must provide an appropriate implementation (i.e., either meow or roar). In a compiled language such as C plus plus, the run-time environment must be able to determine which version of the speak method to call through a base class pointer. This is called polymorphism (computer science) on the programmer s side, but is implemented using virtual method tables.

When you compile a derived class, the compiler associates with the class data and function pointers from its base classes in addition to those of the derived class itself. In this example, the compiler s representation of a Tiger also includes everything a Cat does. The compiler does not duplicate the actual function code. Rather, it uses a pointer to the parent class code. (Duplicating code would cause bloat and redundancy). So when you call a method through a derived class, the compiler knows exactly where to find the relevant code. But if you call a method through the base class, the compiler cannot necessarily know what code to execute. It isn t determined until run time to which derived class the object belongs, and different derived classes can have different methods. For example, a virtual method (C plus plus) or a non-final method (Java programming language). Instead, the compiler creates a table that is a dispatch table containing pointers to the implementations of each possible derived class.

If a program references an object through a base class pointer or reference at run time, the program uses the table to look up which method to call, based on to which derived class the particular object belongs. This does incur a speed hit compared to using the single compiled-in pointer that is possible with a non-virtual method. However, as compilers mature, they are better able to optimize virtual function tables as well as the code that uses them.

=Implementation Example=

An object s dispatch table will contain the addresses of the object s dynamically bound methods. Method calls are performed by fetching the method s address from the object s dispatch table. The dispatch table is the same for all objects belonging to the same class, and is therefore typically shared between them. Objects belonging to type-compatible classes (for example siblings in an inheritance hierarchy) will have dispatch tables with the same layout: the address of a given method will appear at the same offset for all type-compatible classes. Thus, fetching the method s address from a given dispatch table offset will get the method corresponding to the object s actual class. (Ellis & Stroustrup 1990, pp. 227–232)

Consider the SymmetricAlgorithm and the BlockCipher abstract classes, as declared in the cryptographic library:

class SymmetricAlgorithm : public Algorithm { public: virtual void set_key(const byte[], u32bit) throw(InvalidKeyLength) = 0; virtual bool valid_keylength(u32bit) const; SymmetricAlgorithm(const std::string&, u32bit, u32bit, u32bit); };

class BlockCipher : public SymmetricAlgorithm { public: virtual void encrypt(const byte[], byte[]) const = 0; virtual void decrypt(const byte[], byte[]) const = 0; virtual void encrypt(byte block[]) const = 0; virtual void decrypt(byte block[]) const = 0; BlockCipher(const std::string&, u32bit, u32bit, u32bit = 0, u32bit = 1); virtual ~BlockCipher() {} };

used to derive the following DES class:

class DES : public BlockCipher { public: void encrypt(const byte[BLOCKSIZE], byte[BLOCKSIZE]) const; void decrypt(const byte[BLOCKSIZE], byte[BLOCKSIZE]) const; void encrypt(byte block[BLOCKSIZE]) const; void decrypt(byte block[BLOCKSIZE]) const; void set_key(const byte[], u32bit = KEYLENGTH) throw(InvalidKeyLength); void clear() throw(); DES() : BlockCipher(name(), BLOCKSIZE, KEYLENGTH); };

The corresponding table will be:

OpenCL::DES virtual function table: .long OpenCL::DES type_info function .long OpenCL::DES::clear(void) .long OpenCL::DES::~DES(void) .long OpenCL::DES::set_key(u_char const *, u_int) .long OpenCL::SymmetricAlgorithm::valid_keylength(u_int) const .long OpenCL::DES::encrypt(u_char const *, u_char *) const .long OpenCL::DES::decrypt(u_char const *, u_char *) const .long OpenCL::DES::encrypt(u_char *) const .long OpenCL::DES::decrypt(u_char *) const

Note how the valid_keylength method is inherited from the SymmetricAlgorithm class.

Now consider a DES sibling class TripleDES:

class TripleDES : public BlockCipher { public: void encrypt(const byte[BLOCKSIZE], byte[BLOCKSIZE]) const; void decrypt(const byte[BLOCKSIZE], byte[BLOCKSIZE]) const; void encrypt(byte block[BLOCKSIZE]) const; void decrypt(byte block[BLOCKSIZE]) const; void set_key(const byte[], u32bit = KEYLENGTH) throw(InvalidKeyLength); void clear() throw(); TripleDES() : BlockCipher(name(), BLOCKSIZE, KEYLENGTH); };

This will implemented with a table with exactly the same layout, but different contents:

OpenCL::TripleDES virtual function table: .long OpenCL::TripleDES type_info function .long OpenCL::TripleDES::clear(void) .long OpenCL::TripleDES::~TripleDES(void) .long OpenCL::TripleDES::set_key(u_char const *, u_int) .long OpenCL::SymmetricAlgorithm::valid_keylength(u_int) const .long OpenCL::TripleDES::encrypt(u_char const *, u_char *) const .long OpenCL::TripleDES::decrypt(u_char const *, u_char *) const .long OpenCL::TripleDES::encrypt(u_char *) const .long OpenCL::TripleDES::decrypt(u_char *) const

Thus, method calls using a pointer to a SymmetricAlgorithm class will use the object s virtual method table to fetch the method address corresponding to the object s type.

=References=