C++ Template Meta Programming – Part 1

You may have heard of template meta programming before. It is a technique that uses the features of C++ templates to shift program execution from runtime to compile time. Basically, we are going to trick the compiler into running our code at compile time and then putting the output into our executable.

Let’s look at an example:

#include <iostream>

template<int n>
struct Factorial
{
    enum { value = n * Factorial<n - 1>::value };
};

template<>
struct Factorial<0>
{
    enum {value = 1};
};

int main() {
    std::cout << Factorial<5>::value << std::endl;
    return 0;
}

What does this code do? Well, first we define a templated struct that takes an integer as a parameter.

template<int n>
struct Factorial
{
    enum { value = n * Factorial<n - 1>::value };
};

Notice, that inside this struct, we define a field named value. This field is defined to be n times the value field of Factorial<n-1>. We are also using total template specialisation:

template<>
struct Factorial<0>
{
    enum {value = 1};
};

This means that if we ever specialise the Factorial template with the parameter 0 it will use this version of Factorial that defines the value field to be 1.

So, when we specialise the Factorial template with the parameter 5, the compiler creates the classes Factorial<5>, Factorial<4>, Factorial<3>, Factorial<2>, Factorial<1> and Factorial<0>. Then it computes the value field for each of these classes. The value field for Factorial<0> is 1. The compiler calculates the value field for each successive Factorial<n> by multiply n times the value field of the previous Factorial specialisation. So we have defined a recursion that calculates the factorial of an integer. What is weird is that this calculation happens entirely at compile time. When we run this code, the first six values of the factorial series have already been calculated, and we will just be reading the last value from the code the compiler has created.

We can do exactly the same thing with the Fibonacci numbers:

#include <iostream>

template<int n>
struct Fibonnaci
{
    enum { value =  Fibonnaci<n - 1>::value + Fibonnaci<n - 2>::value };
};

template<>
struct Fibonnaci<0>
{
    enum {value = 1};
};

template<>
struct Fibonnaci<1>
{
    enum {value = 1};
};

int main() {
    std::cout << Fibonnaci<5>::value << std::endl;
    return 0;
}

So we have seen how to do recursions via template meta programming. Next we will see how to write conditional statements that are evaluated at compile time.

Generic Programming, C++ vs C#

At first glance, C++ and C# are two very similar languages. However the more you look, the more you realise that they are two very different beasts. Today we are going to talk about how these two languages handle generic programming.

The Implementation

First lets look at how the two languages implement generic programming. In C++ we can define a template for a class like this:

template<typename T>
class Holder
{
public:
   T value;
};

We can then use that template in our code like so:

Holder<int> intHolder;

When the compiler sees this usage, it goes back to the definition of the Holder class and generates a new class. In this new class it replaces the type variable T with the type int. This new class generated by the compiler is what the name Holder<int> refers to. This class gets compiled as normal. It would be completely equivalent if we had instead defined a Holder class specialised to ints ourselves:

class Holder_int
{
public:
   int value;
};

If we also specialise our Holder class with the type double, the compiler will generate another version of Holder, this time with type variable T replaced by the type double.

Now, in C# the equivalent to the above example is:

class Holder<T>
{
    public T value;
}

This looks very similar, however the underlying implementation is very different. In C# generics are resolved at runtime not at compile time. The Holder class we defined will remain generic when it is complied to intermediate language. When we run code that uses the Holder class, the just in time compiler generates the different machine code implementations for whatever specialisation of Holder we have used. The JIT compiler will generate separate versions of the Holder class for each value type used. However, it generates a single implementation that is shared for all reference types. This works because reference types are implemented as pointers, which are always the same size, regardless of the type they are pointing to.

Constraints

Usually we need more than just a typename in our generic code. We want to do things with the values of that type. So, suppose we wanted to add a method to our generic Holder class that calls a length method on our inner object of type T. In C# we do it like this:

public interface IHasLength
{
   int length();
};

public class Holder<T> where T : IHasLength
{
   public T value;
   int GetLength()
   {
      return T.length();
   }
}

The syntax, class Holder where T : IHasLength specifies that whatever type this generic is specialised with must implement the interface IHasLength. With that constraint, the compiler knows that whatever type we specialise this class with will have a Length method, so we can call it freely in our generic code. There are five different kinds of constraint we can impose. We have just seen the interface constraint. We can also constrain a type parameter to be a subclass of a given class, to have a default constructor, to be a value type or to be a reference type.

In C++ we don’t need explicit type constraints. Instead there are implicit type constraints. For example, suppose we have the following code:

