Title: The C++ Template Argument Deduction

With the increasing popularity of the Standard C++ library and the STL, it is becoming more and more important for a C++ programmer to understand the underlying mechanics of generic programming in C++. In this article I will look into the little known details of template argument deduction, an area of the C++ language that a lot of programmers find difficult to comprehend and a knowledge of which is vital for using Standard C++ efficiently.

This article is intended for experienced C++ programmers who wish to know the exact and yet clearly explained details of how argument deduction is done in the C++ language. Deduction of template arguments is an incredibly vast area and covering it in detail and in all its entirety in one article would be impossible, so I chose to pick out the most frequently used contexts that call for template argument deduction and explain them in detail rather than gloss over all cases of use of argument deduction. The following uses of argument deduction are covered in this article: "Deducing template arguments from a function call expression", "Deducing template arguments when taking the address of a (member) function template specialization", "Deducing template arguments for explicit specialization of a (member) function template".

Template argument deduction only pertains to function templates. This means that whenever you reference a specialization of a class template, you need to explicitly specify all template arguments. I will therefore refer to function templates only in the remainder of the article.

Although there are different cases when the language calls on template argument deduction, they are all based on deducing template arguments from a type. So it is here that the discussion will start.

Template parameters come in three flavors: 1) template template parameters (associated with a class template, which I will denote as TT for the remainder of the article), 2) type template parameters (associated with a type, denoted as T), and 3) non-type template parameters (most often associated with a constant value of integral or enumeration type, denoted as i).

To deduce a template argument from a given type means that you have two types - a type-id that contains one or more template parameters, I will call such a type-id P for the rest of the article (some combinations of TTs, Ts, and is within one P are possible). For the moment I will omit the details of how P is obtained, suffice to say that in most cases it is one of the function parameters of a function template declaration. The other type that you have is a type-id that comprises no template parameters, which I will call A, and an attempt is made to find a class template for a TT, a type for T, and a value for i so that P becomes identical to A.

Example:

template<template<class> class TT, class T>
T* alloc(TT<T>& a) {
  return a.allocate(16);
}

For this template P can be TT<T>. If the type-id A from which we want to deduce TT and T is std::allocator<int>, then argument deduction deduces TT to be std::allocator and T to be int. This results in P becoming std::allocator<int>, i.e. identical to A.

So far so good, but what kind of type can A be and what combinations of TTs, Ts, and is are allowed in P so that template argument deduction is possible on the template parameters that P consists of? The first part of the question

is easier to answer since for template argument deduction the language allows A to be any valid C++ type (not a constant reference to constant function, of course). As for P, only the following combinations are allowed:

Where cv-seq designates any valid sequence of const and volatile qualifiers, _opt stands for optional, (T) designates a list of function parameters where at least one parameter is T, <T> designates a list of template arguments where at least one template argument is T, and, finally, <i> designates a list of template arguments where at least one template argument is i. type refers to any C++ type which consists of no template parameters, i.e. it does not depend on the template parameters of the function template. The construct class-template-name designates a name of a class template that is not a template template parameter. For instance this is shown in the following code snippet, where P can be std::allocator<T> and class-template-name is thus std::allocator.

template<class T>
T* alloc(std::allocator<T>& a);

A few explanations are necessary to make sense of the above. When there is more than one T in some of the combinations shown, the Ts do not need to be the same type template parameter. A good example that demonstrates this is the standard object generator for pointers to member functions - the function template mem_fun_ref. Here is one of its declarations (the name mem_fun_ref is overloaded):

template<class R, class T, class A>
mem_fun1_ref_t<R,T,A> mem_fun_ref(R(T::*)(A));

Here P can be R(T::*)(A), which is a variant of T(T::*)(T).

The second point that must be made about the allowable combinations is that they can be applied recursively - any of the 24 forms shown can be used in place of T in forming other permissible combinations, provided, of course, that the resulting form is a legal C++ type-id. For instance P having a form of type(T::*)(TT<T>,char)const is composed of type(T::*)(T)const and TT<T> and is accepted by template argument deduction (remember (T) designates a list of function parameters where at least one parameter is T, so (TT<T>,char) is a variation on (T)). The following function template declaration clarifies this example further:

