Month: May 2010

Why Member Functions are not Virtual by Default


A common error in C++ that the compiler cannot catch for you, is getting a base function called instead of the expected overridden one because you forgot to make it virtual. Example:

#include <iostream>
using namespace std;

struct Base {
    void print() {
        cout << "Base" << endl;
    }
};

struct Derived : public Base {
    void print() {
        cout << "Derived" << endl;
    }
};

int main() {
    Base b;
    Derived d;
    b.print(); //Base
    d.print(); //Derived
    Base *bp = &d;
    bp->print(); //Base (Here we would like to see Derived)
}

In Java, this would print Derived, as methods are virtual by default. In C++ however, this is not so. But if we add virtual to the declaration, we get the result we are looking for:

(...)
struct Base {
    virtual void print() {
(...)
    b.print(); //Base
    d.print(); //Derived
    bp->print(); //Derived

Why is this so? Why can’t all member functions be virtual, just like in most other object oriented languages? There are a couple of reasons:

Do not pay for what you do not need

There is an important guideline in the design of C++, that a feature should not incur any overhead when it is not used. And polymorphism is impossible to achieve without at least a small overhead. The way this is usually implemented is with a table of function pointers for each class, called a virtual table, or just vtbl. In our example, Base and Derived would each have a table with one entry, pointing to Base::print() and Derived::print(), respectively. Note that there is only one vtbl per class, not per object, so this overhead is not large, but it is there.

In addition to a vtbl per class, every object has a pointer to the vtbl of its class, adding (usually) one word to each object. This is another small spacial overhead.

Finally, there is a small overhead in time as well, as functions get an extra level of indirection as they are resolved through the vtbl. This is however usually negligible.

All in all, the overhead is so small that one might challenge the non-virtual default. But still, a rule is a rule. And there is more!

Backward compatibility

C++ was designed to be as close to 100% compatible with C as possible. If you have an object of a really simple class*, you can pass it to a C function just as if it were an instance of a good old C struct, and be sure that it will be ok. Its size is just the combined size of its data members (plus padding, if any), and it can be copied with memcpy(). As soon as you add a virtual method, the size of the object is no longer the size expected by C, it has an extra magic word (or maybe more) that C won’t recognize, and it cannot be portably used with memcpy().

And a third one?

There is a third argument as well, arguing that virtual methods break encapsulation, and should be used with care. While I agree, other languages have solved this in a perfectly good manner, by having member functions virtual by default, but making it possible to disallow inheritance. Java does this by the final keyword. Which is why I don’t really count this as an argument against virtual-by-default.

So if you don’t want to pay for what you don’t use, and if you depend on C, you cannot have virtual-by-default.

* More specifically a Plain Old Data Structure (POD), which I won’t cover here.

 

New sourcecode formatting


Thanks to Alf, I have discovered the WordPress [sourcecode] tag. Where I would previously use <code> and <pre> and get the following result:

int true_random() {
    return 4; //Generated by fair roll of a die
}

I now use [sourcecode language="cpp"] ... [/sourcecode] and get the following:

int true_random() {
    return 4; //Generated by fair roll of a die
}

The syntax highlighting and line numbering is done client-side with JavaScript, but even without JavaScript the code looks nicely formatted with <pre>.

I have gone through all my older posts and updated them to use the new tag, please let me know if you see any spots I missed, or any errors I made in the process.

Puzzle #0: Call Sequence


Here’s a puzzle that should highlight a couple of interesting features in C++:

What is the output of the following program?

#include <iostream>;
using namespace std;

int main();

void term() {
    cout << "term()" << endl;
    main();
}

struct Positive {
    Positive(int i) {
        set_terminate(term);
        cout << "Positive::Positive(" << i << ")" << endl;
        if (i <= 0)
            throw main;
    }
};

Positive n(-1);

int main() {
    cout << "main()" << endl;
    Positive p(1);
}

If you just want the answer, you will find it at the bottom of this post. But first, I will go through the why.

Lines 1-2 are uninteresting. Lines 4-18 contain all the magic, but I’ll come back to those, I want to go through the program in chronological order as it is being executed. The entry point for this program is not main(), but rather the definition of Positive n(-1). This variable is global, and so will be initialized before main() is called. To initialize it, its constructor is called with i = -1, and so the real action starts on line 13.

On line 13, I use set_terminate() to set a termination handler. The termination handler will be called if a thrown exception is not handled. Otherwise, this statement has no visible immediate effect. We then encounter the first printout of this program, on line 14:

Positive::Positive(-1)

Our Positive class is however designed to only handle positive numbers, and throws on line 16. It is set to throw main, but this is really just a decoy. In C++, you can throw whatever you want, I happen to throw a function pointer to main(). In particular, this does not mean that main() is called.

The exception thrown on line 16 is never handled, and so the builtin terminate() calls the termination handler set_terminate(), which is defined on lines 6-9. Now we encounter our second printout:

term()

This is a straightforward cout on line 7. Then, we manually call main(). main is just a normal function, and even though it is special in that C++ will call it for you at startup, you are free to call it manually whenever you want. This is the third printout:

main()

main() then attempts to instantiate the local Positive object p(1). This calls the Positive constructor, which prints out

Positive::Positive(1)

This is a valid positive number, so no more exceptions are thrown. Control is returned to main(), which returns control to term(), which, being a termination handler, is not allowed to return, but still attempts to do so. I cannot find anything in the standard about what exactly is supposed to happen in this case, so I guess this is undefined behaviour. No matter what, returning doesn’t make any sense, as there is nowhere to return to. What happens on my system (gcc@linux) is program abortion with SIGABRT. What happens on yours?

Finally, the complete output of the program

$ ./outsidemain
Positive::Positive(-1)
term()
main()
Positive::Positive(1)
Aborted

This is probably not the most useful post I have written, but it highlights a few interesting points, and making a puzzle is always fun.

Why Initializer Lists don’t Work with Base Members


As you might know, you cannot initialize a base member in a derived constructors initializer list:

struct Base {
    int base_mem;
};

struct Derived : public Base {
    Derived(int i) : base_mem(i) {} //Error!
};

int main() {
    Derived(42);
}

This is not allowed. But why? There are two key points to get here:

1: What is the point of an initializer list in the first place?
If you don’t use an initializer list, but initialize all your objects in the constructor body, they will first be created once, even before the constructor body, and then you will re-assign them. This might be a performance-problem, but could also be a bigger problem if the constructors of those types have side-effects like hitting a database, acquiring some resource etc.

2: When are the different parts of an object constructed?
When constructing a Derived object, the first thing that happens is that Bases default constructor is invoked. In this example, I didn’t declare one, so the compiler will generate one for me. When this constructor is done, including both its initializer-list and its body, it is Derived()s turn.

This means that when C++ gets around to Derived()s initializer, the Base part of the object has already been created, all Base members are initialized, and we have lost the advantage of using initializer lists.

So how do we solve this? Make sure the Derived constructor explicitly specifies which Base constructor to use, and have this one initialize the variable. Example:

struct Base {
    Base(int i) : base_mem(i) {}
    int base_mem;
};

struct Derived : public Base {
    Derived(int i) : Base(i) {}
};

Array Initialization Initializes all Elements


I was talking about C++ with a Java programmer the other day, as he had to work on a bit of C++ code. I discovered that it isn’t necessarily obvious that all the elements in an array are constructed when the array is initialized. That is however always the case.

For arrays of built-in types, the values aren’t actually set to a specific default (except for non-local and static arrays), and will end up having arbitrary values.

For arrays of a user-defined type, the default constructor is used for all the array elements. If you don’t want this behaviour, you need to use an array of pointers. All the elements will still be initialized, but the elements being initialized are now the pointers, not the actual objects. It is worth mentioning that pointers count as a built in type, and elements of non-local and static arrays will have undefined values. In particular, they are not initialized to point to NULL.

The reason why all the elements are initialized is that there is no such thing as a “null-object”. You can have a null-pointer not pointing to anything, but you cannot have an actual object that isn’t really an object, so to speak. This of course goes for Java as well, but here, an array of a user-defined type is actually an array of pointers, even though you don’t see any *s in the code. (Java uses pointer semantics for user-defined types and value semantics for built-in types.)

Here is a summary using actual C++ code:

int ints[10]; //Non-local array, all elements ==0
int func() {
    int ints[10]; //Local array, no default value is set, but all elements are fully usable ints.
    static int sints[10]; //Static local array, all elements are initialized to 0
    Foo foos[10]; //User-defined type, all elements are constructed using the default constructor Foo::Foo();
    Foo *foos[10]; //Local array, no default value is set. The pointers point all over the place.
}

If your class has no public default constructor, it is impossible to create an array of such objects:

class NoDefault {
private:
    NoDefault(); //Make default constructor private, and hence unusable
};
NoDefault nodefaults[10]; //Impossible!
NoDefault *pnodefaults[10]; //This is fine, no objects are constructed, only pointers.

Note also that you cannot have an array of references. The most obvious reason is that a reference must always refer to an object. There is no such thing as a “null-reference”. One could however imagine getting around this using an initializer list, like this:

    Foo f1, f2;
    Foo& foors[2] = {f1, f2};

Now we don’t try to initialize references that don’t refer to anything. This is still not allowed though. One reason is that you cannot point to a reference, so accessing elements in the array in a normal sense like foors[1] wouldn’t make sense. In C++, you can only have arrays of objects, and references are not objects. (Pointers are objects though.)

In summary:

  • Elements of arrays of a user-defined type are initialized using the default constructor.
  • Elements of local non-static arrays of a built-in type are not explicitly initialized, and will have arbitrary values.
  • Elements of non-local and static arrays of a built-in type are initialized to their default value (0).
  • You cannot have an array of a user-defined type without a public default constructor.
  • You can only have arrays of objects and pointers, not references.