what does (template) rebind<> do?

The _Alloc template is used to obtain objects of some type. The container may have an internal need to allocate objects of a different type. For example, when you have a std::list<T, A>, the allocator A is meant to allocate objects of type T but the std::list<T, A> actually needs to allocate objects of some node type. Calling the node type _Ty, the std::list<T, A> needs to get hold of an allocator for _Ty objects which is using the allocation mechanism provided by A. Using

typename _A::template rebind<_Ty>::other

specifies the corresponding type. Now, there are a few syntactic annoyances in this declaration:

  1. Since rebind is a member template of _A and _A is a template argument, the rebind becomes a dependent name. To indicate that a dependent name is a template, it needs to be prefixed by template. Without the template keyword the < would be considered to be the less-than operator.
  2. The name other also depends on a template argument, i.e., it is also a dependent name. To indicate that a dependent name is a type, the typename keyword is needed.

rebind is for allocating memory for a type that differs from the element type of the container being implemented. Take from this MSDN article:

For example, given an allocator object al of type A, you can allocate an object of type _Other with the expression:

A::rebind<Other>::other(al).allocate(1, (Other *)0)

Or, you can name its pointer type by writing the type:

A::rebind<Other>::other::pointer

Example in the code of stdc++ : /usr/include/4.8/ext/new_allocator.h

rebind is defined as a structure member of the allocator class; this structure defines a member other that is defined as an instance of the allocator specialized for a different argument type (the other member defines an allocator class that can creates a different type of objects)

 template<typename _Tp>
    class new_allocator
    {
    public:
      ...
      template<typename _Tp1>
        struct rebind
        { typedef new_allocator<_Tp1> other; };

When it is used:

  typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;

the type of the allocator is referenced as

  typename _Alloc::template rebind<_Tp>::other 

Now the typedef is used to define _Tp_alloc_type - which can then be used as a shorter name for the same thing.

An example usage is in std::list where the internal list node also needs its allocator, which is redefined from the argument allocator.