Template deduction in C++ is like generic type parameter deduction in C#: it allows us to omit template arguments. Template specialization has no C# equivalent, but enables special-casing of templates based on certain arguments. Today we’ll look at how these features can make our code a lot less noisy and also a lot more efficient.

Table of Contents

Template Argument Deduction

The compiler has to know all the arguments to instantiate a template, but that doesn’t mean we have to explicitly state them all. Just like how we can use auto variables, parameters, and return values and the compiler will deduce their types, the compiler can also deduce template arguments.

The same is true to some extent with C# generics. Consider this example:

// C#
static class TypeUtils
{
    // Generic method
    public static void PrintType<T>(T x)
    {
        DebugLog(typeof(T));
    }
}
 
// Type arguments explicitly specified
TypeUtils.PrintType<int>(123); // System.Int32
TypeUtils.PrintType<bool>(true); // System.Boolean
 
// Type arguments deduced by the compiler
TypeUtils.PrintType(123); // System.Int32
TypeUtils.PrintType(true); // System.Boolean

The same works in C++, as we see in this literal translation of the C#:

struct TypeUtils final
{
    // Member function template
    template<typename T>
    static void PrintType(T x)
    {
        DebugLog(typeid(T).name());
    }
};
 
// Type arguments explicitly specified
TypeUtils::PrintType<int>(123); // i
TypeUtils::PrintType<bool>(true); // b
 
// Type arguments deduced by the compiler
TypeUtils::PrintType(123); // i
TypeUtils::PrintType(true); // b

Support for deduction in C++ is considerably more advanced than in C#. For example, non-type template parameters can be deduced:

// Template has one type parameter (T) and one non-type parameter (N)
template<class T, int N>
// Function takes a reference to an array of length N const T elements
int GetLengthOfArray(const T (&t)[N])
{
    return N;
}
 
// Compiler deduces T as int and N as 3
DebugLog(GetLengthOfArray({1, 2, 3})); // 3
 
// Compiler deduces T as float and N as 2
DebugLog(GetLengthOfArray({2.2f, 3.14f})); // 2

Template template parameters can be deduced, too:

// Template with two parameters:
// 1) T, a type parameter
// 2) TContainer, a template parameter
template<typename T, template<typename> typename TContainer>
void PrintLength(const TContainer<T>& container)
{
    DebugLog(container.Length);
}
 
template<typename T>
struct List
{
    int Length;
};
 
List<int> list{};
PrintLength(list); // T deduced as int, TContainer deduced as List

The compiler will also consider all the overloaded functions in an attempt to find the one that matches best:

// Template takes one type parameter
template<class T>
// Function takes a pointer to a function that takes a T and returns a T
int CallWithDefaultAndReturn(T(*func)(T))
{
    return func({});
}
 
int AddOne(int x)
{
    DebugLog("int");
    return x + 1;
}
 
int AddOne(char x)
{
    DebugLog("char");
    return x + 1;
}
 
// CallWithDefaultAndReturn is an overload set
// Compiler looks at this function and deduces that T is int:
//   int AddOne(int)
// Compiler looks at this function and fails to deduce T:
//   int AddOne(char)
// Since deduction succeeded for one of them, that one gets passed
DebugLog(CallWithDefaultAndReturn(AddOne)); // "int" then 1

Note that deduction involves a few transformations of types. First, arrays “decay” to pointers:

template<class T>
void ArrayOrPointer(T)
{
    DebugLog("is array?", typeid(T) == typeid(int[3]));
    DebugLog("is pointer?", typeid(T) == typeid(int*));
}
 
int arr[3];
ArrayOrPointer(arr); // is array? false, is pointer? true

Second, functions “decay” to function pointers:

void SomeFunction(int) {}
 
template<class T>
void FunctionOrPointer(T)
{
    DebugLog("is function?", typeid(T) == typeid(decltype(SomeFunction)));
    DebugLog("is pointer?", typeid(T) == typeid(void(*)(int)));
}
 
FunctionOrPointer(SomeFunction); // is function? false, is pointer? true

And third, const is removed:

template<class T>
void ConstOrNonConst(T x)
{
    // If T was 'const int' then this would be a compiler error
    x = {};
}
 
