Copy Semantics and the Rule of Three

Commonly referred to as "the three amigos", the

• copy constructor,
• copy assignment operator, and
• destructor

are sometimes generated by the compiler, when not defined directly by the programmer. Given a class definition such as the one below, the compiler will provide its own, synthesized version of the copy constructor and assignment operator for us.

class Basic
{
public:
    Basic()
        : m_data(new char[1024])
    {
    }

    ~Basic()
    {
        if (m_data)
            delete[] m_data;
         m_data = 0;
     }

private:
     char *m_data;
};

Here is how these default, compiler adaptations deal with different member types when we copy, assign to, or delete an object:

Default copy constructor:

• Primitive types: Value is copied
• Pointer types: Pointer is copied (shallow copy)
• Objects: Calls object's copy constructor

Default assignment operator:

• Primitive types: Value is copied
• Pointer types: Pointer is copied (shallow copy)
• Objects: Calls object's assignment operator

Default destructor:

• Primitive types: Does nothing
• Pointer types: Does nothing
• Objects: Calls object's destructor

With C++11 also comes two new amigos (more about these later), they are the:

• move constructor, and
• move assignment operator.

A shallow copy simply means that the value of the pointer is copied, i.e., the address of the data, not the data itself. In our class definition above, the compiler-generated copy constructor and assignment operator are implicit. Consequently, the two objects in the following statements will end up with m_data pointers pointing to the same data.

Basic obj1;
Basic obj2(obj1);

The problem with our compiler-generated copy constructor (or, the problem with the Basic class destructor, depending on how you look at it) manifests when the objects are destroyed.

int main(int argc, char **argv)
{
    Basic obj1;
    Basic obj2(obj1);
    return 0;
}

This program will crash, and here is why:

• The first object falls out of scope, and the data pointed to by m_data is released (in the destructor). So far, so good.
• The second object falls out of scope. Since this object's m_data pointer is still pointing to the address of the memory we just released, the program will attempt to release the same memory again, which will cause the program to crash.

Rule of three

Dr. Dobbs describes the problem in great detail, in an article by Andrew Koenig and Barbara E. Moo. The observations are summarized in the following two rules, collectively referred to as "the rule of three":

• If a class has a nonempty destructor, it almost always needs a copy constructor and an assignment operator.
• If a class has a nontrivial copy constructor or assignment operator, it usually needs both of these members and a destructor as well.

Simply put, the rule states that; if we define one of the three members, we should usually define all three of them. To do so, there are essentially four different approaches. Each will be described in more detail below.

• No copying
• Deep copy
• Reference counting
• Copy-on-write

The Evil Side of Returning a Member as const Reference

Returning a class member (e.g., from a getter function) has negative impact on performance when large objects and copying is involved. In some code I have come across, instead of simply returning a copy, a const reference is used as the return value. Here is an example:

class SomeClass
{
public:
    // ...
    const std::string &someString() const { return m_someStr; }

private:
    std::string m_someStr; 
}

Before elaborating any further on this, let's recall the different ways of passing arguments to functions.

Behind the Scenes: Polymorphism and Function Resolution in C++

This post describes how function resolution is typically (but not always) implemented by compilers.

For non-virtual functions, the compiler matches a function call with the corresponding function definition at compile-time. This is known as static binding.

Dynamic Polymorphism

When a member function is declared virtual, it can be overridden in a class that directly, or indirectly, derives from the class where it was declared (the base class).

class Base
{
public:
    virtual ~Base() {}
    virtual void hello() = 0;     // hello is pure virtual
};

class A : public Base
{
public:
    void hello() { std::cout << "A says 'hello'\n"; }
};

class B : public Base
{
public:
    void hello() { std::cout << "B says 'hello'\n"; }
};

void sayHello(Base& helloer)
{
    helloer.hello();
}

int main()
{
    Base *a = new A;
    Base *b = new B;
    sayHello(*a);
    sayHello(*b);
    delete a;
    delete b;
}

This program generates the following output:

A says 'hello'
B says 'hello'

Even though helloer is a reference to the base class, which function that will actually be called depends on the type of object we pass to sayHello(). This means, of course, that the function call to hello() must be resolved at run-time. This is referred to as dynamic binding. Internally this is achieved using two constructs known as v-tables (virtual tables, or dispatch tables) and v-pointers.

• A v-table is created for every class that: declares one or more virtual functions, or overrides a virtual function. (A)
• Such class is called a polymorphic class.
• Functions that override virtual functions from a parent class are adjusted in the v-table of the derived class. (B)
• The function call is resolved at run-time, from the matching index in the v-table, pointed to by the actual object's v-pointer. (C)
• Each object of a polymorphic class has its own v-pointer, but there is only one v-table per class.
• The v-tables and v-pointers are added by the compiler, and not visible to the programmer.

