How indexing within the virtual table is decided in c++?

Question

Consider the below code.

  #include<iostream>

using namespace std;

class Base
{
public:
    virtual void function1() {cout<<"Base:function1()\n";};
    virtual void function2() {cout<<"Base:function1()\n";};
};

class D1: public Base
{
public:
    virtual void function1() {cout<<"D1:function1()\n";};
    virtual void function2() {cout<<"D1:function2()\n";};
};


int main()
{
    Base *ptr= new D1;

    ptr->function1();
    ptr->function2();

    return 0;
}

The ptr will be pointing to D1 obj. so whenever i call ptr->function1(), the function address is fetched from virtual table of class D1. It works same way for ptr->function2() as well.

In this case the vtable[0] will have function pointer to function1(), vtable[1] will have function pointer to function2().

My question is how function call to vtable index mapping happens?

How ptr->function1() & ptr->function2() indexes to vtable[0] & vtable[1] respectively?

Answer 1

The first element of the class is usuaylly the (hidden) vtable pointer - vptr. For a polymorphic class, the vtable is first initialized to the vtable of base class in the base class constructor. Then, when the derived class constructor executes the same vtable pointer is initialized to point to the derived class vtable. Note that the base class vtable points to base version of function1 and function2 whereas derived class vtable points to derived version of function1 and function2. Now, when a pointer to base class points to an instance of derived class, this is what 'typically may' happen:

class base
{
    //int* vptr;            //hidden vtable pointer, created by compiler for polymorphic class. vptr points to base class vtable for base clas objects
public:
    virtual void function1(){std::cout <<"base::function1()"<<std::endl;}
    virtual void function2(){std::cout <<"base::function2()"<<std::endl;}
};

class derived: public base
{
    //int* vptr;            //hidden vtable pointer, inherited from the base class. vptr points to derived class vtable for derived class objects
public:
    virtual void function1(){std::cout <<"derived::function1()"<<std::endl;}
    virtual void function2(){std::cout <<"derived::function2()"<<std::endl;}
};


int main()
{
    typedef void (*vtableFnPtr)();      

    base* pBase;
    base base_obj;
    derived derived_obj;

    pBase = &derived_obj;                   //base pointer pointing to derived object

    //one of the several possible implementations by compiler
    int* vtableCallBack = *(int**)&derived_obj; //read the address of vtable pointed by the hidden vptr in the derived_obj

    //pBase->function1();
    ((vtableFnPtr)vtableCallBack[0])();     //calls derived::function1(), when application calls pBase->function1();

    //pBase->function2();
    ((vtableFnPtr)vtableCallBack[1])();     //calls derived::function2(), when application calls pBase->function2();

    pBase = &base_obj;

    //one of the several possible implementations by compiler
    vtableCallBack = *(int**)&base_obj;     //base pointer pointing to base object

    //pBase->function1();
    ((vtableFnPtr)vtableCallBack[0])();     //calls base::function1(), when application calls pBase->function1();

    //pBase->function2();
    ((vtableFnPtr)vtableCallBack[1])();     //calls base::function2(), when application calls pBase->function2();

}

Note that the C++ compiler does not say anything about the implementation methodology to be used for achieving polymorphic behavior and hence it is completly upto the compiler to use vtable or any other implementation as long as the behavior is polymorphic. However, vtable remains one of the most widely used methods to achieve polymorphic behavior.

Answer 2

"All problems in computer science can be solved by another level of indirection"

I referred to excellent and detail blog post and have tried below to explain use of vtable for your simple example. See if you are read thorough it.

struct Base;
// enumerates all virtual functions of A    
struct table_Base {
  void (*function1)(struct Base *this);
  void (*function2)(struct Base *this);
};

struct Base {
  const struct table_Base *pvtable; // table maintains pointers to virtual functions. Eventually to implementations
  int data;
};

void Base_function1(struct Base *this) {
  std::cout << "Base:function1()" << std::endl;
}

void Base_function2(struct Base *this) {
  std::cout << "Base:function2()" << std::endl;
}

// table data for Base
static const struct table_Base table_Base_for_Base = { Base_function1,  Base_function2};

void Base_Ctor(struct Base *this) {      
  this->pvtable = &table_Base_for_Base;
  this->data = 1;  
}

// Now for class D1
struct D1;    
struct table_D1 {
  void (*function1)(struct D1 *this);
  void (*function2)(struct D1 *this);
};

struct D1 {
  struct Base base;
  const struct table_D1 *pvtable;
  int more_data;
};

void D1_function1(struct D1 *this) {
  std::cout << "D1:function1()" << std::endl;
}

void D1_function2(struct D1 *this) {
  std::cout << "D1:function2()" << std::endl;
}

// Important functions that do re-direction
void D1Base_function1(struct Base *this) {
  D1_function1((struct D1*) this);
}

void D1Base_function2(struct Base *this) {
  D1_function2((struct D1*) this);
}

// table data for D1
static const struct table_D1 table_D1_for_D1 = {D1_function1,  D1_function2};

// IMPORTANT table
static const struct table_Base table_Base_for_D1 = {D1Base_function1,  D1Base_function2};

// Constructor for derived class D1
void D1_Ctor(struct D1 *this) 
{  
  Base_Ctor(&this->base); // Base class vtable is initialized.

  // Now, Override virtual function pointers   
  this->base.vtbl = &table_Base_for_D1; // Replace the vtable
  this->mode_data = 100;  
}

Internally this is the logic followed by the compiler to achieve correct behavior for virtual functions.

ptr->function1();
ptr->function2();

You can trace the method calls above using vtable logic explained and see if it works.