const int c = 123;
ConstOrNonConst(c); // Compiles, meaning T is non-const int

Fourth, references to T become just T:

template<class T>
void RefDetector(T x)
{
    // If T is a reference, this assigns to the caller's value
    // If T is not a reference, this assigns to the local copy
    x = 123;
}
 
int i = 42;
int& ri = i;
RefDetector(ri);
DebugLog(i); // 42

To keep the reference, we have to say that we want a reference by adding the &:

template<class T>
void RefDetector(T& x) // <-- Added &
{
    x = 123;
}
 
int i = 42;
int& ri = i;
RefDetector(ri);
DebugLog(i); // 123

One exception is when passing an lvalue to a function template that takes a non-const rvalue reference. In this case, the compiler will deduce the type as an rvalue reference:

template<class T>
void Foo(T&&)
{
}
 
int i = 123; // lvalue, not lvalue reference
Foo(i); // T is int&&
Foo(123); // T is int&

After these transformations, the compiler looks for an exact match but it’ll also accept a few discrepancies. First, non-const will match const but not the other way around:

template<typename T>
void TakeConstRef(const T& x)
{
}
 
template<typename T>
void TakeNonConstRef(T& x)
{
    x = 42;
}
 
// Compiler deduces T='const int&' even though 'i1' is non-const
int i1 = 123;
TakeConstRef(i1);
 
// Compiler deduces T='const int&'
const int i2 = 123;
TakeNonConstRef(i2); // Compiler error: can't assign to x

Second, the same is true for pointers:

template<typename T>
void TakeConstRef(const T* p)
{
}
 
template<typename T>
void TakeNonConstRef(T* p)
{
    *p = 42;
}
 
// Compiler deduces T='const int*' even though 'i1' is non-const
int i1 = 123;
TakeConstRef(&i1);
 
// Compiler deduces T='const int*'
const int i2 = 123;
TakeNonConstRef(&i2); // Compiler error: can't assign to *p

And third, derivation is allowed to support polymorphism:

template<class T>
struct Base
{
};
 
template<class T>
struct Derived : public Base<T>
{
};
 
template<class T>
void TakeBaseRef(Base<T>&)
{
}
 
Derived<int> derived;
 
// Compiler accepts Derived<T> for Base<T> an deduces that T is 'int'
TakeBaseRef(derived);
Class Template Argument Deduction

Since C++17, the arguments to a class template can also be deduced:

// Class template
template<class T>
struct Vector2
{
    T X;
    T Y;
 
    Vector2(T x, T y)
        : X{x}, Y{y}
    {
    }
};
 
// Explicit class template argument: float
Vector2<float> v1{2.0f, 4.0f};
 
// Compiler deduces the class template argument: float
Vector2 v2{2.0f, 4.0f};
 
// Also works with 'new'
// 'v3' is a Vector<float>*
auto v3 = new Vector2{2.0f, 4.0f};

To help the compiler deduce these arguments, we can write a “deduction guide” to tell it what to do:

// Class template
template<class T>
struct Range
{
    // Constructor template
    template<class Pointer>
    Range(Pointer beg, Pointer end)
    {
    }
};
 
double arr[] = { 123, 456 };
 
// Compiler error: can't deduce T (class template argument) from constructor
Range range1{&arr[0], &arr[1]};
 
// Deduction guide tells the compiler how to deduce the class template argument
template<class T>
Range(T* b, T* e) -> Range<T>;
 
// OK: compiler uses deduction guide to deduce that T is 'double'
Range range2{&arr[0], &arr[1]};

As we see in this example, deduction guides are written like a function template with the “trailing return syntax.” The major difference is that their name is the name of a class template and their “return type” is a class template with its arguments passed.

Specialization

So far, all of our templates have been instantiated the same way regardless of the template arguments provided to them. Sometimes we want to use an alternate version of the template when certain arguments are provided. This is called specialization of a template. Consider this class template:

// A very generalized vector
template<typename T, int N>
struct Vector
{
    T Components[N];
 
    T Dot(const Vector<T, N>& other) const noexcept
    {
        T result{};
        for (int i = 0; i < N; ++i)
        {
            result += Components[i] * other.Components[i];
        }
        return result;
    }
};
 