template<typename T>
class Holder
{
public:
   T value;
   int GetLength()
   {
      return value.length();
   }

}

Here, we have just written our code assuming that an object of type T has a Length method that returns a value that can be cast to an integer. We do not need to specify this constraint ourselves. We can instantiate this class and specify a specific type, for example via:

Holder<string> stringHolder();

The compiler then generates the version of Holder specialised to the type string. This new class is then compiled as normal. As the string class has a length method, this will compile successfully. However, suppose we instantiated our class like so:

Holder<int> intHolder();

The int type does not have a length method, so the class generated by this code will not compile.

Whereas the constraints on C# generic types are quite limited, in C++ we can use any constraint at all. For example, it is impossible to impose a constraint on a generic type parameter in C# that it must have an addition operator. This is because there is no interface that all types that have an addition operator implement. However, in C++, we just use the addition operator in our template code and the compiler will make sure that the specific types we use have an addition operator. This all works in C++ because the types are resolved at compile time, so the compiler can check that types satisfy the implicit interface then. In C# the type substitution does not actually happen until runtime, so it would be impossible for the C# compiler to do a check like this.

Beyond Type Parameters

Another cool feature of C++ templates is that we can pass values to our templates as well as type parameters. For example, in C++ the following code is valid:

tempate<int n>
bool LessThan(int x)
{
   return x < n;
}

This defines a template function with a parameter of type int. We can use this template like so:

bool result = LessThan<10>(5);

The code LessThan<10> causes the compiler to generate a version of the LessThan method with 10 substituted for the parameter n. You can’t do anything like this in C#.

Overall, C++ templates are a lot more powerful and flexible than C# generics. Of course this means that it is a lot easier to trip yourself up with C++ templates. And when things do go wrong the compiler output is probably going to be completely incomprehensible. As C++ generates separate code for every different version of a template that gets used this has the potential to create very large binaries. However, on a modern system this probably won’t really be a problem.

Finally, the rule of five in C++

Ok, we’ve talked in detail about the special copy and move methods. It’s time to put them together in a reasonable example. Suppose we have the Bond class as defined in our previous examples. We are going to define a Portfolio class that represents a collection of Bonds. The rule of five refers to the four methods we have discussed so far, along with the destructor. The destructor is just a method that frees up whatever resources your class has a reference to. The rule of five states that if you define any of these five special methods, you ought to define them all.

Let’s look at the code.

#include <string>
#include <algorithm>

class Portfolio
{
private:
	std::string Name;
	Bond* Bonds;
	int Size;
public:
	Portfolio(std::string name, Bond* bonds, int size) : Name(name), Bonds(bonds), Size(size)
	{
	}

	Portfolio(const Portfolio& lhs) : Name(lhs.Name)
	{
		std::copy(lhs.Bonds, lhs.Bonds + lhs.Size, Bonds);
	}

	Portfolio& operator=(const Portfolio& lhs)
	{
		if(&lhs != this)
		{
			delete[] Bonds;
		        std::copy(lhs.Bonds, lhs.Bonds + lhs.Size, Bonds);	
			Name = lhs.Name;
			Size = lhs.Size;
		}
		return *this;
	}
		
	Portfolio(Portfolio&& lhs) : Name(lhs.Name), Bonds(lhs.Bonds)
	{
		lhs.Bonds = nullptr;
		lhs.Size = 0;
	}

	Portfolio& operator=(Portfolio&& lhs)
	{
		if(&lhs != this)
		{
			delete[] Bonds;
			Bonds = lhs.Bonds;	
			Name = lhs.Name;
			Size = lhs.Size;
			lhs.Size = 0;
			lhs.Bonds = nullptr;
		}
		return *this;
	}

	~Portfolio()
	{
		delete[] Bonds;
	}
};

Now this code isn’t perfect, in fact we’ll be refining it in future posts. But I think it is a good demonstration of the various special methods in action.

Our Portfolio class manages a resource, a block of memory containing Bond objects. Let’s look at the copy methods first. Whenever we copy a portfolio we want to make a copy of it’s set of bonds. So our copy construction uses the std::copy function to make a deep copy of this resource. When we copy assign, we first free whatever memory we currently have a pointer to. Then we do a deep copy of the array of Bonds. Also, when assigning we check to make sure that we aren’t self assigning.

