[c++] Where and why do I have to put the "template" and "typename" keywords?

In templates, where and why do I have to put typename and template on dependent names?
What exactly are dependent names anyway?

I have the following code:

template <typename T, typename Tail> // Tail will be a UnionNode too.
struct UnionNode : public Tail {
    // ...
    template<typename U> struct inUnion {
        // Q: where to add typename/template here?
        typedef Tail::inUnion<U> dummy; 
    };
    template< > struct inUnion<T> {
    };
};
template <typename T> // For the last node Tn.
struct UnionNode<T, void> {
    // ...
    template<typename U> struct inUnion {
        char fail[ -2 + (sizeof(U)%2) ]; // Cannot be instantiated for any U
    };
    template< > struct inUnion<T> {
    };
};

The problem I have is in the typedef Tail::inUnion<U> dummy line. I'm fairly certain that inUnion is a dependent name, and VC++ is quite right in choking on it.
I also know that I should be able to add template somewhere to tell the compiler that inUnion is a template-id. But where exactly? And should it then assume that inUnion is a class template, i.e. inUnion<U> names a type and not a function?

C++11

Problem

While the rules in C++03 about when you need typename and template are largely reasonable, there is one annoying disadvantage of its formulation

template<typename T>
struct A {
  typedef int result_type;

  void f() {
    // error, "this" is dependent, "template" keyword needed
    this->g<float>();

    // OK
    g<float>();

    // error, "A<T>" is dependent, "typename" keyword needed
    A<T>::result_type n1;

    // OK
    result_type n2; 
  }

  template<typename U>
  void g();
};

As can be seen, we need the disambiguation keyword even if the compiler could perfectly figure out itself that A::result_type can only be int (and is hence a type), and this->g can only be the member template g declared later (even if A is explicitly specialized somewhere, that would not affect the code within that template, so its meaning cannot be affected by a later specialization of A!).

Current instantiation

To improve the situation, in C++11 the language tracks when a type refers to the enclosing template. To know that, the type must have been formed by using a certain form of name, which is its own name (in the above, A, A<T>, ::A<T>). A type referenced by such a name is known to be the current instantiation. There may be multiple types that are all the current instantiation if the type from which the name is formed is a member/nested class (then, A::NestedClass and A are both current instantiations).

Based on this notion, the language says that CurrentInstantiation::Foo, Foo and CurrentInstantiationTyped->Foo (such as A *a = this; a->Foo) are all member of the current instantiation if they are found to be members of a class that is the current instantiation or one of its non-dependent base classes (by just doing the name lookup immediately).

The keywords typename and template are now not required anymore if the qualifier is a member of the current instantiation. A keypoint here to remember is that A<T> is still a type-dependent name (after all T is also type dependent). But A<T>::result_type is known to be a type - the compiler will "magically" look into this kind of dependent types to figure this out.

struct B {
  typedef int result_type;
};

template<typename T>
struct C { }; // could be specialized!

template<typename T>
struct D : B, C<T> {
  void f() {
    // OK, member of current instantiation!
    // A::result_type is not dependent: int
    D::result_type r1;

    // error, not a member of the current instantiation
    D::questionable_type r2;

    // OK for now - relying on C<T> to provide it
    // But not a member of the current instantiation
    typename D::questionable_type r3;        
  }
};

That's impressive, but can we do better? The language even goes further and requires that an implementation again looks up D::result_type when instantiating D::f (even if it found its meaning already at definition time). When now the lookup result differs or results in ambiguity, the program is ill-formed and a diagnostic must be given. Imagine what happens if we defined C like this

template<>
struct C<int> {
  typedef bool result_type;
  typedef int questionable_type;
};

A compiler is required to catch the error when instantiating D<int>::f. So you get the best of the two worlds: "Delayed" lookup protecting you if you could get in trouble with dependent base classes, and also "Immediate" lookup that frees you from typename and template.

Unknown specializations

