Hello internet! I'd like to inaugurate my blog with a topic that's very dear to me: metaprogramming! In particular, I want to guide you through an introduction to this fascinating discipline in a way that's easy to follow and that gives you the building blocks to write your own tools. Being completely honest, this is an advanced programming topic, but the tools we're going to use are mostly learnt during one's first year of programming.

We're going to be writing C++20, so expect lots of shiny templates! Grab a seat and a compiler and let us answer the fundamental question of this post:

What's the narrowest integer that can hold a particular value?

If you're writing size-bounded data container such as a vector or a stack with a maximum capacity and want to optimise for size, then this exercise can become a useful tool to incorporate in your project. Let's start by understanding the scope of the problem.

Definitions

First of all, we're going to define what we mean by narrowest integer. Integer types are those we use to represent integer numbers, such as char, int or long. With narrow we mean that we're going to be inspecting the width of those types, i.e. their size in bytes accessible through sizeof(<type>). For example, sizeof(int) should be 4 in your machine. I say should because your particular computer architecture may use a different number of bytes to represent an int. That's ok and you shouldn't worry about it, as our implementation is going to be architecture independent.

Also, the type of the solution will be a type. We want a piece of code that will return not the name, but the actual type we're looking for so we can use it to declare other variables. That's the fun of metaprogramming! We're going to put the compiler to work and make our program flexible to the programmer's input!

Metaprogramming techniques with templates

The basics

The tool we use in C++ to write generic code is the template. You can think of templates as blueprints for pieces of code that share a common structure for data and behaviour. Using these blueprints, we can instantiate actual code structures that will be part of our final program. For a simple but complete example, let's take a look at the definition of std::array:

template <typename T, size_t N>
struct array {
    T data[N];
    // Other goodies...
};

The template declaration indicates that we're going to be defining a class template that takes two template parameters:

typename T: A symbol that corresponds to the name of a type.
size_t N: A value known at compile time of type size_t.

When we declare an object of type std::array<int, 10>, the compiler will substitute all instances of T and N with int and 10 respectively. In this example, the inner body of the class would be substituted by int data[10], an array that holds ten ints just like we wanted. This technique is called template specialisation, meaning that we're specialising the generic type array<T,N> with T=int and N=10. In the case of std::array, the specialisation is full, but we can partially specialise templates by only specialising some of its parameters.

What we want to do now is to use this technique to work with the template parameters as data and manipulate them to make computations at compile time. To achieve this, we're going to add two new ingredients into the mix.

Type aliases and constant expressions

We're now entering the realm of functional programming. Here, there are no variables, just constants values that we can combine to define more constant values. Keep in mind that the values we're going to be working with here are both numeric values and types. That's right, we're going to be manipulating types just like we manipulate numbers. Let's start by declaring a structure template that can hold an alias for any type:

template <typename T>
struct type_holder {
    using type = T; // Equivalent to `typedef T type`
};

This structure contains a type alias called type that we can access through the :: operator. For example, if we declare the specialisation type_holder<char *>, then type_holder<char *>::type will be char *. But how can we assert that with code? After all, we'll want to test our results. To achieve this, we want to take a look at an implementation of integral constants, C++'s tool for representing constant values with templates:

template <typename T, T Value>
struct integral_constant {
    using value_type = T;
    static constexpr T value = Value;
//  ^~~~~~ ^~~~~~~~~
//  |      Must be known at compile time
//  |
//  Accessible from the type with operator ::

    // Other goodies...
};

Our tests need to assert truthfulness and falseness and the standard library defines two specialisations of integral_constant for that purpose:

using true_type  = integral_constant<bool, true>;
using false_type = integral_constant<bool, false>;

// Assert these expressions at compile time or throw a compilation error
static_assert(true_type::value);
static_assert(!false_type::value);

Wait, isn't this a bit overkill? After all, the values true and false are already part of the core language, right? Yes, you're right. However, using std::integral_constant will make our life easier by simplifying the code we have to write from now own. Let's see it in action by writing a structure that will assert the type held in type_holder.

Partial specialisation and inheritance

What we want now is a structure that can tell us if two types are equal. The standard library gives us a structure that does just that called std::is_same. Let's take a look at its implementation

template <typename T, typename U>
struct is_same : std::false_type { };

template <typename T>
struct is_same<T, T> : std::true_type { };
//                     ^~~~~~
//                     Partial specialisations require that we specify the
//                     parameters we're using after the structure's name.
//                     In this case, both parameters are of the same type.

