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.