In the code of D, the name typename D::questionable_type is not a member of the current instantiation. Instead the language marks it as a member of an unknown specialization. In particular, this is always the case when you are doing DependentTypeName::Foo or DependentTypedName->Foo and either the dependent type is not the current instantiation (in which case the compiler can give up and say "we will look later what Foo is) or it is the current instantiation and the name was not found in it or its non-dependent base classes and there are also dependent base classes.

Imagine what happens if we had a member function h within the above defined A class template

void h() {
  typename A<T>::questionable_type x;
}

In C++03, the language allowed to catch this error because there could never be a valid way to instantiate A<T>::h (whatever argument you give to T). In C++11, the language now has a further check to give more reason for compilers to implement this rule. Since A has no dependent base classes, and A declares no member questionable_type, the name A<T>::questionable_type is neither a member of the current instantiation nor a member of an unknown specialization. In that case, there should be no way that that code could validly compile at instantiation time, so the language forbids a name where the qualifier is the current instantiation to be neither a member of an unknown specialization nor a member of the current instantiation (however, this violation is still not required to be diagnosed).

Examples and trivia

You can try this knowledge on this answer and see whether the above definitions make sense for you on a real-world example (they are repeated slightly less detailed in that answer).

The C++11 rules make the following valid C++03 code ill-formed (which was not intended by the C++ committee, but will probably not be fixed)

struct B { void f(); };
struct A : virtual B { void f(); };

template<typename T>
struct C : virtual B, T {
  void g() { this->f(); }
};

int main() { 
  C<A> c; c.g(); 
}

This valid C++03 code would bind this->f to A::f at instantiation time and everything is fine. C++11 however immediately binds it to B::f and requires a double-check when instantiating, checking whether the lookup still matches. However when instantiating C<A>::g, the Dominance Rule applies and lookup will find A::f instead.

I am placing JLBorges's excellent response to a similar question verbatim from cplusplus.com, as it is the most succinct explanation I've read on the subject.

In a template that we write, there are two kinds of names that could be used - dependant names and non- dependant names. A dependant name is a name that depends on a template parameter; a non-dependant name has the same meaning irrespective of what the template parameters are.

For example:

template< typename T > void foo( T& x, std::string str, int count )
{
    // these names are looked up during the second phase
    // when foo is instantiated and the type T is known
    x.size(); // dependant name (non-type)
    T::instance_count ; // dependant name (non-type)
    typename T::iterator i ; // dependant name (type)
      
    // during the first phase, 
    // T::instance_count is treated as a non-type (this is the default)
    // the typename keyword specifies that T::iterator is to be treated as a type.

    // these names are looked up during the first phase
    std::string::size_type s ; // non-dependant name (type)
    std::string::npos ; // non-dependant name (non-type)
    str.empty() ; // non-dependant name (non-type)
    count ; // non-dependant name (non-type)
}

What a dependant name refers to could be something different for each different instantiation of the template. As a consequence, C++ templates are subject to "two-phase name lookup". When a template is initially parsed (before any instantiation takes place) the compiler looks up the non-dependent names. When a particular instantiation of the template takes place, the template parameters are known by then, and the compiler looks up dependent names.

During the first phase, the parser needs to know if a dependant name is the name of a type or the name of a non-type. By default, a dependant name is assumed to be the name of a non-type. The typename keyword before a dependant name specifies that it is the name of a type.

Summary

Use the keyword typename only in template declarations and definitions provided you have a qualified name that refers to a type and depends on a template parameter.

Preface

This post is meant to be an easy-to-read alternative to litb's post.

The underlying purpose is the same; an explanation to "When?" and "Why?" typename and template must be applied.

What's the purpose of typename and template?

typename and template are usable in circumstances other than when declaring a template.

There are certain contexts in C++ where the compiler must explicitly be told how to treat a name, and all these contexts have one thing in common; they depend on at least one template-parameter.

We refer to such names, where there can be an ambiguity in interpretation, as; "dependent names".

This post will offer an explanation to the relationship between dependent-names, and the two keywords.

A snippet says more than 1000 words

Try to explain what is going on in the following function-template, either to yourself, a friend, or perhaps your cat; what is happening in the statement marked (A)?

template<class T> void f_tmpl () { T::foo * x; /* <-- (A) */ }

It might not be as easy as one thinks, more specifically the result of evaluating (A) heavily depends on the definition of the type passed as template-parameter T.

Different Ts can drastically change the semantics involved.

struct X { typedef int       foo;       }; /* (C) --> */ f_tmpl<X> ();
struct Y { static  int const foo = 123; }; /* (D) --> */ f_tmpl<Y> ();

The two different scenarios:

• If we instantiate the function-template with type X, as in (C), we will have a declaration of a pointer-to int named x, but;

• if we instantiate the template with type Y, as in (D), (A) would instead consist of an expression that calculates the product of 123 multiplied with some already declared variable x.

The Rationale

The C++ Standard cares about our safety and well-being, at least in this case.

To prevent an implementation from potentially suffering from nasty surprises, the Standard mandates that we sort out the ambiguity of a dependent-name by explicitly stating the intent anywhere we'd like to treat the name as either a type-name, or a template-id.

If nothing is stated, the dependent-name will be considered to be either a variable, or a function.

How to handle dependent names?

If this was a Hollywood film, dependent-names would be the disease that spreads through body contact, instantly affects its host to make it confused. Confusion that could, possibly, lead to an ill-formed perso-, erhm.. program.

A dependent-name is any name that directly, or indirectly, depends on a template-parameter.

template<class T> void g_tmpl () {
   SomeTrait<T>::type                   foo; // (E), ill-formed
   SomeTrait<T>::NestedTrait<int>::type bar; // (F), ill-formed
   foo.data<int> ();                         // (G), ill-formed    
}

We have four dependent names in the above snippet:

• E)
  • "type" depends on the instantiation of SomeTrait<T>, which include T, and;
