How do nested templates get resolved in C++?

Question

I recently asked a question about determining whether an iterator points to a complex value at compile time and received an answer that works.

The question is here: How can I specialize an algorithm for iterators that point to complex values?

And the solution was a set of templates that determine whether one template is a specialization of another:

template <class T, template <class...> class Template>
struct is_specialization : std::false_type {};

template <template <class...> class Template, class... Args>
struct is_specialization<Template<Args...>, Template> : std::true_type {};

This does work, but I am really struggling to understand how this works. Particularly the nested template within a template is confusing to me. I'm also still fairly new to using variadic templates and it seems odd to have a variadic template with no type provided, for example: <class...> instead of something like this <class... Args>.

Can someone please break down this template and describe how it gets resolved?

Answer 1

You have to take in count that there are three types of template parameters:

1) types

2) non-types (or values)

3) template-templates

The first type is preceded by typename (or class)

template <typename T>
void foo (T const & t);

In the preceding example, T is a type and t (a classical function argument) is a value of type T.

The second type of template parameter are values and are preceded by the type of the value (or auto, starting from C++17, for a not specified type)

template <int I>
void bar ()
 { std::cout << I << std::endl; }

In the preceding example the I template parameter is a value of type int.

The third type is the most complex to explain.

Do you know (I suppose) that std::vector<int> and std::vector<double> are different types, but they have in common std::vector, a template class.

A template-template parameter is a parameter that accept std::vector, the template class without arguments.

A template-template parameter is preceded by a template keyword, as in the following example

template <template <int> class C>
void baz ();

The template-template parameter C in the preceding example is class (or struct) that require a single int (value) template parameter.

So if you have a class

template <int I>
class getInt
 { };

you can pass getInt, as template parameter, to baz()

baz<getInt>();

Now you should be able to understand your code:

template <class T, template <class...> class Template>
struct is_specialization : std::false_type {};

the is_specialization struct is a template struct that receive, as template parameters, a type (T) and a template-template Template that accept classes/structs receiving a variadic number of type template parameters.

Now you have a specialization of is_specialization:

template <template <class...> class Template, class... Args>
struct is_specialization<Template<Args...>, Template> : std::true_type {};

This specialization is selected when the first template parameter (Template<Args...>) is a class based on the second (Template).

An example: if you instantiate

is_specialization<std::vector<int>, std::map>

the main version (that inherit from std::false_type) is selected because std::vector<int> isn't based on std::map.

But if you instantiate

is_specialization<std::vector<int>, std::vector>

the specialization (that inherit from std::true_type) is selected because std::vector<int> is based on std::vector.

Answer 2

This is a answer based on what caused "click" in my head when it comes to this, I am sure max66 answer is much more useful if you can follow it. If like me even after reading about this you are still strugling here is my attempt to explain this.

Do not read the first lines of templates

So this:

template <class T, template <class...> class Template>
struct is_specialization : std::false_type {};

template <template <class...> class Template, class... Args>
struct is_specialization<Template<Args...>, Template> : std::true_type {};

becomes this:

struct is_specialization : std::false_type {};

struct is_specialization<Template<Args...>, Template> : std::true_type {};

Now things are bit simpler. We have first general case, and second special case(that is prefered by compiler when he can match the arguments). By match I do not mean anything fancy, almost literal text matching.

So for example if we do

is_specialization<std::vector<double>, std::set>

Now compiler will try to match special case. You can imagine it literally replacing the Template with std::vector (if he is matching on the first argument first), and then fail since he now expects Template to mean std::vector and in the second argument it is std::set. He also replaced Args... with double but that is not so important since that is not the cause of mismatch.

Similarly compiler could have first tried to match second argument and conclude that Template must be std::set, and then he fails since first argument is not std::set<Args...>.

I consider the first lines of templates much less important and easier to understand, but for completeness let's go over them.

template <class T, template <class...> class Template>

Just means that this is a template whose second arg is template template argument, this is needed so you can pass something like std::set as second argument(note that normally this will not work, you would need to pass std::set of some type, e.g. std::set<float>).

The ugliest part is the first line of second template:

template <template <class...> class Template, class... Args>

Here again if we remember what we do in specialization code makes sense. We have template template argument Template, and Args are needed just because we want to use template template argument as normal template argument(as first arg(Template<Args...>)).

tl;dr

Ignore first lines of template, pattern match.

Disclaimer: Like I said this is just my way of explaining this code to myself, I know that standard people would cry reading phrases like "first line" or "pattern match".