Short answer: Whenever referring to a nested name that is a dependent name, i.e. nested inside a template instance with unknown parameter.

Long answer: There are three tiers of entities in C++: values, types, and templates. All of those can have names, and the name alone doesn’t tell you which tier of entity it is. Rather, the information about the nature of a name’s entity must be inferred from the context.

Whenever this inference is impossible, you have to specify it:

template <typename> struct Magic; // defined somewhere else

template <typename T> struct A
{
  static const int value = Magic<T>::gnarl; // assumed "value"

  typedef typename Magic<T>::brugh my_type; // decreed "type"
  //      ^^^^^^^^

  void foo() {
    Magic<T>::template kwpq<T>(1, 'a', .5); // decreed "template"
    //        ^^^^^^^^
  }
};

Here the names Magic<T>::gnarl, Magic<T>::brugh and Magic<T>::kwpq had to be expliciated, because it is impossible to tell: Since Magic is a template, the very nature of the type Magic<T> depends on T — there may be specializations which are entirely different from the primary template, for example.

What makes Magic<T>::gnarl a dependent name is the fact that we’re inside a template definition, where T is unknown. Had we used Magic<int>, this would be different, since the compiler knows (you promise!) the full definition of Magic<int>.

(If you want to test this yourself, here’s a sample definition of Magic that you can use. Pardon the use of constexpr in the specializaation for brevity; if you have an old compiler, feel free to change the static member constant declaration to the old-style pre-C++11 form.)

template <typename T> struct Magic
{
  static const T                    gnarl;
  typedef T &                       brugh;
  template <typename S> static void kwpq(int, char, double) { T x; }
};
template <> struct Magic<signed char>
{
  // note that `gnarl` is absent
  static constexpr long double brugh = 0.25;  // `brugh` is now a value
  template <typename S> static int kwpq(int a, int b) { return a + b; }
};

Usage:

int main()
{
  A<int> a;
  a.foo();

  return Magic<signed char>::kwpq<float>(2, 3);  // no disambiguation here!
}

The typename keyword, is needed because iterator is a dependent type on P. The compiler can’t guess if iterator refers to a value or a type, so it assume its a value unless you yell typename. It’s needed whenever there is a type dependent on a template argument, in a context that either types or values would be valid. For instance, as base classes typename is not needed since a base class must be a type.

On the same subject, there is a template keyword used to let the compiler know that some dependent name is a template function instead of a value.

The typename keyword is needed whenever a type name depends on a template parameter, (so the compiler can ‘know’ the semantics of an identifier (type or value) without having a full symbol table at the first pass).

Not in the same meaning, and a bit less common, the lone typename keyword can also be useful when using generic template parameters: http://ideone.com/amImX

#include <string>
#include <list>
#include <vector>

template <template <typename, typename> class Container,
          template <typename> class Alloc = std::allocator>
struct ContainerTests 
{
    typedef Container<int, Alloc<int> > IntContainer;
    typedef Container<std::string, Alloc<int> > StringContainer;
    //
    void DoTests()
    {
        IntContainer ints;
        StringContainer strings;
        // ... etc
    }
};

int main()
{
    ContainerTests<std::vector> t1;
    ContainerTests<std::list>   t2;

    t1.DoTests();
    t2.DoTests();
}