template<template<class> class Alloc,
                     class C, class T>
void dummy_alloc(
            void(C::*)(Alloc<T>,char)const);

Here one possible form of P is void(C::*)(Alloc<T>)const. If the corresponding A designates the type void(Myclass::*)(std::allocator<int>)const, then template argument deduction will deduce Alloc to be std::allocator, C to be Myclass, and T to be int.

The forms involving template template parameters TT<T>, TT<i>, TT<> require special elucidation. Each of these forms specifies the use of a class template TT, i.e. a class template specialization, meaning that whenever you use any of the above three combinations in P, you need to supply the same number of template arguments as the declaration of TT specifies, unless the declaration of TT contains one or more default template arguments in which case the trailing template arguments can be omitted. Note that the angle brackets must be present even if all TT's template parameters have defaults. The following example demonstrates the use of a template template parameter in P where TT has default template arguments for all its parameters.

template<class T, template<class=T> class TT> >
void foo(int(*arr)(TT<>));

In this example P can be int(*arr)(TT<T>) and given A of int(*)(std::allocator<int>) template argument deduction will resolve T to int and TT to std::allocator.

Although there is a form TT<> among the allowable choices for P, it shouldn't be taken as a template template parameter with no template arguments. In fact it just means that the list of arguments doesn't contain any other template parameters and must contain non-dependent types, which is illustrated by the following example:

template<template<class, class> class Sequence>
void empty_sequence(Sequence<int,
          std::allocator<int> >& seq) {
  seq.empty();
}

In this function template, P can be Sequence<T, Alloc<T> >, which is a variant of TT<T1,T2> (it is allowed to treat the form TT<T> as TT<T1,T2> where T1 and T2 are type template parameters with T2 being TT<T>, see the notes to the table of allowable forms) where, as you can see, the type parameter T1 is T and T2 is Alloc<T>. Given a corresponding A of std::vector<int, std::allocator<int> >, template argument deduction will be able to deduce Sequence to be std::vector, Alloc to be std::allocator, and T to be int in spite of the T appearing twice within the P. In fact it will deduce T twice and, with above A, each time to the same type.

But what happens if P references a type template parameter T more than once and the corresponding A supplies two different types for each occurrence of T in P? For instance, in the previous example if A had a form of std::vector<int,std::allocator<char> >, then template argument deduction would deduce T to have type int in one place and char in the other. The language prohibits these scenarios and deduction fails for P's function template when the context supplies such an A.

A careful look at the table of allowable forms reveals that it's not possible to form a qualified P by using them (even if the use is recursive). This means that if you make P qualified, template argument deduction is not possible for it. For example:

template<template<class, class> class Sequence,
  template<class> class Alloc, class T>
void empty_sequence(T::Sequence<T, Alloc<T> >&);

In this code sample one possible P is T::Sequence<T,Alloc<T> > and because of this P being qualified, template argument deduction is not possible regardless of the form that the corresponding A has.

As I said before, in forming P a standard conforming compiler is allowed to replace T in any of the allowable forms with another form from the table, but no such provision is made for i. There are only four forms that contain i in the table, these are type[i], T[i], class-template-name<i>, and TT<i>. And in all these forms i is used as an expression that has the form of a simple identifier. Thus, by strictly following the rules it is not possible to get such P that would contain i in a form different from a simple identifier. It follows that if you have a P wherein i is used in an expression which doesn't have the form of a simple identifier, template argument deduction is not possible.

template<unsigned i>
void foo(int(&p)[+i]);

In this example P can be int[+i]. And no matter what form the corresponding A has, no argument deduction is possible for this P.

In a similar manner, no recursive use of the allowable forms enables to get P of, for example, this form: type(*)[sizeof(T)]. This is illustrated in the following code snippet:

template<class T, template<class> class TT>
void foo(int(*arr)[sizeof(TT<T>)]);

Which again means that should argument deduction be presented with such P, it will not deduce any template parameters in it.

