16.2. Template Argument Deduction

We’ve seen that, by default, the compiler uses the arguments in a call to determine the template parameters for a function template. The process of determining the template arguments from the function arguments is known as template argument deduction. During template argument deduction, the compiler uses types of the arguments in the call to find the template arguments that generate a version of the function that best matches the given call.

16.2.1. Conversions and Template Type Parameters

As with a nontemplate function, the arguments we pass in a call to a function template are used to initialize that function’s parameters. Function parameters whose type uses a template type parameter have special initialization rules. Only a very limited number of conversions are automatically applied to such arguments. Rather than converting the arguments, the compiler generates a new instantiation.

 

As usual, top-level consts (§ 2.4.3, p. 63) in either the parameter or the argument are ignored. The only other conversions performed in a call to a function template are

• const conversions: A function parameter that is a reference (or pointer) to a const can be passed a reference (or pointer) to a nonconst object (§ 4.11.2, p. 162).

• Array- or function-to-pointer conversions: If the function parameter is not a reference type, then the normal pointer conversion will be applied to arguments of array or function type. An array argument will be converted to a pointer to its first element. Similarly, a function argument will be converted to a pointer to the function’s type (§ 4.11.2, p. 161).

Other conversions, such as the arithmetic conversions (§ 4.11.1, p. 159), derived-to-base (§ 15.2.2, p. 597), and user-defined conversions (§ 7.5.4, p. 294, and § 14.9, p. 579), are not performed.

As examples, consider calls to the functions fobj and fref. The fobj function copies its parameters, whereas fref’s parameters are references:

template <typename T> T fobj(T, T); // arguments are copied
template <typename T> T fref(const T&, const T&); // references
string s1("a value");
const string s2("another value");
fobj(s1, s2); // calls fobj(string, string); const is ignored
fref(s1, s2); // calls fref(const string&, const string&)
              // uses premissible conversion to const on s1
int a[10], b[42];
fobj(a, b); // calls f(int*, int*)
fref(a, b); // error: array types don't match

In the first pair of calls, we pass a string and a const string. Even though these types do not match exactly, both calls are legal. In the call to fobj, the arguments are copied, so whether the original object is const doesn’t matter. In the call to fref, the parameter type is a reference to const. Conversion to const for a reference parameter is a permitted conversion, so this call is legal.

In the next pair of calls, we pass array arguments in which the arrays are different sizes and hence have different types. In the call to fobj, the fact that the array types differ doesn’t matter. Both arrays are converted to pointers. The template parameter type in fobj is int*. The call to fref, however, is illegal. When the parameter is a reference, the arrays are not converted to pointers (§ 6.2.4, p. 217). The types of a and b don’t match, so the call is in error.

A template type parameter can be used as the type of more than one function parameter. Because there are limited conversions, the arguments to such parameters must have essentially the same type. If the deduced types do not match, then the call is an error. For example, our compare function (§ 16.1.1, p. 652) takes two const T& parameters. Its arguments must have essentially the same type:

long lng;
compare(lng, 1024); // error: cannot instantiate compare(long, int)

This call is in error because the arguments to compare don’t have the same type. The template argument deduced from the first argument is long; the one for the second is int. These types don’t match, so template argument deduction fails.

If we want to allow normal conversions on the arguments, we can define the function with two type parameters:

// argument types can differ but must be compatible
template <typename A, typename B>
int flexibleCompare(const A& v1, const B& v2)
{
    if (v1 < v2) return -1;
    if (v2 < v1) return 1;
    return 0;
}

Now the user may supply arguments of different types:

long lng;
flexibleCompare(lng, 1024); // ok: calls flexibleCompare(long, int)

Of course, a < operator must exist that can compare values of those types.

Normal Conversions Apply for Ordinary Arguments

A function template can have parameters that are defined using ordinary types—that is, types that do not involve a template type parameter. Such arguments have no special processing; they are converted as usual to the corresponding type of the parameter (§ 6.1, p. 203). For example, consider the following template:

template <typename T> ostream &print(ostream &os, const T &obj)
{
    return os << obj;
}

The first function parameter has a known type, ostream&. The second parameter, obj, has a template parameter type. Because the type of os is fixed, normal conversions are applied to arguments passed to os when print is called:

In the first call, the type of the first argument exactly matches the type of the first parameter. This call will cause a version of print that takes an ostream& and an int to be instantiated. In the second call, the first argument is an ofstream and there is a conversion from ofstream to ostream& (§ 8.2.1, p. 317). Because the type of this parameter does not depend on a template parameter, the compiler will implicitly convert f to ostream&.

16.2.2. Function-Template Explicit Arguments

 

In some situations, it is not possible for the compiler to deduce the types of the template arguments. In others, we want to allow the user to control the template instantiation. Both cases arise most often when a function return type differs from any of those used in the parameter list.

In this case, there is no argument whose type can be used to deduce the type of T1. The caller must provide an explicit template argument for this parameter on each call to sum.

We supply an explicit template argument to a call the same way that we define an instance of a class template. Explicit template arguments are specified inside angle brackets after the function name and before the argument list:

// T1 is explicitly specified; T2 and T3 are inferred from the argument types
auto val3 = sum<long long>(i, lng); // long long sum(int, long)

This call explicitly specifies the type for T1. The compiler will deduce the types for T2 and T3 from the types of i and lng.

Explicit template argument(s) are matched to corresponding template parameter(s) from left to right; the first template argument is matched to the first template parameter, the second argument to the second parameter, and so on. An explicit template argument may be omitted only for the trailing (right-most) parameters, and then only if these can be deduced from the function parameters. If our sum function had been written as

// poor design: users must explicitly specify all three template parameters
template <typename T1, typename T2, typename T3>
T3 alternative_sum(T2, T1);

then we would always have to specify arguments for all three parameters:

// error: can't infer initial template parameters
auto val3 = alternative_sum<long long>(i, lng);
// ok: all three parameters are explicitly specified
auto val2 = alternative_sum<long long, int, long>(i, lng);

Normal Conversions Apply for Explicitly Specified Arguments

For the same reasons that normal conversions are permitted for parameters that are defined using ordinary types (§ 16.2.1, p. 680), normal conversions also apply for arguments whose template type parameter is explicitly specified:

16.2.3. Trailing Return Types and Type Transformation

Using an explicit template argument to represent a template function’s return type works well when we want to let the user determine the return type. In other cases, requiring an explicit template argument imposes a burden on the user with no compensating advantage. For example, we might want to write a function that takes a pair of iterators denoting a sequence and returns a reference to an element in the sequence:

template <typename It>
??? &fcn(It beg, It end)
{
    // process the range
    return *beg;  // return a reference to an element from the range
}

We don’t know the exact type we want to return, but we do know that we want that type to be a reference to the element type of the sequence we’re processing:

vector<int> vi = {1,2,3,4,5};
Blob<string> ca = { "hi", "bye" };
auto &i = fcn(vi.begin(), vi.end()); // fcn should return int&
auto &s = fcn(ca.begin(), ca.end()); // fcn should return string&

Here, we know that our function will return *beg, and we know that we can use decltype(*beg) to obtain the type of that expression. However, beg doesn’t exist until the parameter list has been seen. To define this function, we must use a trailing return type (§ 6.3.3, p. 229). Because a trailing return appears after the parameter list, it can use the function’s parameters:

// a trailing return lets us declare the return type after the parameter list is seen
template <typename It>
auto fcn(It beg, It end) -> decltype(*beg)
{
    // process the range
    return *beg;  // return a reference to an element from the range
}

Here we’ve told the compiler that fcn’s return type is the same as the type returned by dereferencing its beg parameter. The dereference operator returns an lvalue (§ 4.1.1, p. 136), so the type deduced by decltype is a reference to the type of the element that beg denotes. Thus, if fcn is called on a sequence of strings, the return type will be string&. If the sequence is int, the return will be int&.

The Type Transformation Library Template Classes

Sometimes we do not have direct access to the type that we need. For example, we might want to write a function similar to fcn that returns an element by value (§ 6.3.2, p. 224), rather than a reference to an element.

The problem we face in writing this function is that we know almost nothing about the types we’re passed. In this function, the only operations we know we can use are iterator operations, and there are no iterator operations that yield elements (as opposed to references to elements).

To obtain the element type, we can use a library type transformation template. These templates are defined in the type_traits header. In general the classes in type_traits are used for so-called template metaprogramming, a topic that is beyond the scope of this Primer. However, the type transformation templates are useful in ordinary programming as well. These templates are described in Table 16.1 and we’ll see how they are implemented in § 16.5 (p. 710).

