Largest / Smallest. Part 1

Sometimes, when multiple types are sent as template parameters, some information about the types needs to be interrogated to be able to configure another property of the template. The STL’s type traits header does a good job of supplying many of the more useful ones, but there is room for extension. Say, for instance, the template implements a type of variant container; a type of smart union. The container may store one of several types declared in the template parameter list. We need to allocate storage for this, but how determine the size?

template typename T1, typename T2, typename T3>
struct Buffer
{
	char buffer[???]; // Wouldn't it be nice to have something simple here,
	                  // rather than manually typing a lot of nested sizeof() boilerplate?
};

We can use template meta programming to help us here.

Here I will show you two variations; one for pre C++11 compilers that don’t support variadic templates and one for those that do.

Let’s say that we want to be able to handle up to four types. The ‘= void’ allows one, two, three or four types to be specified.

template <typename T1, typename T2 = void, typename T3 = void, typename T4 = void>
strut Largest
{
};

First, let’s create a helper template to determine the largest of two types.

// Declaration.
template <const bool Boolean, typename TrueType, typename FalseType>
struct ChooseType;

// Specialisation for 'true'.
// Defines 'type' as 'TrueType'.
template <typename TrueType, typename FalseType>
struct ChooseType<true, TrueType, FalseType>
{
  typedef TrueType type;
};

// Specialisation for 'false'. 
// Defines 'type' as 'FalseType'.
template <typename TrueType, typename FalseType>
struct ChooseType<false, TrueType, FalseType>
{
  typedef FalseType type;
};

These templates will define their ‘type’ to either that of TrueType or FalseType dependent on the condition supplied.

Next we create a recursive typedef that chooses the largest type between the first template parameter type and all of the rest. We typedef ‘all of the rest’ for clarity.

// Define 'LargestOther' as 'Largest' with all but the first parameter. 
typedef typename Largest<T2, T3, T4>::type LargestOther;

Now the recursive bit.

typedef typename ChooseType<(sizeof(T1) > sizeof(LargestOther)), // Boolean
                             T1,                                 // TrueType
                             LargestOther>                       // FalseType
                             ::type type;                        // The largest type of the two.

The compiler will recursively parse the template until there is one type to test. Here we need something to stop the compiler attempting to parse any further.
What we do is to add a specialisation for the final single type.

//***************************************************************************
// Specialisation for one template parameter.
//***************************************************************************
template <typename T1>
struct Largest<T1,   void, void, void>
{
  typedef T1 type;

  enum
  {
    size = sizeof(type)
  };
};

Putting this all together we get…

template <typename T1, typename T2 = void, typename T3 = void, typename T4 = void>
  struct Largest
{
private:

  // Declaration.
  template <const bool Boolean, typename TrueType, typename FalseType>
  struct ChooseType;

  // Specialisation for 'true'.
  // Defines 'type' as 'TrueType'.
  template <typename TrueType, typename FalseType>
  struct ChooseType<true, TrueType, FalseType>
  {
    typedef TrueType type;
  };

  // Specialisation for 'false'. 
  // Defines 'type' as 'FalseType'.
  template <typename TrueType, typename FalseType>
  struct ChooseType<false, TrueType, FalseType>
  {
    typedef FalseType type;
  };

public:

  // Define 'LargestOther' as 'Largest' with all but the first parameter. 
  typedef typename Largest<T2, T3, T4>::type LargestOther;

  // Set 'type' to be the largest of the first parameter and any of the others.
  // This is recursive.
  typedef typename ChooseType<(sizeof(T1) > sizeof(LargestOther)), // Boolean
                               T1,                                 // TrueType
                               LargestOther>                       // FalseType
                               ::type type;                        // The largest type of the two.
};

//***************************************************************************
// Specialisation for one template parameter.
//***************************************************************************
template <typename T1>
struct Largest<T1, void, void, void>
{
  typedef T1 type;
};

How It’s Used

template typename T1, typename T2, typename T3>
struct Buffer
{
	char buffer[sizeof(typename Largest<T1, T2, T3>::type)];
};

The number of types that can be handled is easily increased.

This is the technique used in the Embedded Template Library to implement largest/smallest traits.

In the next post I’ll show you how to achieve the same with variadic templates.

John Wellbelove

John Wellbelove

Director of Aster Consulting Ltd
United Kingdom
I have been involved in technology and computer systems for all of my working life and have amassed considerable knowledge of designing and implementing systems that are both performant and correct. My role normally encompasses the entire project life-cycle, from specification to maintenance phase. Most systems I have worked on have required high speed and deterministic performance, often within a highly constrained platform. I am experienced in designing and adapting algorithms to solutions that are both space and time efficient, avoiding the normal overheads of standard solutions. Acting as a mentor for colleagues has often been a significant, though unofficial, part of my role.

I administer an open source project on Github.
See http://www.etlcpp.com/

Leave a Reply

Your email address will not be published. Required fields are marked *