Simple, right? Template instantiation rules specify that the most specialised template will be used if many specialisations are available. In this case, is_same<int, int> will use the specialisation inheriting from true_type because <T, T> is more specialised than <T, U>. On the other hand, is_same<int, bool> will use the one that inherits from false_type because <T, T> cannot be instantiated with two different types.

Now, here's the kicker: since both specialisations inherit from types that are full specialisations of std::integral_constant, they will also inherit their value_type and value members. This means that just by using inheritance we've made one expression's value equal to true and the other, to false.

With this tool, we can write a nice test:

static_assert(std::is_same<type_holder<char *>::type, char *>::value);

In fact, we can simplify this code a bit by using the suffixes _t and _v to directly access the type and value of the structures. First, let's look at how we can define these symbols for both type_holder and is_same:

template <typename T>
using type_holder_t = typename type_holder<T>::type;
//                    ^~~~~~~~
//                    Required as we don't know the type of `T` yet

template <typename T, typename U>
inline constexpr T is_same_v = std::is_same<T, U>::value;

But wait, why are we using _t and _v anyway if we could be concealing the implementation in a deeper namespace and just exposing the types and values in the std namespace? Well, directly accessing the type like this was an afterthought that started to be added to the standard in C++14 and since all C++ code must be backwards compatible, new symbols had to be added for this task. In the case of _v, the qualifier inline constexpr is required to globally expose the value and it wasn't added to the language until C++17, so all your code written in C++11 or 14 will still have to use ::value.

With these two shortcuts, we can simplify the previous test quite a bit:

static_assert(std::is_same_v<type_holder_t<char *>, char *>);

Nice! We now have a tool to check that our templates are choosing the correct type! Let's now start our work to find the proverbial narrowest integer. In order to find it, we will have to introduce the last tool we'll learn in this article.

Packs, recursivity, and finding the narrowest integer

Declaring the structures

In order to find the narrowest integer, we will have to provide a list of integer types to search through. We're going to define our list with four fixed-width integer types: int8_t, int16_t, int32_t, and int64_t. These type are required to be at least their announced number of bytes wide, so there's no need to call sizeof on them to find their size and we can order them from narrowest to widest just by looking at their names. Of course, you're free to expand the list with other types you like.

Let's declare the structures we're going to be working with:

namespace impl {
    template <size_t Value, typename... Integers>
    struct narrowest_integer_for;
}

template <size_t Value>
struct narrowest_integer_for :
        impl::narrowest_integer_for<Value, int8_t, int16_t, int32_t, int64_t>
{ };

There's a bit to unpack here (pun intended). First, we have the template parameter typename... Integers, which declares a template parameter pack. Parameter packs allow us to write variadic templates that receive an arbitrary number of arguments. In the previous code, impl::narrowest_integer_for will be instantiated with one numeric value and any number of types.

We also have a second narrowest_integer_for in the global namespace that takes the Value parameter. This structure inherits from impl::narrowest_integer_for, passing both the Value parameter and a pack of types. We're doing this to define our own list of integer types to search through and allow the user to just specify the value they want to use for the search.

Parameter pack destructuring

What we want to do now is iterate through our parameter pack and inspect every type to see if it can hold our value. We're going to tackle the first part of the problem first: iterating through the pack. To do this, we're going to destructure the pack and consume it recursively.

Wait, what does this all mean? Let's take a look at the code first and explore this technique with a concrete example:

namespace impl {
    // A preliminary declaration is required to declare specialisations
    template <size_t Value, typename... Integers>
    struct narrowest_integer_for;

    // Base case: The pack only contains one type
    template <size_t Value>
    struct narrowest_integer_for<Value> {
        using type = void;
    };

    // General case, we destructure the pack as (X:XS)
    template <size_t Value, typename X, typename... XS>
    struct  narrowest_integer_for<Value, X, XS...> :
            narrowest_integer_for<Value, XS...>
    { };
}

If you've worked we Haskell before you may be familiar with the (x:xs) idiom. If you haven't don't worry, we're going to explain how it works.

Let's focus first on the base case structure. The parameter typename... Integers is gone! This means that the base case will be reached when there are no elements left in the pack to consume. If we haven't found an integer type wide enough to represent Value, we want to return an error. Since we cannot use void as the type of an object, we assign it in the base case as an error-like type.

In the general case, we're destructuring Integers into X, which will call the head, and XS..., which will call the tail. This means that when we instantiate this template, the argument pack will be divided into two parts: a head containing the first element and a tail containing the rest. For example, this is how the first pack will be destructured:

template <size_t Value>
struct narrowest_integer_for :
        impl::narrowest_integer_for<Value, int8_t, int16_t, int32_t, int64_t>