In general, a P which is qualified or contains i involved in an expression other than a simple identifier (that is, not used by itself) or contains any other template parameter used in an expression such as sizeof is conventionally called a nondeduced context. Having such a P in a template declaration is not ill-formed, it's just that template argument deduction cannot deduce any template parameters in that P regardless of the form of the corresponding A. This effectively means that the template parameters that such P comprises must be either explicitly specified or deduced elsewhere. I'd like to note here that it is not possible to get a nondeduced context by recursively applying only the allowable forms. When consulting the table of allowable forms you should regard a nondeduced conext as a non-dependent type, which is denoted there as type.

Now that I've explained the concept of deducing template arguments from a type, it is high time that I embark upon some of the contexts that call on template argument deduction.

It is not uncommon for C++ programmers to initialize an object of type pointer to (member) function with an expression referring to a (member) function. As is the case with non-template (member) functions, (member) function template specializations can be used in such contexts too, much like normal non-template functions:

ptrdiff_t count_chr(const char* str,
                    const char ch) {
  // using the specialization of the standard
  // 'count' algorithm
  ptrdiff_t (* pf)(const char*, const char*,
      const char&)
    = std::count<const char*, char>;
 return (*pf)(str, str+std::strlen(str), ch);
}

One thing to remember here is that there are no implicit conversions etween pointers to functions of different types and pointers to member functions of the same class of different types. There must be an exact match:

struct test {
  void update1(char*, char*);
  void update2(const char*, const char*);
  void update3(const char*, const char*,
                        int=0);
};
void  testing() {
  // Error, no exact match
  void (test::* pmf1)(const char*,
        const char*) = &test::update1;
  // OK
  void (test::* pmf2)(const char*,
        const char*) = &test::update2;
  // Error, default arguments are not
  // part of function type
  void (test::* pmf3)(const char*,
        const char*) = &test::update3;
}

Before plunging right into the nitty-gritty details of argument deduction, it would be helpful if I clarified the meaning of the term function template specialization, which has already been used a number of times in this article (member function template specializations follow the same conventions and will be omitted from the following discussion).

A function template specialization is a use of a function template name with a full set of template arguments that uniquely identifies exactly one specialization. For instance in the code example above std::count<const char*,char> is a specialization of the function template count. Sometimes a set of template arguments is given explicitly in a specialization and the number of arguments in the set matches the number of template parameters of the corresponding template, sometimes the set contains fewer template arguments than the number of template parameters of the matching function template, and sometimes it contains no template arguments at all (even the angle brackets could be left out). Whenever some or all template arguments are omitted, they must be deducible from the context and the result of the deduction is a function template specialization. When a full set of template arguments is specified, no template argument deduction takes place.

The point is that a C++ programmer never deals with function templates themselves (except, for example, when they declare, define or explicitly specialize them). Most of the time it is a specialization of a given template that a programmer uses. Below an earlier code fragment has been modified to clarify the points that were made earlier:

ptrdiff_t count_chr(const char* str,
                    const char ch) {
  // Using the specialization of the standard
  //    'count' algorithm without specifying
  //    template arguments explicitly.
  // 1. Name lookup finds the function template
  //  template<class InIter, class T>
  //  typename 
  //    iterator_traits<InIter>::difference_type
  //      count(InIter first, InIter last,
  //                    const T& val);
  // 2. Template argument deduction deduces the
  //  template arguments to have types 'const
  //  char*' and 'char' respectively. Thus
  //  making the expression 'std::count'
  //  equivalent to 'std::count<const char*,
  //  char>'
  //
   ptrdiff_t (* pf)(const char*,
       const char*, const char&) = std::count;
   return (*pf)(str, str+std::strlen(str), ch);
}

Returning to template argument deduction when taking the address of a (member) function template, what I need to explain is how P's and A's are formed when some template arguments are not specified. The answer is surprisingly simple - there is just one P and one A. P is the type of the initializer expression (possibly converted to a type of pointer to function) and A is the type of the object being initialized.

For instance in the code sample above:

P is typename iterator_traits<InIter>::
difference_type(*)(InIter, InIter, const T&),

which in terms of the conventions used in the table of allowable forms is a variant of type(*)(T).