When we move, we don’t need to copy the entire portfolio of bonds. So, in the move constructor we just copy the pointer to the array, rather than copying its contents. Now that we have moved our array into a new object we don’t want to leave another Portfolio with a pointer to it, so we set the array pointer in the source object to nullptr. Just like with copy assignment, when move assigning, first we check for self assignment. Then we delete the memory we currently have a pointer to, and copy the pointer from the source object. Finally, as before, we set the source object’s pointer to nullptr.

Moving in C++

So, in a previous post we covered the copy constructor and copy assignment operator. We also had a look at copy elision. Now it’s time to talk about the move constructor and move assignment operator. To explain what these special move methods are and why we need them, we are going to have another quick look at our Bond example. As before we are including a subclass to prevent elision.

#include <iostream>

class Bond
{
private:
	double Rate;
public:
	Bond(double rate) : Rate(rate)
	{
               std::cout << "Constructing" << std::endl;
	}

        // copy assignment
       	Bond& operator=(const Bond& other)
	{
		std::cout << "Copy assigning" << std::endl;
		Rate = other.Rate;
		return *this;
	}

        // copy constructor
       	Bond(const Bond& other) : Rate(other.Rate)
	{
		std::cout << "Copy constructing" << std::endl;
	}
};

class NamedBond : public Bond
{
private:
       string Name;
public:
       NamedBond(string name, double rate) : Bond(bond), Name(name)
       {
             std::cout << "Sub class constructing" << std::endl;
       }
}

When we run the following code:

Bond b(new NamedBond(1.2, "Name"));

we will see something like:

Constructing
Sub class construction
Copy constructing

What happens is, we build an object of type NamedBond and then copy it into a Bond object. But we don’t actually use the NamedBond object we constructed. It just exists as a temporary object without a name. We don’t actually have to copy it into the Bond object b. We can move it.

So, we are going to add two more special methods, the move constructor and the move assignment operator. This is how we define them:

        // move constructor
       	Bond(Bond&& other) : Rate(other.Rate)
	{
		std::cout << "Move constructing" << std::endl;
	}
 
        // move assignment
       	Bond& operator=(Bond&& other)
	{
		std::cout << "Move assigning" << std::endl;
		Rate = other.Rate;
		return *this;
	}

Now when we run:

Bond b(new NamedBond(1.2, "Name"));

we will see:

Constructing
Sub class constructing
Move constructing

So, the move constructor was used here. Why did the compiler decide to do that? Well, the compiler knows we are just using a temporary value to create b. Also the && modifier on the move constructor’s parameter, indicates it accepts a temporary value. This means that the move constructor will always get called when initialising with a temporary object. For example, suppose we have a function such as:

static NamedBond NamedBondFactory(double rate, string name)
{
      return new NamedBond(rate, name);
}

The following code:

Bond b(NamedBondFactory(1.2, "Name"));

will also go through the move constructor rather than the copy constructor. Similarly, if we have defined an addition operator on NamedBonds, then

NamedBond a(1.2, "Name1");
NamedBond b(2.4, "Name2");
NamedBond c(a + b);

will use the move constructor rather than the copy constructor.

We see the same thing with move assignment. However, just as with copy assignment, the compiler is much stricter and will not elide move assignments. So we can see the effect without using the NamedBond subclass.

So, suppose we run the following code:

Bond b(1.2);
b = Bond(2.3);

We will see:

Constructing
Construction
Move Assigning

We did not pass through the copy constructor. This is because the object created by Bond(2.3) is only a temporary object. Similarly, suppose we have a function which returns a Bond object, let’s call it BondFactory. The following code:

Bond b(1.2, "Name");
b = BondFactory();

Will print:

Constructing
Constructing
Move assigning

Why would we bother with these two extra methods? Why not just use the copy constructor and copy assignment? Well, the secret is in the signature. Firstly, we know that the move methods only take arguments that are temporary values. Secondly, the parameters to the move constructor and move assignment are not const. Taken together this means that, rather than copy data/resources the source object, we can just move data/resources out of it.

We can say that the move methods allow us to transfer ownership of resources from one object to another. For a class like Bond this distinction is a little pointless. But for more complex objects it can be crucial. For example, suppose we have an object that contained an array, our copy constructor and copy assignment would copy all the values in the array, whereas the move constructor and move assignment would just copy the pointer and set the pointer in the source to null. This pattern, a deep copy in the copy methods and a shallow copy in the move methods, is fairly typical. Also, when we move, we we always make sure to not leave any reference in the source object to whatever resources we are moving.

We can also invoke the move methods explicitly. We do this by using the std::move() function. So, as we know, the following code,

DerivedBond b(1.2, "Name");
Bond c(b);