class Fruit
{
public:
    Fruit()
        : m_color("fruit-colored"),
          m_peeled(false)
    {}

    virtual ~Fruit() {}
    virtual void eat();    
    virtual void peel();
    void setColor(const std::string &color) { m_color = color; }
    const std::string &color() const { return m_color; }

protected:
    std::string m_color;
    bool m_peeled;
};

void Fruit::eat()
{
    std::cout << "Now eating this " << m_color << " fruit!\n";
}

void Fruit::peel()
{
    if (!m_peeled)
         m_peeled = true;
}

class Orange : public Fruit
{
public:
     Orange()
         : Fruit()
     {
         m_color = "orange";
     }
     void eat();
};

void Orange::eat()
{
    if (m_peeled) {
        Fruit::eat();
    } else {
        std::cout << "Can't eat orange before peeling it!\n";
    }
}

int main()
{
    Fruit *fruit1 = new Fruit;
    Fruit *fruit2 = new Orange;
    Fruit *fruit3 = new Orange;

    fruit1->eat();       // Now eating this fruit-colored fruit!
    fruit2->eat();       // Can't eat orange before peeling it! 

    fruit2->peel();
    fruit2->eat();       // Now eating this orange fruit! 

    std::cout << fruit2->color();        // orange

    delete fruit1;
    delete fruit2;
    delete fruit3;

    return 0;
}

Run this example from codepad: http://codepad.org/QUyLRq6l

Lambda Calculus Cheat Sheet

Click here to download in PDF format

The Meaning and Usefulness of Closures

In the previous post, I talked about the Fixed Point Combinator in λ-Calculus, and mentioned that combinator is another word for a closed lambda term, i.e., an expression with no free variables:

λx.x, λxy.x, λxy.y, etc.

Take for example the term λxy.y, which is really shorthand for λx.λy.y:

FV(λx.λy.y)   =   FV(λy.y) − {x}   =   FV(y) − {y} − {x}   =   {y} − {y} − {x}   =   Ø.

The opposite of a combinator – any expression that uses free variables, is called a closure. Even though the meaning of the term is slightly different in different contexts, the idea is basically the same:

Examining the term λx.(f x), we have the free variables FV(λx.f x) …

= FV(f x) − {x} = FV(f) ∪ FV(x) − {x} = {f} ∪ {x} − {x} = {f, x} − {x}
= {f}.

In Haskell, the definition for a function, func:

func f = \x -> f x

… uses the variable f, bound outside of the abstraction. It is therefore a closure.

The Pattern of Recursion and Fixed Point Combinators

Recursion is an interesting, and important computation tool that enables us to formulate patterns of self-similarity and express infinity, using a finite set of elements. There is a strong relation between recursion and the principle of induction in mathematics. Imperative programming languages usually allow recursion in a program to take place by letting us define a function that calls itself. Here is a simple recursive function in C++:

#include <iostream.h>

void count(int n)
{
    std::cout << "Counting: " << n << "\n";
    if (n < 5) {
        count(n+1);
    }
}

int main(int argc, char **argv)
{
    count(1);
    return 0;
}

Run this example from codepad:
http://codepad.org/YmxQcTIX

In functional programming, recursion has a much more central position. Purely functional languages do not define any looping constructs, but instead rely entirely on recursion to achieve iterative algorithms. Many data types are defined recursively. In Haskell, recursion even allows us to define (conceptually) infinite data structures:

n = 5 : n
take 3 n                -- [5, 5, 5]

Codepad: http://codepad.org/sRbFkSH5

Here, we take the first three elements from an infinite list of fives. The list n is defined as a single element, 5, followed by a list – itself.

n is a 5, followed by n, which is a 5 followed by n, which is a 5 followed …

A Reminder About Implicit Conversion and Default Value Arguments

Implicit conversion is usually undesirable, and as a general rule, single-parameter constructors should be explicit unless there is a specific reason otherwise. Using the explicit keyword, we declare a constructor to be non-converting:

class Stuff
{
public:
    explicit Stuff(int n)
    {
    }

    // ...
}

Stuff stuff = 5;            
// error: conversion from ‘int’ to non-scalar type ‘Stuff’ requested

Stuff stuff(5);             // ok

But what if the constructor takes more than one argument, and default values are specified for the additional, or for all arguments? We can still call this constructor using one parameter only. Consider the following example:

class Stuff
{
public:
    Stuff(int x, int y = 0, int z = 1)
    {
    }

    // ....
}

Stuff stuff = 5;            // aargh!

The explicit keyword should be used here as well. So, the rule actually applies to:

• single argument constructors, and
• multiple argument constructors, if all OR all except one of the arguments have a default value.