A is ptrdiff_t(*)(const char*, const char*, const char&) and template argument deduction will be seeking such types for InIter and T that will make P identical to A.

If the initializer expression was std::count<const char*>, only one template argument would have to be deduced (since one is specified explicitly), i.e. in that case P would be:

typename iterator_traits<const char*>::
                     difference_type(*)(
   const char*, const char*, const T&)

It is easy enough to write the initializer in such a way that no matching specialization could be found. For example the initializer of the form std::count<char*> will result in P being:

typename iterator_traits<char*>::
   difference_type(*)(char*, char*, const T&),

which doesn't enable template argument deduction to make such P identical to the corresponding A.

If the name of the function template whose address is being taken is overloaded, then there are as many Ps as there are overloaded function templates by that name and template argument deduction will be performed against all of them with the same A. Those templates for which deduction does not succeed will not be considered further. If the initializer expression does not contain the angle brackets, non-template functions will also be considered, i.e. if the namespace std contained a function declaration:

ptrdiff_t count(const char*,
                const char*, const char&);

this function would also be considered in the example above. It is then up to overload resolution to decide which function template specialization is the most specialized and choose it. Note that a non-template function is always preferred to any function template specialization, as a non-template function is considered more specialized than a corresponding function template specialization.

It is quite common for P to contain multiple references to the same template parameter and my example with the standard count algorithm showed it. The first reference was in the return type iterator_traits<InIter>::difference_type, which is a nondeduced context and is therefore ignored, meaning that InIter must be deducible from its other occurrences in the P. The second and the third appearances are the same and have the form InIter. As the corresponding parts of A also constitute the same type const char*, InIter can be deduced from either part to be the same type. If they were different, for instance, if A was ptrdiff_t(*)(const char*, char*, const char&), then InIter would be deduced to be const char* in one part and to char* in the other. Whenever such a situation arises, argument deduction fails. See the discussion on this issue in the previous chapter.

Consider the following piece of code in which two overloaded declarations of the function template foo are defined:

template<class T>
struct example {
  template<class U> // 1st member template
  int foo(U);
  template<class U> // 2nd member template
  int foo(U*);
};

Now suppose I have an explicit specialization of the following form in the same translation unit:

template<> template<>
int example<char>::foo(int*);

But which member function template is explicitly specialized here? One possible answer is that it is the second one, but is it really? The truth is that for explicit specializations of (member) function templates, template argument deduction is done in a way similar to that I covered in the previous chapter - A is the function type of an explicit specialization named N and P's are the function types of templates with name N that are members of the same scope as the explicit specialization. Template argument deduction then makes an attempt to make each of the P's identical to A (for more on that see the chapter "Deducing template arguments from a type" at the beginning of this article). Those templates for which argument deduction fails are not considered further. Those for which it does are submitted to overload resolution and the latter makes a decision as to which of the templates is more specialized than the others. When it can make this decision, the explicit specialization is considered to specialize the most specialized template, otherwise the explicit specialization declaration is ill-formed.

In the example shown A is int example<char>::foo(int*). Given that the explicit specialization is a member of the class scope example<char>, there are two P's: P₁ is int example<char>::foo(U), and P₂ is int example<char>::foo(U*). For P₁ argument deduction succeeds with U deduced to be int*. For P₂ it succeeds too resulting in U having type int. So both member function templates are submitted to overload resolution for finding out which of them is more specialized than the other, and the latter selects the second, meaning that the explicit specialization specializes the second member template.

When declaring an explicit specialization, it is possible to explicitly specify some or all the template arguments of the function template being specialized. The arguments will actually be applied to the templates of the same name and scope as the explicit specialization. This can come handy in influencing the result of argument deduction. For example if the same translation unit contains another explicit specialization of the form:

template<> template<>
int example<char>::foo<int*>(int*);

Things will proceed as follows:

No argument deduction will take place at all since the two member templates have just one template parameter and it has been specified. Since P₂ now has a different type from the type of the explicit specialization it is no longer considered, thus the explicit specialization specializes the first member template.

