Когда необходимо использовать ключевое слово "typename"?

Краткий ответ: При обращении к вложенному имени, которое является зависимым именем, т.е. вложенным внутрь экземпляра шаблона с неизвестным параметром.

Длинный ответ: В языке Си++ существует три уровня сущностей: значения, типы и шаблоны. Все они могут иметь имена, и само по себе имя не говорит о том, к какому уровню сущностей оно относится. Скорее, информация о природе сущности имени должна быть выведена из контекста.

В тех случаях, когда такой вывод невозможен, его приходится уточнять:

template  struct Magic; // defined somewhere else

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

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

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

Здесь имена Magic::gnarl, Magic::brugh и Magic::kwpq пришлось эксплицировать, поскольку сказать об этом невозможно: Поскольку Magic является шаблоном, то сама природа типа Magic зависит от T - могут существовать специализации, совершенно отличные от первичного шаблона, например.

Что делает Magic::gnarl зависимым именем, так это тот факт, что мы находимся внутри определения шаблона, где T неизвестно. Если бы мы использовали Magic, все было бы иначе, поскольку компилятор знает (обещаем!) полное определение Magic.

(Если вы хотите проверить это самостоятельно, то вот пример определения Magic, который вы можете использовать. Извините за использование constexpr в специализации для краткости; если у вас старый компилятор, смело меняйте объявление статической константы-члена на старую форму, характерную для версии до С++11).

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

Использование:

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

  return Magic::kwpq(2, 3);  // no disambiguation here!
}

Ключевое слово typename необходимо, поскольку iterator является зависимым типом от P. Компилятор не может понять, относится ли iterator к значению или к типу, поэтому он считает, что это значение, пока вы не скажете typename. Он необходим в тех случаях, когда тип зависит от аргумента шаблона, в контексте, когда допустимы либо типы, либо значения. Например, в качестве базовых классов typename не нужен, поскольку базовый класс должен быть типом.

По этому же поводу существует ключевое слово template, которое используется для того, чтобы сообщить компилятору, что некоторое зависимое имя является шаблонной функцией, а не значением.

Ключевое слово typename необходимо в тех случаях, когда имя типа зависит от параметра шаблона (чтобы компилятор мог 'знать' семантику идентификатора (тип или значение), не имея при первом проходе полной таблицы символов).

Не в том же значении и несколько реже ключевое слово lone typename может быть полезно при использовании общих параметров шаблона: http://ideone.com/amImX.

#include 
#include 
#include 

template 
struct ContainerTests 
{
    typedef Container IntContainer;
    typedef Container StringContainer;
    //
    void DoTests()
    {
        IntContainer ints;
        StringContainer strings;
        // ... etc
    }
};

int main()
{
    ContainerTests t1;
    ContainerTests   t2;

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