Sunday 12 January 2014

Comparison of tuples using variadic templates

In a previous post I explained how the tuple has been implemented in VC++ 2013 using variadic templates. That post gave some explanation of the definition and construction of tuples. You'll should understand that post before you read this one.

The comparison of tuples is interesting and it also uses variadic templates. The STL provides comparison operators for tuples even though they can be composed of many different types, which aren't known, and often don't exist, until the client code is written. This post shows how this is achieved.

Comparison of tuples

The include file <tuple> contains the (non-member) helper operator:

template<class... _TypesLhs, class... _TypesRhs> inline
bool operator==(const tuple<_TypesLhs...>& _Left, const tuple<_TypesRhs...>& _Right)
{
  return (_Left._Equals(_Right));
}

Here _TypesLhs is the types of the tuple on the left hand side and _TypesRhs the types of the tuple on the right. Note that this is not the type of the tuple itself, but the collection of types of all the elements of the tuple. This function simply calls through to the tuple member function _Equals which looks like this:

template<class... TypesRhs>
bool _Equals(const tuple<TypesRhs...>& _Right) const
{
  return (_Myfirst._Val == _Right._Myfirst._Val
  && _Mybase::_Equals(_Right._Get_rest()));
}

Remember that a tuple is composed of a base part that holds a single element of a templated type, and a derived part that holds the remaining elements and the collection of associated types. This pattern continues recursively down to a base class that doesn't hold any value and is based on a template definition with zero types.

The _Equals function above compares the two elements in the most derived class. If they don't match then it will return false. If they do match is will call recursively into the _Equals function in the base class. If these calls make it all the way to the base tuple, which is templated for zero arguments, then it always returns true and the tuples match. This is another example of how powerful variadic templates can be.

You should understand that if the corresponding elements of two tuples can't be compared with the == operator then compiler will complain if you try to compare those tuples. This reminds us how much of the work here is being done at compile time. Template classes and template functions are not classes and functions. They're templates that the compiler uses to write classes and functions during compilation, and this is just the same when variadic templates are being used.

Comparing tuples with different numbers of elements

Comparing tuples of different sizes obviously shouldn't return true, but this is in fact also dealt with at compile time. You'll need to understand a few more things to see how this is done, but they're interesting so I'm adding them into this post.

Firstly, I previously omitted from the _Equals function the following line:

static_assert(_Mysize == sizeof...(_Other), "comparing tuple to object with different size");

The first parameter to a static_assert must be a constant expression that can be converted to a bool. A constant expression is an expression that can be evaluated by the compiler. As I'll show, _Mysize is a const and sizeof can be figured out by the compiler, so _Mysize == sizeof...(_Other) is a constant expression. If the compiler evaluates this expression to true then the static_assert declaration has no effect. If it evaluates to false the compiler gives an error with the message supplied in the second argument to static_assert.

So, how does the compiler determine the size of each tuple? The tuple member variable _Mysize is defined as follows:

static const size_t _Mysize = 1 + sizeof...(_Rest);

Here, _Rest is the collection of types of the tuple from which this class is derived, i.e. all the types not held by this class. To understand how this calculation works consider sizeof(tuple<double, long, std::string>). Here:

sizeof(tuple<double, long, std::string>) = 1 + sizeof(tuple<long, std::string);
sizeof(tuple<long, std::string>) = 1 + sizeof(std::string);
sizeof(tuple<std::string>) = 1 + sizeof(tuple<>);
sizeof(tuple<>) = 0;

This should explain how comparing tuples with differing numbers of elements can give a compilation error.

Sunday 5 January 2014

More on STL Tuples - Implementation using Variadic Templates

My previous post on STL tuples mentioned that they can be implemented using variadic templates. This post looks at the VC++ 2013 tuple implementation to see how this has been achieved. Doing so gives a great example of how powerful variadic templates can be.

(Note, in order to keep the code below clean I've cut out some details, e.g. template parameters with defaults that are used. These extras have no affect on what I'm explaining and clutter up the code snippets. If you want to see these details go look in <tuple>.)

Simple class definition for a tuple in VC++ 2013

Firstly, there is the following class definition for tuple:

template<>
class tuple<>
{
public:
  tuple()
  {
  }
  // more implementation

This is a template class with no template parameters, and a constructor that takes no parameters. You could invoke this constructor with:

tuple<> temp;

but I can't think of a reason to ever do that.

Variadic template class definition for the tuple

There is then another tuple definition that uses variadic templates:

template<class T, class... _Rest>
class tuple<T, _Rest...> : private tuple<_Rest...>
{ // recursive tuple definition
public:
  _Tuple_val<T> _Myfirst;
  tuple<_Rest...> _Get_rest();

To understand this you'll need to know that the ... notation can be read as "collection of". Also, if you're not familiar with the class keyword inside the template angle brackets, it's equivalent to typename in this context.

Now you can begin to parse the above code. This definition of tuple is templated for a parameter of type T and a collection of types referred to as _Rest. It privately inherits from a tuple that is templated for this collection of types. The comment "recursive tuple definition" is not mine, it's taken from the VC++ 2013 STL code. It explains that when using the above definition the compiler will recursively create new tuple definitions for a shrinking list of types until that list is empty, at which point it will use the original tuple definition, which is templated for zero types.

To explain with an example, consider you wish to use tuple<double, long, std::string>. The compiler will first create a class definition of tuple that is templated for type double and the collection of types long and std::string. This class will inherit from another class definition of tuple that is templated for type long  and the collection of types std::string. This class will inherit from a tuple class that is templated for type std::string and inherits from the original tuple class definition that is templated for zero types.

Construction and Implementation details

Look at the two members that I've picked out. _Tuple_val<T> is a helper class and it's used to store a value of type T_Get_rest() is a member function that returns a reference to the base class. So, from the previous example, in the most derived class, which is templated for type double and the collection of types long and std::string_Myfirst refers to the value of the double and _Get_rest() returns a reference to its base class i.e. the class that is templated for a long  and the collection of types std::string.

Now look at the constructor that is used when many types are passed in:

explicit tuple(T&& _This_arg, _Rest&&... _Rest_arg)
_Myfirst(_This_arg), tuple<_Rest...>(_Rest_arg...)
{
}

As you can see, the constructor simply initializes the _Myfirst variable with the corresponding value _This_arg, and the rest of the arguments are passed to the base class, which is by definition a tuple templated for the types of those arguments.

Hopefully this example gives a good idea of the power of variadic templates. I'll follow up with another post on some more VC++ 2013 tuple implementation details including how they are compared.