Table 16.1. Standard Type Transformation Templates

 

In this case, we can use remove_reference to obtain the element type. The remove_reference template has one template type parameter and a (public) type member named type. If we instantiate remove_reference with a reference type, then type will be the referred-to type. For example, if we instantiate remove_reference<int&>, the type member will be int. Similarly, if we instantiate remove_reference<string&>, type will be string, and so on. More generally, given that beg is an iterator:

 

 

remove_reference<decltype(*beg)>::type

 

will be the type of the element to which beg refers: decltype(*beg) returns the reference type of the element type. remove_reference::type strips off the reference, leaving the element type itself.

 

Using remove_reference and a trailing return with decltype, we can write our function to return a copy of an element’s value:

 

Note that type is member of a class that depends on a template parameter. As a result, we must use typename in the declaration of the return type to tell the compiler that type represents a type (§ 16.1.3, p. 670).

Each of the type transformation templates described in Table 16.1 works similarly to remove_reference. Each template has a public member named type that represents a type. That type may be related to the template’s own template type parameter in a way that is indicated by the template’s name. If it is not possible (or not necessary) to transform the template’s parameter, the type member is the template parameter type itself. For example, if T is a pointer type, then remove_pointer<T>::type is the type to which T points. If T isn’t a pointer, then no transformation is needed. In this case, type is the same type as T.

16.2.4. Function Pointers and Argument Deduction

 

When we initialize or assign a function pointer (§ 6.7, p. 247) from a function template, the compiler uses the type of the pointer to deduce the template argument(s).

As an example, assume we have a function pointer that points to a function returning an int that takes two parameters, each of which is a reference to a const int. We can use that pointer to point to an instantiation of compare:

template <typename T> int compare(const T&, const T&);
// pf1 points to the instantiation int compare(const int&, const int&)
int (*pf1)(const int&, const int&) = compare;

The type of the parameters in pf1 determines the type of the template argument for T. The template argument for T is int. The pointer pf1 points to the instantiation of compare with T bound to int. It is an error if the template arguments cannot be determined from the function pointer type:

// overloaded versions of func; each takes a different function pointer type
void func(int(*)(const string&, const string&));
void func(int(*)(const int&, const int&));
func(compare); // error: which instantiation of compare?

The problem is that by looking at the type of func’s parameter, it is not possible to determine a unique type for the template argument. The call to func could instantiate the version of compare that takes ints or the version that takes strings. Because it is not possible to identify a unique instantiation for the argument to func, this call won’t compile.

We can disambiguate the call to func by using explicit template arguments:

// ok: explicitly specify which version of compare to instantiate
func(compare<int>);  // passing compare(const int&, const int&)

This expression calls the version of func that takes a function pointer with two const int& parameters.

16.2.5. Template Argument Deduction and References

 

In order to understand type deduction from a call to a function such as

 

 

template <typename T> void f(T &p);

 

in which the function’s parameter p is a reference to a template type parameter T, it is important to keep in mind two points: Normal reference binding rules apply; and consts are low level, not top level.

 

Type Deduction from Lvalue Reference Function Parameters

 

When a function parameter is an ordinary (lvalue) reference to a template type parameter (i.e., that has the form T&), the binding rules say that we can pass only an lvalue (e.g., a variable or an expression that returns a reference type). That argument might or might not have a const type. If the argument is const, then T will be deduced as a const type:

 

 

template <typename T> void f1(T&);  // argument must be an lvalue
// calls to f1 use the referred-to type of the argument as the template parameter type
f1(i);   //  i is an int; template parameter T is int
f1(ci);  //  ci is a const int; template parameter T is const int
f1(5);   //  error: argument to a & parameter must be an lvalue

 

If a function parameter has type const T&, normal binding rules say that we can pass any kind of argument—an object (const or otherwise), a temporary, or a literal value. When the function parameter is itself const, the type deduced for T will not be a const type. The const is already part of the function parameter type; therefore, it does not also become part of the template parameter type:

 

 