//                                         ^~~~~~  ^~~~~~~~~~~~~~~~~~~~~~~~~
//                                         X       XS...
//                                         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//                                         Integers
{ };

As you can see, impl::narrowest_integer_for<Value, X, XS...> recursively inherits from impl::narrowest_integer_for<Value, XS...>, consuming the head of the pack. The next time we instantiate the pack, it will only contain the types int16_t, int32_t, and int64_t and so on. Without more operations, this structure will always yield the type void, as it unconditionally consumes the pack until it reaches the base case. Let's introduce our final structure, one that will let us check if the type X can be used to represent Value.

Conditional type assignment

Our algorithm to find the narrowest type is very simple:

For every type X in the pack:
- If Value is less or equal than the highest number X can hold:
  - Return X
If no suitable type was found in the pack:
- Return void

We've already taken care of the last condition by iterating through the parameter pack. For the first condition, we need a structure that will let us choose between two types depending on the result of a condition. The standard library defines std::conditional to let us do just that. We're going to be using this structure, but let's take a look at its implementation first:

template <bool Expr, typename TrueT, typename FalseT>
struct conditional;

template <typename TrueT, typename FalseT>
struct conditional<true, TrueT, FalseT> {
    using type = TrueT;
};

template <typename TrueT, typename FalseT>
struct conditional<false, TrueT, FalseT> {
    using type = FalseT;
};

template <bool Expr, typename TrueT, typename FalseT>
using conditional_t = typename conditional<Expr, TrueT, FalseT>::type;

If you've been following this article, then there should be no mysteries here. This structure lets us select the first (TrueT) or second (FalseT) type depending on the value of the boolean expression.

What we need for the condition is the highest number a particular type can hold. To get it, we're going to use the numeric limits library, which will let us access the maximum value of an integer type. For example:

static_assert(std::numeric_limits<int8_t>::max() == 127);
//            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//            This function is consteval-qualified, which means that its
//            value must and will always be known at compile time!

With this last piece of the puzzle, let's re-write the general case structure of narrowest_integer_for to include this check:

template <size_t Value, typename X, typename... XS>
struct narrowest_integer_for<Value, X, XS...> : std::conditional<
        (Value <= std::numeric_limits<X>::max()),
        X,
        typename narrowest_integer_for<Value, XS...>::type>
{ };

Every time we instantiate this structure, we check if Value is less or equal than the highest number X can hold. If it is, we assign X to type and the operation is over. Otherwise, we recurse into narrowest_integer_for<Value, XS...> and assign its type member to the type member of this structure instead.

As this is a recursive operation, the value of type in any level N will also be assigned to all levels [0..N-1]. Thus, no matter how deep we are into the search, the final value of type will be accessible from the top-level structure. This is exactly what we want, as we'll always access the type member from the definition of narrowest_integer_for that lives in the global namespace.

In conclusion

The problem is solved: we have created a structure capable of determining the narrowest integer that can hold a particular value at compile time.

In this article we have taken a look into how template metaprogramming works and how to perform some operations with templates. Using std::integral_constant and many other structures found in the type traits library you can make your programs behave more flexibly and take tons on decisions on compile time.

Here's the final code for the exercise we've been working on:

#include <cstddef>
#include <cstdint>
#include <limits>
#include <type_traits>

namespace impl {
    template <size_t Value, typename... Integers>
    struct narrowest_integer_for;

    template <size_t Value>
    struct narrowest_integer_for<Value> {
        using type = void;
    };

    template <size_t Value, typename X, typename... XS>
    struct narrowest_integer_for<Value, X, XS...> : std::conditional<
            (Value <= std::numeric_limits<X>::max()),
            X,
            typename narrowest_integer_for<Value, XS...>::type>
    { };
}

template <size_t Value>
struct narrowest_integer_for :
        impl::narrowest_integer_for<Value, int8_t, int16_t, int32_t, int64_t>
{ };

template <size_t Value>
using narrowest_integer_for_t = typename narrowest_integer_for<Value>::type;

static_assert(std::is_same_v<narrowest_integer_for_t<75>,           int8_t>);
static_assert(std::is_same_v<narrowest_integer_for_t<250>,          int16_t>);
static_assert(std::is_same_v<narrowest_integer_for_t<195518>,       int32_t>);
static_assert(std::is_same_v<narrowest_integer_for_t<237254386759>, int64_t>);

I hope that you enjoyed reading this first article of mine and that you learnt some techniques that you can use in your programs. If you'd like to discuss this article, feel free to send me an email at the address listed at the top.

Thank you for reading and have a great day!

Finding the narrowest integer