• F)
  • "NestedTrait", which is a template-id, depends on SomeTrait<T>, and;
  • "type" at the end of (F) depends on NestedTrait, which depends on SomeTrait<T>, and;
• G)
  • "data", which looks like a member-function template, is indirectly a dependent-name since the type of foo depends on the instantiation of SomeTrait<T>.

Neither of statement (E), (F) or (G) is valid if the compiler would interpret the dependent-names as variables/functions (which as stated earlier is what happens if we don't explicitly say otherwise).

The solution

To make g_tmpl have a valid definition we must explicitly tell the compiler that we expect a type in (E), a template-id and a type in (F), and a template-id in (G).

template<class T> void g_tmpl () {
   typename SomeTrait<T>::type foo;                            // (G), legal
   typename SomeTrait<T>::template NestedTrait<int>::type bar; // (H), legal
   foo.template data<int> ();                                  // (I), legal
}

Every time a name denotes a type, all names involved must be either type-names or namespaces, with this in mind it's quite easy to see that we apply typename at the beginning of our fully qualified name.

template however, is different in this regard, since there's no way of coming to a conclusion such as; "oh, this is a template, then this other thing must also be a template". This means that we apply template directly in front of any name that we'd like to treat as such.

Can I just stick the keywords in front of any name?

"Can I just stick typename and template in front of any name? I don't want to worry about the context in which they appear..." - Some C++ Developer

The rules in the Standard states that you may apply the keywords as long as you are dealing with a qualified-name (K), but if the name isn't qualified the application is ill-formed (L).

namespace N {
  template<class T>
  struct X { };
}

         N::         X<int> a; // ...  legal
typename N::template X<int> b; // (K), legal
typename template    X<int> c; // (L), ill-formed

^{Note: Applying typename or template in a context where it is not required is not considered good practice; just because you can do something, doesn't mean that you should.}

Additionally there are contexts where typename and template are explicitly disallowed:

• When specifying the bases of which a class inherits

  Every name written in a derived class's base-specifier-list is already treated as a type-name, explicitly specifying typename is both ill-formed, and redundant.

                      // .------- the base-specifier-list
    template<class T> // v
    struct Derived      : typename SomeTrait<T>::type /* <- ill-formed */ {
      ...
    };
  

  
  

• When the template-id is the one being referred to in a derived class's using-directive

    struct Base {
      template<class T>
      struct type { };
    };
  
    struct Derived : Base {
      using Base::template type; // ill-formed
      using Base::type;          // legal
    };
  

typedef typename Tail::inUnion<U> dummy;

However, I'm not sure you're implementation of inUnion is correct. If I understand correctly, this class is not supposed to be instantiated, therefore the "fail" tab will never avtually fails. Maybe it would be better to indicates whether the type is in the union or not with a simple boolean value.

template <typename T, typename TypeList> struct Contains;

template <typename T, typename Head, typename Tail>
struct Contains<T, UnionNode<Head, Tail> >
{
    enum { result = Contains<T, Tail>::result };
};

template <typename T, typename Tail>
struct Contains<T, UnionNode<T, Tail> >
{
    enum { result = true };
};

template <typename T>
struct Contains<T, void>
{
    enum { result = false };
};

PS: Have a look at Boost::Variant

PS2: Have a look at typelists, notably in Andrei Alexandrescu's book: Modern C++ Design

_{This answer is meant to be a rather short and sweet one to answer (part of) the titled question. If you want an answer with more detail that explains why you have to put them there, please go here.}

The general rule for putting the typename keyword is mostly when you're using a template parameter and you want to access a nested typedef or using-alias, for example:

template<typename T>
struct test {
    using type = T; // no typename required
    using underlying_type = typename T::type // typename required
};

Note that this also applies for meta functions or things that take generic template parameters too. However, if the template parameter provided is an explicit type then you don't have to specify typename, for example:

template<typename T>
struct test {
    // typename required
    using type = typename std::conditional<true, const T&, T&&>::type;
    // no typename required
    using integer = std::conditional<true, int, float>::type;
};

The general rules for adding the template qualifier are mostly similar except they typically involve templated member functions (static or otherwise) of a struct/class that is itself templated, for example:

Given this struct and function:

template<typename T>
struct test {
    template<typename U>
    void get() const {
        std::cout << "get\n";
    }
};

template<typename T>
void func(const test<T>& t) {
    t.get<int>(); // error
}

Attempting to access t.get<int>() from inside the function will result in an error:

main.cpp:13:11: error: expected primary-expression before 'int'
     t.get<int>();
           ^
main.cpp:13:11: error: expected ';' before 'int'

Thus in this context you would need the template keyword beforehand and call it like so:

t.template get<int>()

That way the compiler will parse this properly rather than t.get < int.