template <typename T> void f2(const T&); // can take an rvalue
// parameter in f2 is const &; const in the argument is irrelevant
// in each of these three calls, f2's function parameter is inferred as const int&
f2(i);  // i is an int; template parameter T is int
f2(ci); // ci is a const int, but template parameter T is int
f2(5);  // a const & parameter can be bound to an rvalue; T is int

 

Type Deduction from Rvalue Reference Function Parameters

 

When a function parameter is an rvalue reference (§ 13.6.1, p. 532) (i.e., has the form T&&), normal binding rules say that we can pass an rvalue to this parameter. When we do so, type deduction behaves similarly to deduction for an ordinary lvalue reference function parameter. The deduced type for T is the type of the rvalue:

template <typename T> void f3(T&&);
f3(42); // argument is an rvalue of type int; template parameter T is int

Reference Collapsing and Rvalue Reference Parameters

Deducing T as int& would seem to mean that f3’s function parameter would be an rvalue reference to the type int&. Ordinarily, we cannot (directly) define a reference to a reference (§ 2.3.1, p. 51). However, it is possible to do so indirectly through a type alias (§ 2.5.1, p. 67) or through a template type parameter.

There are two important consequences from these rules:

It is surprisingly hard to write code that is correct when the types involved might be plain (nonreference) types or reference types (although the type transformation classes such as remove_reference can help (§ 16.2.3, p. 684)).

In practice, rvalue reference parameters are used in one of two contexts: Either the template is forwarding its arguments, or the template is overloaded. We’ll look at forwarding in § 16.2.7 (p. 692) and at template overloading in § 16.3 (p. 694).

For now, it’s worth noting that function templates that use rvalue references often use overloading in the same way as we saw in § 13.6.3 (p. 544):

template <typename T> void f(T&&);      // binds to nonconst rvalues
template <typename T> void f(const T&); // lvalues and const rvalues

As with nontemplate functions, the first version will bind to modifiable rvalues and the second to lvalues or to const rvalues.

16.2.6. Understanding std::move

 

The library move function (§ 13.6.1, p. 533) is a good illustration of a template that uses rvalue references. Fortunately, we can use move without understanding the template mechanisms that it uses. However, looking at how move works can help cement our general understanding, and use, of templates.

In § 13.6.2 (p. 534) we noted that although we cannot directly bind an rvalue reference to an lvalue, we can use move to obtain an rvalue reference bound to an lvalue. Because move can take arguments of essentially any type, it should not be surprising that move is a function template.

How std::move Is Defined

The standard defines move as follows:

// for the use of typename in the return type and the cast see § 16.1.3 (p. 670)
// remove_reference is covered in § 16.2.3 (p. 684)
template <typename T>
typename remove_reference<T>::type&& move(T&& t)
{
   // static_cast covered in § 4.11.3 (p. 163)
   return static_cast<typename remove_reference<T>::type&&>(t);
}

This code is short but subtle. First, move’s function parameter, T&&, is an rvalue reference to a template parameter type. Through reference collapsing, this parameter can match arguments of any type. In particular, we can pass either an lvalue or an rvalue to move:

string s1("hi!"), s2;
s2 = std::move(string("bye!")); // ok: moving from an rvalue
s2 = std::move(s1);  // ok: but after the assigment s1 has indeterminate value

How std::move Works

In the first assignment, the argument to move is the rvalue result of the string constructor, string("bye"). As we’ve seen, when we pass an rvalue to an rvalue reference function parameter, the type deduced from that argument is the referred-to type (§ 16.2.5, p. 687). Thus, in std::move(string("bye!")):

• The deduced type of T is string.

• Therefore, remove_reference is instantiated with string.

• The type member of remove_reference<string> is string.

• The return type of move is string&&.

• move’s function parameter, t, has type string&&.

Accordingly, this call instantiates move<string>, which is the function

string&& move(string &&t)

The body of this function returns static_cast<string&&>(t). The type of t is already string&&, so the cast does nothing. Therefore, the result of this call is the rvalue reference it was given.

Now consider the second assignment, which calls std::move(s1). In this call, the argument to move is an lvalue. This time:

• The deduced type of T is string& (reference to string, not plain string).

• Therefore, remove_reference is instantiated with string&.

• The type member of remove_reference<string&> is string,

• The return type of move is still string&&.

• move’s function parameter, t, instantiates as string& &&, which collapses to string&.

Thus, this call instantiates move<string&>, which is