will use the copy constructor to initialise c. However, if we use std::move like so:

DerivedBond b(1.2, "Name");
Bond(std::move(b));

the move constructor will be used. This is especially useful when we want to transfer ownership of a resource that is held by an object that is not temporary. We can also use std::move to invoke the move assignment operator. Whereas

Bond a(1.3);
DerivedBond b(1.2, "Name");
a = b;

will invoke the copy assignment method, this code:

Bond a(1.3);
DerivedBond b(1.2, "Name");
a = std::move(b);

will invoke move assignment.

The examples we have covered are a little bit complicated. Usually, when they are explained the effect of copy elision is ignored, which I think it quite confusing. If you try to run some examples you see on the internet they will not work at all the way they should, because the moves/copies are elided by the constructor. Our next post will bring everything we have covered together in a single example.

Not Copying in C++

So, in our last post we had a look at copy construction and copy assignment. Let’s use the code from that post and look at a quick example. Suppose we have simple function that returns a Bond. Something like:

static Bond BondFactory(double rate)
{
        return Bond(rate);
}

Of course this example is very silly, but let’s just go with it. So, suppose we run the following code in a Main method:

Bond b(BondFactory(1.2));

What do we see? Well, the output should look like this:

Constructing

This seems kind of strange. We constructed a Bond object inside the method BondFactory, and we see in the output that we visited the Bond constructor. However, we also copied the return value of BondFactory into a new Bond object b. So why did execution not pass through the copy constructor?

The answer is copy elision. The constructor sees that we are directly copying the result of the BondFactory method into another Bond object. So, rather than constructing and copying, it just constructs the Bond object once, creating the object b directly. What’s surprising here is that our copy constructor has a side effect, it prints to the console, yet the compiler stills skips it.

Now, suppose we defined a subclass of Bond:

class NamedBond : public Bond
{
private:
       string Name;
public:
       NamedBond(string name, double rate) : Bond(bond), Name(name)
       {
             std::cout << "Sub class constructing" << std::endl;
       }
}

And we had a factory method like:

static Bond BondFactory(double rate)
{
      return new NamedBond(rate, "none");
}

Now, if we run the following code in our main method,

Bond b(BondFactory(1.2));

We will see:

Constructing
Sub class constructing
Copy constructing

This time we do pass through the copy constructor. That is because copy elision only happens when the return type is the same as the value it is being copied into. In this case, the return type is a subclass of the value it is being coped into. So the compiler will not elide the copy step.

We will see the same effect when we copy from temporary objects that never get assigned a name. If we run the following code:

Bond b(Bond(1.2));

Our output will be:

Constructing

Whereas, if we run:

Bond b(NamedBond(1.2, "Name"));

we will get:

Constructing
Sub class constructing
Copy constructing

Similarly if we define an addition operator on Bond objects. If we run the following code:

Bond a(1.6);
Bond b(2.3);
Bond c(a + b);

The output will be:

Constructing
Constructing
Constructing

However, if we use the subtype, as so:

NamedBond a(1.6, "Name1");
NamedBond b(2.3, "Name2");
Bond c(a + b);

We will see the copy construction taking place.

Constructing
sub class Constructing
Constructing
sub class Constructing
Constructing
sub class Constructing
Copy constructing

With copy assignment the constructor is a lot stricter. With our example code, the following:

Bond b(1.2);
Bond c(2.3);
b = c;

will result in:

Constructing
Constructing
Copy assigning

So, the copy assignment method gets called here. This is because the compiler only elides the copy assignment when doing so has no consequence. In our case, if it was elided, we would miss the cout statement so it does not. It makes sense to be stricter with elision for the assignment operator, as we may have logic in that method that frees up resources that have already been initialised, this would not be the case with the copy constructor.

The C++ standard allows copy elision to take place, it does not mandate it. This means that elision behaviour depends entirely on what C++ compiler you use, what version of the language you are using and what compiler settings you have enabled. What I have described above is what you should normally expect to see.

Copy elision can also happen when throwing exceptions. However I will not get into the details here, as it is really not as interesting. If your exceptions are defined in such away that copy elision is important, you are defining them wrong.

Copying in C++

We are going to talk about two special C++ methods, the copy constructor and the copy assignment operator. You will often hear about these in the context of the rule of three or the rule of five. We’re not going to cover either of these rules. Instead we’re going to focus on these two methods themselves. What are the copy constructor and assignment operator for? Why are there two different methods that seem to do the same thing? When do they get used?

