How does the C++ compiler know which implementation of a virtual function to call?

Question

Here is an example of polymorphism from http://www.cplusplus.com/doc/tutorial/polymorphism.html (edited for readability):

// abstract base class
#include <iostream>
using namespace std;

class Polygon {
    protected:
        int width;
        int height;
    public:
        void set_values(int a, int b) { width = a; height = b; }
        virtual int area(void) =0;
};

class Rectangle: public Polygon {
    public:
        int area(void) { return width * height; }
};

class Triangle: public Polygon {
    public:
        int area(void) { return width * height / 2; }
};

int main () {
    Rectangle rect;
    Triangle trgl;
    Polygon * ppoly1 = &rect;
    Polygon * ppoly2 = &trgl;
    ppoly1->set_values (4,5);
    ppoly2->set_values (4,5);
    cout << ppoly1->area() << endl; // outputs 20
    cout << ppoly2->area() << endl; // outputs 10
    return 0;
}

My question is how does the compiler know that ppoly1 is a Rectangle and that ppoly2 is a Triangle, so that it can call the correct area() function? It could find that out by looking at the "Polygon * ppoly1 = ▭" line and knowing that rect is a Rectangle, but that wouldn't work in all cases, would it? What if you did something like this?

cout << ((Polygon *)0x12345678)->area() << endl;

Assuming that you're allowed to access that random area of memory.

I would test this out but I can't on the computer I'm on at the moment.

(I hope I'm not missing something obvious...)

Answer 1

Each object (that belongs to a class with at least one virtual function) has a pointer, called a vptr. It points to the vtbl of its actual class (which each class with virtual functions has at least one of; possibly more than one for some multiple-inheritance scenarios).

The vtbl contains a bunch of pointers, one for each virtual function. So at runtime, the code just uses the object's vptr to locate the vtbl, and from there the address of the actual overridden function.

In your specific case, Polygon, Rectangle, and Triangle each has a vtbl, each with one entry pointing to its relevant area method. Your ppoly1 will have a vptr pointing to Rectangle's vtbl, and ppoly2 similarly with Triangle's vtbl. Hope this helps!

Answer 2

Chris Jester-Young gives the basic answer to this question.

Wikipedia has a more in depth treatment.

If you want to know the full details for how this type of thing works (and for all type of inheritance, including multiple and virtual inheritance), one of the best resources is Stan Lippman's "Inside the C++ Object Model".

Answer 3

Disregarding aspects of binding, it's not actually the compiler that determines this.

It is the C++ runtime that evaluates, via vtables and vpointers, what the derived object actually is at runtime.

I highly recommend Scott Meyer's book Effective C++ for good descriptions on how this is done.

Even covers how default parameters in a method in a derived class are ignored and any default parameters in a base class are still taken! That's binding.

Answer 4

To answer the second part of your question: that address probably won't have a v-table in the right place, and madness will ensue. Also, it's undefined according to the standard.

Answer 5

cout << ((Polygon *)0x12345678)->area() << endl;

This code is a disaster waiting to happen. The compiler will compile it all right but when it comes to run time, you will not be pointing to a valid v-table and if you are lucky the program will just crash.

In C++, you shouldn't use old C-style casts like this, you should use dynamic_cast like so:

Polygon *obj = dynamic_cast<Polygon *>(0x12345678)->area();
ASSERT(obj != NULL);

cout << obj->area() << endl;

dynamic_cast will return NULL if the given pointer is not a valid Polygon object so it will be trapped by the ASSERT.

Answer 6

Virtual function tables. To wit, both of your Polygon-derived objects have a virtual function table that contains function pointers to the implementations of all their (non-static) functions; and when you instantiate a Triangle, the virtual function pointer for the area() function points to the Triangle::area() function; when you instantiate a Rectangle, the area() function points to the Rectangle::area() function. Because virtual function pointers are stored along with the data for an object in memory, every time you reference that object as a Polygon, the appropriate area() for that object will be used.