string&& move(string &t)

and which is exactly what we’re after—we want to bind an rvalue reference to an lvalue. The body of this instantiation returns static_cast<string&&>(t). In this case, the type of t is string&, which the cast converts to string&&.

static_cast from an Lvalue to an Rvalue Reference Is Permitted

Ordinarily, a static_cast can perform only otherwise legitimate conversions (§ 4.11.3, p. 163). However, there is again a special dispensation for rvalue references: Even though we cannot implicitly convert an lvalue to an rvalue reference, we can explicitly cast an lvalue to an rvalue reference using static_cast.

Binding an rvalue reference to an lvalue gives code that operates on the rvalue reference permission to clobber the lvalue. There are times, such as in our StrVec reallocate function in § 13.6.1 (p. 533), when we know it is safe to clobber an lvalue. By letting us do the cast, the language allows this usage. By forcing us to use a cast, the language tries to prevent us from doing so accidentally.

Finally, although we can write such casts directly, it is much easier to use the library move function. Moreover, using std::move consistently makes it easy to find the places in our code that might potentially clobber lvalues.

16.2.7. Forwarding

Some functions need to forward one or more of their arguments with their types unchanged to another, forwarded-to, function. In such cases, we need to preserve everything about the forwarded arguments, including whether or not the argument type is const, and whether the argument is an lvalue or an rvalue.

As an example, we’ll write a function that takes a callable expression and two additional arguments. Our function will call the given callable with the other two arguments in reverse order. The following is a first cut at our flip function:

// template that takes a callable and two parameters
// and calls the given callable with the parameters ''flipped''
// flip1 is an incomplete implementation: top-level const and references are lost
template <typename F, typename T1, typename T2>
void flip1(F f, T1 t1, T2 t2)
{
    f(t2, t1);
}

This template works fine until we want to use it to call a function that has a reference parameter:

void f(int v1, int &v2) // note v2 is a reference
{
    cout << v1 << " " << ++v2 << endl;
}

Here f changes the value of the argument bound to v2. However, if we call f through flip1, the changes made by f do not affect the original argument:

f(42, i);        // f changes its argument i
flip1(f, j, 42); // f called through flip1 leaves j unchanged

The problem is that j is passed to the t1 parameter in flip1. That parameter has is a plain, nonreference type, int, not an int&. That is, the instantiation of this call to flip1 is

void flip1(void(*fcn)(int, int&), int t1, int t2);

 

The value of j is copied into t1. The reference parameter in f is bound to t1, not to j.

 

Defining Function Parameters That Retain Type Information

 

To pass a reference through our flip function, we need to rewrite our function so that its parameters preserve the “lvalueness” of its given arguments. Thinking ahead a bit, we can imagine that we’d also like to preserve the constness of the arguments as well.

 

We can preserve all the type information in an argument by defining its corresponding function parameter as an rvalue reference to a template type parameter. Using a reference parameter (either lvalue or rvalue) lets us preserve constness, because the const in a reference type is low-level. Through reference collapsing (§ 16.2.5, p. 688), if we define the function parameters as T1&& and T2&&, we can preserve the lvalue/rvalue property of flip’s arguments (§ 16.2.5, p. 687):

template <typename F, typename T1, typename T2>
void flip2(F f, T1 &&t1, T2 &&t2)
{
    f(t2, t1);
}

As in our earlier call, if we call flip2(f, j, 42), the lvalue j is passed to the parameter t1. However, in flip2, the type deduced for T1 is int&, which means that the type of t1 collapses to int&. The reference t1 is bound to j. When flip2 calls f, the reference parameter v2 in f is bound to t1, which in turn is bound to j. When f increments v2, it is changing the value of j.

what is passed to g will be the parameter named t2 inside flip2. A function parameter, like any other variable, is an lvalue expression (§ 13.6.1, p. 533). As a result, the call to g in flip2 passes an lvalue to g’s rvalue reference parameter.

Using std::forward to Preserve Type Information in a Call

We can use a new library facility named forward to pass flip2’s parameters in a way that preserves the types of the original arguments. Like move, forward is defined in the utility header. Unlike move, forward must be called with an explicit template argument (§ 16.2.2, p. 682). forward returns an rvalue reference to that explicit argument type. That is, the return type of forward<T> is T&&.