The copy constructor is defined just like a normal constructor, except it takes a single argument, a constant reference to an object of that class. The copy assignment operator is defined as an overload of the = operator. Let’s define a trivial class called Bond, that has a single field, a constructor, a copy constructor and a copy assignment operator.

#include <iostream>

class Bond
{
private:
	double Rate;
public:
	Bond(double rate) : Rate(rate)
	{
                std::cout << "Constructing" << std::endl;
	}

        // copy assignment
       	Bond& operator=(const Bond& other)
	{
		std::cout << "Copy assigning" << std::endl;
		Rate = other.Rate;
		return *this;
	}

        // copy constructor
       	Bond(const Bond& other) : Rate(other.Rate)
	{
		std::cout << "Copy constructing" << std::endl;
	}
};

Suppose we run the following code:

Bond A(1.6);
Bond B(A);

You will see, “Constructing” printed to the terminal, followed by “Copy constructing”. Nothing surprising here, when we create Bond A, we use the normal constructor. However, when we create Bond B, we use the copy constructor.

Similarly, if we run the following code from a main method:

Bond A(1.6);
Bond B(1.2);
B = A;

This time we will see our “Constructing” message appear twice followed by “Copy Assigning”. That is exactly what you would expect, as we are clearly using the assignment operator to copy from the Bond A to the Bond B. Now you might think that the copy assignment method is used every time we use the = operator to copy Bond objects. However it is not! Let’s say we ran the following code from a main method:

Bond A(1.6);
Bond B = A;

You won’t see the “Copy Assigning” output, you will see the “Copy constructing” message instead! That’s because we are not copy assigning here. Copy assignment happens whenever we use the = operator to assign to a Bond object that has already been initialised. Whereas, the copy constructor is called when we copy a Bond object into a new Bond that has not been initialised yet.

In our second example, the Bond B was already initialised with the normal constructor, before we assigned to it with =, so the copy assignment method was called. however, in our third example, the Bond B did not exist yet when we used the = operator, so the copy constructor was called. This difference is easy to remember, because constructors always initialise new objects!

When you see an example like this, you might ask yourself a couple of questions. Why are we splitting hairs over these two different cases? Why do we even need two different methods, couldn’t C++ just use a single copy method here?

Well, with these kind of trivial examples, it is a little pointless to have a separate copy constructor and copy assignment operator. So let’s imagine a slightly more complex example. Suppose we have a class, Holder that has a pointer to some object on the heap. Now when copy construct we know that our Holder object is uninitialised, so we can just copy the from source to the target. Whether we do a deep or shallow copy is irrelevant here. When we do a copy assignment, the target object will have a pointer to an object on the heap. So, before we can copy from the source object, we must free this memory with a delete. Otherwise we would end up with a serious memory leak.

To consider an even more complicated example. imagine a client class that talks to a server. When we copy a client object, we may want different behaviour depending on whether the target object has already started talking to a server or not.

So, in more complicated examples, the difference between copy assignment and copy construction can be quite important. The thing that you need to remember is that copy assignment happens when the target is already initialised, copy construction when it has not been initialised yet.

The Tricky Little Differences Between C# and C++ – part 1

There are a lot of big differences between C++ and C#. Really, despite their similar syntax, they are completely different languages. C# has garbage collection, C++ has manual memory management. C# is compiled to a special intermediate language that is then just in time compiled by the run time. C++ is compiled to machine code.

But, when you transfer between the two languages you are probably not going to get caught out by obvious things like that. It’s much more likely that the small subtle differences will trip you up. I’m going to cover some of these little differences that I’ve come across.

In this post we’ll be looking at uninitialised strings. Suppose we create a string in C++ without instantiating it directly ourselves and then print its contents. Like this:

string s;
cout << s << endl; 

This will just print an empty line, because the string s is empty. However, if you try the same thing in C#, it won’t work quite the same. If we use C# and do something like:

string s;
Console.WriteLine(s);

we’ll get the following runtime error:

Program.cs(10,31): error CS0165: Use of unassigned local variable 's'

This is a little surprising, normally C# is the more user friendly language. But in this case in C++ we get a friendly default behaviour whereas in C# we get a nasty runtime exception. Why?

This is because, in our C++ example we created a string object on the stack and dealt with it directly. When we created it, C++ called the default constructor which creates an empty string. However, in C# strings are reference types. This means that whenever we create one we are creating an object on the (managed) head. So our C# is really equivalent to the following C++ code:

String* s = NULL;
count << *s << endl;

If you run this you’ll end up with a seg fault, that’s because a null pointer points to memory address 0 which is inaccessible to you.