03 - deduction

When a template is being used (instantiated), the compiler needs to "figure out" what types (or values in case of NTTP) should replace template parameters. This mechanism is known as deduction.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <iostream>

template <typename T>
const T& min(const T& x, const T& y)
{
	if (y < x)
		return y;
	else
		return x;
}

int main()
{
	std::cout << ::min(2, 1)        << "\n"; // deduces T as int
	std::cout << ::min(1.618, 3.14) << "\n"; // deduces T as double
	std::cout << ::min('a', 'b')    << "\n"; // deduces T as char
}

The example above is very trivial; however template type deduction itself is a rather complex feature. I won't describe it in detail because there are simply too many cases and too many possible combinations with other language features. Instead, you will learn specific deduction rules along the way, similarly how const is laid out in the beginner tutorial - not a chapter of its own but an addition to every other feature (const objects, const parameters, const functions, const methods, ...). Deduction intertwines significantly with various elements of the type system and introducing them all in a single lesson would roughly be copy-pasting cppreference or the standard specification.

The examples use :: to avoid ambiguities with standard library functions. Because of ADL, calls to function templates can also search identical names in the standard library if the type of one of arguments also comes from the standard library namespace.

Deduction vs auto

auto is based on the same mechanism. In fact, auto is specified to use template type deduction, as if the deduced type was a function template parameter and the initializer was the argument.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

template <typename T>
void f1(T) {}

template <typename T>
void f2(T&) {}

int main()
{
	const int x = 1;

	auto  a1 = x; // auto =       int, a1 has type       int
	auto& a2 = x; // auto = const int, a2 has type const int&

	f1(x); // T =       int, parameter has type       int
	f2(x); // T = const int, parameter has type const int&
}

You can observe that both sets of cases are identical:

  • Template type deduction (and auto) strip top-level cv-qualifiers when used without qualifiers.

  • Existing qualifiers remain and participate in deduction.

  • The final type is built from both present and deduced type modifiers.

You can also observe that:

  • auto does deduction only for a single initializer value - not (potentially multiple) function parameters.

  • Templates can be required to deduce something like std::vector<T> (where the template parameter is only a part of the final type) while (as of writing this) you can not write something like std::vector<auto> v = /* expr */;.

In other words, deduction in templates covers significantly larger amount of (potentially more complex) situations.

std::initializer_list is a special case:

  • templates can not deduce it directly

  • auto can deduce it only when paired with copy-list-initialization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <initializer_list>

template <typename T>
void f1(std::initializer_list<T>) {}

template <typename T>
void f2(T) {}

int main()
{
	// copy-list-initialization
	auto a1 = {1, 2, 3}; // auto = std::initializer_list<int>

	// direct-list-initialization
	// auto a2{1, 2, 3}; // error: not allowed with muliple parameters and deduction
	auto a3{1};          // auto = int
	// TODO when was N3922 introduced? C++11? C++17?

	f1({1, 2, 3});    // T = int
	// f2({1, 2, 3}); // error: can not deduce from braced-init-list
}

Deduction vs multiple parameters

Each function parameter is deduced separately. If there is a conflict between deductions or the deduction can not be performed, the instantiation will fail.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <vector>

template <typename T, typename U>
void f(T, T, U) {}

template <typename T>
void g1(std::vector<T>) {}

template <typename T>
void g2(std::vector<T>, T) {}

int main()
{
	f(1, 2, 3);   // ok: T deduced as int, U deduced as int
	f(1, 2, 3.0); // ok: T deduces as int, U deduced as double

	// error: conflicting deductions
	// argument 1 deduced T as int,
	// argument 2 deduced T as double
	// argument 3 deduced U as int
	// f(1, 2.0, 3);

	// error: can not deduce T (not std::initializer_list)
	// g1({1, 2, 3});

	// argument 1 can not deduce T
	// argument 2 deduces T as int
	g2({1, 2, 3}, 4); // ok
}

As you can see, deduction can fail for some arguments. What is important is that:

  • there are no conflicts between deductions

  • every template parameter has at least 1 successful deduction

Explicit specification

There are no requirements between function arguments and template parameters. This means that:

  • types of function template arguments do not have to be in the same order as template parameters

  • not every parameter must be declared using a unique template parameter

  • not all template parameters have to be used within the list of arguments

This in turn means that many function templates can not deduce their template parameters.

Undeduced template parameters and parameters that have conflicting deduction can be fixed by explicitly specifying them when instantiating the template:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <iostream>

template <typename T>
const T& min(const T& x, const T& y)
{
	if (y < x)
		return y;
	else
		return x;
}

template <typename U, typename T>
U convert_to(T value)
{
	return static_cast<U>(value);
}

int main()
{
	// ::min(1, 2.0); // error: conflicting deductions for T
	::min<double>(1, 2.0); // ok: T = double

	// U is explicitly specified as unsigned short
	// T is deduced from the argument as int
	std::cout << convert_to<unsigned short>(-1); // ok
}

The order of template parameters is crucial. You generally want to have non-deducible template parameters first and deducible parameters later:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// good: T is deduced and U can be specified first
template <typename U, typename T>
U convert_to1(T value)
{
	return static_cast<U>(value);
}

// also good, just different (swapped) names of template parameters
template <typename T, typename U>
T convert_to2(U value)
{
	return static_cast<T>(value);
}

// bad: T will be deduced but U has to be specified second
// any call will have to specify both to reach U
//
// error: U not specified and can not be deduced
// convert_to3<int>(1)
//
// will work, but verbose and duplicate work
// (int is both deduced and specified explicitly)
// convert_to3<int, double>(1)
template <typename T, typename U>
U convert_to3(T value)
{
	return static_cast<U>(value);
}

Default template arguments

Another way of dealing with non-deducible (but not conflicting) template parameters is to provide defaults. Below is a simplified implementation of std::exchange - a function which sets a new value and returns the old one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <vector>
#include <string>
#include <iostream>

template <typename T, typename U = T>
T exchange(T& object, U new_value)
{
	T old_value = object;
	object = new_value;
	return old_value;
}

int main()
{
	// the argument is non-deducible but the default template parameter solves the problem
	std::vector<int> v = {1, 2};
	std::cout << ::exchange(v, {1, 2, 3, 4}).size() << "\n";

	// the argument is deducible but U (const char*) is different from T (std::string)
	std::string s = "abc";
	std::cout << ::exchange(s, "xyz") << "\n";
}

The function could be implemented using just one template parameter for both arguments but:

  • using 2 different template type parameters allows assignment of objects of a different type

    • in some cases this improves performance by avoiding creation of expensive objects (e.g. strings)

    • in some cases this is desired because the target object intentionally accepts objects of a different type (e.g. a fraction class accepting assignment from integer types)

  • the default template argument functions as a fallback to T when the argument type can not be deduced

In short, such implementation (2 template parameters with default) results in best of both worlds: support for mixed-type assignments and support for non-deducible arguments.

Note another small thing: the default of the second template parameter depends on the first. Such dependency is not allowed within non-template default arguments:

1
2
3
4
5
6
7
8
9
10

int f1(int x, int y = 0); // ok

// error: parameter not allowed as default argument
// int f2(int x, int y = x);

template <typename T, typename U = int> // ok
U g1(T x, T y);

template <typename T, typename U = T> // also ok!
U g2(T x, T y);

Summary