// Usage
Vector<float, 2> v1{2, 4};
DebugLog(v1.Components[0], v1.Components[1]); // 2, 4
 
Vector<float, 2> v2{6, 8};
DebugLog(v1.Dot(v2)); // 44

Now let’s specialize Vector for a common use case: two float components.

// Specialization of the Vector template
template<> // Takes no arguments
struct Vector<float, 2> // Arguments are provided by the specialization instead
{
    // Specialization can have very different contents
    // This union allows access either by the Components array or X and Y
    union
    {
        float Components[2];
        struct
        {
            float X;
            float Y;
        };
    };
 
    float Dot(const Vector<float, 2>& other) const noexcept
    {
        // Specialized version doesn't need a loop
        // Easier for readers to understand
        // Compiler can't fail to optimize out the loop
        return X*other.X + Y*other.Y;
    }
};
 
// We can use X and Y or the Components array to access the components
Vector<float, 2> v1{2, 4};
DebugLog(v1.Components[0], v1.Components[1]); // 2, 4
DebugLog(v1.X, v1.Y); // 2, 4
 
// Dot still works
Vector<float, 2> v2{6, 8};
DebugLog(v1.Dot(v2)); // 44

There are several reasons we might want to specialize the Vector template for common types and sizes of vectors. Perhaps we’ve inspected the assembly and realized that the compiler didn’t optimize out the loop in Dot. Perhaps we want to add the convenience of X and Y data members as synonyms for the first two elements of the Components array. Perhaps we want to use SIMD instructions that only work on particular numbers of particular data types. We’ll see how to do that later in the series.

Regardless of our reasons, there are a couple aspects of the above example to take note of. First, we’re able to specialize not just type parameters like T but also non-type parameters like N.

Second, our specialization is also named Vector. It doesn’t get a unique name like Vector2. Usually, specializations are meant to be transparent to the user of the template. The template author often provides them to optimize some use case or to provide a superset of functionality in some particular case. The Vector<float, 2> specialization could have omitted the Components array, but then a Vector<float, 2> wouldn’t be compatible with other instantiations of Vector:

template<>
struct Vector<float, 2>
{
    // No Components
    float X;
    float Y;
 
    float Dot(const Vector<float, 2>& other) const noexcept
    {
        return X*other.X + Y*other.Y;
    }
};
 
Vector<float, 2> v1{2, 4};
 
// Compiler error: Vector<float, 2> doesn't have a Components data member
DebugLog(v1.Components[0], v1.Components[1]); // 2, 4
 
// OK: Vector<float, 2> has X and Y
DebugLog(v1.X, v1.Y); // 2, 4

That said, sometimes incompatibility is desirable. Take the cross product, for example. We may want to omit this from specializations of 2D vectors as the operation doesn’t make a lot of sense. Then again, we might want to return a 3D vector such as (0, 0, 1) or (0, 0, -1). Template specializations give us the flexibility to make this design choice.

Finally, we also have the option to “partially specialize” a template. We use a “partial specialization” when we only want to specialize some of the template arguments, not all of them like above. For example, we might want to specialize for 2D vectors but not for float:

// Partial specialization of the Vector template
// Now takes only one parameter: the type T
template<typename T>
// Pass arguments to the main Vector template
// They can be either parameters to the specialization or regular arguments
struct Vector<T, 2>
{
    union
    {
        // We can still use T, but we also know that N is 2
        T Components[2];
        struct
        {
            T X;
            T Y;
        };
    };
 
    T Dot(const Vector<T, 2>& other) const noexcept
    {
        // The loop is removed, but we still support any arithmetic type
        return X*other.X + Y*other.Y;
    }
};
 
// X and Y are available
Vector<float, 2> v1{2, 4};
DebugLog(v1.X, v1.Y); // 2, 4
 
// Multiple types (float and double) are usable now
Vector<double, 2> v2{6, 8};
DebugLog(v2.X, v2.Y); // 6, 8
Conclusion

Both C# and C++ support argument deduction in their generics and templates. As usual, C++ goes way further and with more complexity. It can deduce non-type parameters and template parameters as well as class arguments leading to much more terse code: Dictionary, not Dictionary<MyKeyType, MyValueType>. Deduction guides give us a tool to really push what’s deductible rather than settling for defaults.