When name lookup finds a name in a function call expression to denote a function template or a (non-special) member function template and the call leaves one or more trailing template arguments unspecified or has a form without the angle brackets, template argument deduction comes into action:

int main() {
  int data[] = {3, 0, -1, -3, 16, };

  // Name lookup finds the function template
  // template<class RandomAccessIterator>
  // void sort(RandomAccessIterator first,
  //           RandomAccessIterator last);
  //
  // Template argument deduction deduces the
  // template argument to have type 'int*'.
  // This results in a call to the function
  // template specialization
  // 'void sort<int*>(int* first, int* last)'.

  std::sort(data,
            data + sizeof data/sizeof*data);

  std::vector<int, std::allocator<int> >
       container, empty;

  // Name lookup finds the member function
  // template
  // template<class InputIterator>
  // void vector<int,allocator<int> >::assign(
  //   InputIterator first, InputIterator last);
  //
  // Template argument deduction deduces the
  // template argument to have type 'int*'.
  // This results in a call to the function
  // template specialization
  // 'void vector<int,allocator<int> >::
  //               assign<int*>(int*, int*)'.

  container.assign(data,
             data + sizeof data/sizeof*data);

  // Argument dependent name lookup finds the
  // namespace scope function template
  // template<class T, class Alloc>
  // bool operator!=(const vector<T,Alloc>&,
  //                 const vector<T,Alloc>&);
  //
  // Template argument deduction deduces T to
  // be 'int' and Alloc to be std::allocator.

  if(container != empty)  container.clear();
}

Unlike the contexts requiring template argument deduction that I looked at before, which were all more alike than different in terms of how P's and A's were formed, this case is really distinctive and you will see why shortly. It is also the most frequently used form of template argument deduction, so I will back its description up with more case studies.

The distinction from what I showed earlier is that when deduction starts for a (member) function template: 1) there can be more than one P, 2) the number of A's is always the same as the number of P's. In fact, any function parameter which depends on a template parameter that has not been explicitly specified (see the earlier discussion on function templates and function template specializations) constitutes a P. If all template arguments are explicitly specified, there are no P's and no argument deduction takes place. If the i-th function parameter of a function template qualifies as P (I will call it P_i for the rest of the article), then the i-th argument of the corresponding function call expression is A (which I will call A_i).

Different to the cases I covered before, here every P_i and A_i can undergo a transformation before template argument deduction takes place. Below are the details of how this process goes:

First every A_i is studied and:

After that is done, every P_i is examined and:

For the rest of this section, whenever I mention P_i or A_i, I'll be referring to their transformed versions.

With the information from the previous paragraphs in mind and the example I presented at the beginning of this section, I can now show how P's and A's are formed for the expression container != empty, for which name lookup finds the function template operator!=(const vector<T,Alloc>&, const vector<T,Alloc>&) as a possible candidate. This template has two function parameters, which depend on the template parameters. Both the function parameters are of reference type and are the same and hence the underlying type of the references is used in determining P's - P₁, P₂ are const vector<T, Alloc>. The corresponding A's are also the same - A₁, A₂ are std::vector<int, std::allocator<int> >. Template argument deduction then deduces T to be int and Alloc to be std::allocator, which results in a call to the function template specialization

bool operator!=<int,std::allocator>(
          const vector<int,std::allocator>&,
          const vector<int,std::allocator>&)

The fact that argument deduction makes each P_i identical to the corresponding A_i has a major implication on calling (member) function templates, for it leaves no room for user-defined conversions on A's. Here is an example:

#include <algorithm>
#include <functional>
#include <iostream>

struct example {
  static void foo(int i) {
    std::cout << i << '\n';
  }
  typedef void  fun_t(int);
  operator  fun_t*() const {
    return  foo;
  }
};

int main() {
  int data[] = {3, 0, -1, -3, 16};
  example inst;

  // std::for_each(data,
  //          data + sizeof data/sizeof*data,
  //          std::ptr_fun(inst));
  std::for_each(data,
              data + sizeof data/sizeof*data,
              example::foo);
}

Let's look at the lines that were commented out and the function call expression std::ptr_fun(inst) in particular. What happens there is that name lookup finds the following two function templates in the scope of the namespace std:

template<class Arg, class Res>
pointer_to_unary_function<Arg,Res>
                    ptr_fun(Res(*)(Arg);

template<class Arg1, class Arg2, class Res>
pointer_to_binary_function<Arg1,Arg2,Res>
                    ptr_fun(Res(*)(Arg1,Arg2);

For the first function template there is one P and one A. P₁ is Res(*)(Arg), which, in terms of the conventions used in the table of allowable forms, is a variant of T(*)(T). The corresponding A₁ is the type example. It is obvious enough that there exist no such types for the template parameters Res and Arg that would make P₁ identical to A₁. There is, however, a user-defined conversion from an expression of type example to type void(*)(int). If it was selected (like in the case of nontemplate functions), argument deduction would deduce Res to be void type and Arg to be int. But, as I said before, the language prohibits this and argument deduction fails. Quite similarly, template argument deduction fails for the second function template. This all leaves the set of candidates submitted to overload resolution empty, thus making the construct std::ptr_fun(inst) ill-formed in the context shown above.

Since you can always perform user-defined conversions inside the body of a function template, the restriction of precluding userdefined conversions on A's can be easily circumvented. And a nice example of that can, not surprisingly, be found in the Standard C++ library. Let's take a look at the function object generator bind2nd, here is its possible implementation:

template<class BinOp, class T>
binder2nd<BinOp> bind2nd(const BinOp& op,
                         const T& second) {
  return binder2nd<BinOp>(op, typename
         BinOp::second_argument_type(second));
}

When called, this function template deduces T to be whatever type the second function argument has (except that it will effectively strip the type of the second argument of the possible const qualifier) and then explicitly converts it to the type required. Here is a small program that shows how this works:

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>

struct  example {
  operator int() const {
    return 3;
  }
};

int main() {
  int data[] = {3, 0, -1, -3, 16};
  example inst;
  std::transform(data,
   data + sizeof data/sizeof*data,
   std::ostream_iterator<int>(std::cout, "  "),
   std::bind2nd(std::modulus<int>(), inst));
}

There's also another way in which argument deduction from a function call expression differs from the cases I looked at in the previous sections. It differs in that it allows each P_i to be not identical to the corresponding A_i . The following is allowed:

Of course, providing that it is possible to find such types for the template parameters of P_i that P_i becomes identical to its A_i, these three alternatives are not considered.

The example of the use of the function template bind2nd that I just presented also demonstrates the case where P's are different from its corresponding A's. Indeed, in the function call expression std::bind2nd(std::modulus<int>(),inst) A₁ is the type std::modulus<int> and A₂ is the type example. The corresponding P's are: P₁ is const BinOp, P₂ is const T. And template argument deduction deduces BinOp to be std::modulus<int> and T to be example, which results in a call to the function template specialization:

binder2nd<std::modulus<int> >
      bind2nd(const std::modulus<int>&,
              const example&)

Given the way the deduction of template arguments from a function call expression goes, some familiar techniques can give surprising results. For example, the extensively studied in this article function template bind2nd is written in such a way that it does not allow either of its template parameters BinOp and T to be deduced to be a const-qualified type. Think about it. The same is true of, for example, the function template make_pair from the standard header utility.

The three cases that I explained in this article are not the only ones when the language uses template argument deduction. The other cases of note are "Deducing template arguments of a conversion function template", "Partial ordering of (member) function templates", "Deducing template arguments for explicit instantiation of a (member) function template", and "Referencing a (member) function template specialization in a friend declaration". Although not covered in this paper, these cases are based on the same principles and I believe that the information given in this article will assist the interested reader in mastering them, should such a need arise. As a starting point I can say that the topics "Deducing template arguments for explicit instantiation of a (member) function template" and "Referencing a (member) function template specialization in a friend declaration" are nearly identical to what I explained in "Deducing Template Arguments for Explicit Specialization of a (member) Function Template."

In any case, I'm now working on a follow-up to this article wherein I plan to give details of how things stand with respect to "Deducing template arguments of a conversion function template" and "Partial ordering of function templates."

I welcome any feedback from readers, which you can send directly to me at the address below.