C++: Understand rebind

You may have seen some esoteric C++ line such as this one:

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

In fact if you have read my previous entry on std::vector internal, you have read this line. Naturally the first question is what this line means?

It defines another _Alloc type (alloc_type) bound by a template parameter _Tp. It behaves just like _Alloc except that it is templatized by _Tp. It's not known at this point exactly what type _Alloc or alloc_type is. _Alloc could be a non-template type; it could be a template class and have 1,2,3...arbitrary number of template parameters. But we know that _Alloc has a inner template class named "rebind" that takes a single template parameter (apart from default template parameters rebind might define).

_Alloc_type{
public:
    template < typename U>
    struct rebind{ 
        typedef some_type < U> other;                       // (a)
        //typedef _Alloc_type < U> other;                   // (b)
        //typedef _Alloc_type < U, T1, T2, T3, T4> other;   // (c)
    };
};

Apart from the theoretical possibilities, the common use of rebind is in conjuncture with a templatized _Alloc_type. Let's rule out case (a) where rebind really has nothing to do with _Alloc_type and becomes a rhetoric exercise. (b) and (c) are equally valid, and currently in STL, we see a pervasive use of case (b).

Let's expand case (b)

template < typename T>
struct _Alloc_type{
    template < typename U>
    struct rebind{
        typedef some_type< U> other;                       // (a)
        //typedef _Alloc_type< U> other;                   // (b)
        //typedef _Alloc_type< U, T1, T2, T3, T4> other;   // (c)
    };
};

Let's also define a client class that will use _Alloc_type

template < typename T, typename U, class _Alloc = _Alloc_type < T> >
struct client{
    typedef typename _Alloc::template rebind< U>::other alloc_type;
};

client< int, int *>::alloc_type allocator;

this client structure converts a int allocator to a int * allocator. Such an exercise may seem in vain given that one can simply write something simpler and equivalent:

_Alloc_type< int *> allocator;

So here is the 2nd question, why would anyone sane want to do something so strange? Let's see the power of such a construct by redo the code structure, such as the way it's used in std::vector:

template < typename T, typename _Alloc>
struct client_base {
    typedef typename _Alloc::template rebind< T>::other alloc_type;
};

template < typename T, typename _Alloc = std::allocator < T> >
struct client : client_base< T, _Alloc> {
};

Here client_base takes a template parameter _Alloc from its derived client class. It is obvious that client_base has no knowedge of the exact type of _Alloc. It does not know if _Alloc will fulfill its need to work with type T. But it knows that _Alloc abide by the contract that _Alloc provides a rebind template to create another _Alloc that will work with any type T. The rebind idiom provides an excellent detour/indirection to create another type that behaves like _Alloc and works on any type T.

To better understand the idea of rebind, let's also expand case (c):

template < typename T, typename T1, typename T2, typename T3, typename T4>
struct custom_allocator {
    template < typename U>
    struct rebind{
        typedef _Alloc_type< U, T1, T2, T3, T4> other;   // (c)
    };
};

template < typename T, typename _Alloc>
struct client_base {
    typedef typename _Alloc::template rebind< T>::other alloc_type;
};

template < typename T, typename T1, typename T2, typename T3, typename T4, typename _Alloc = custom_allocator< T, T1, T2, T3, T4> >
struct client : client_base< T3, _Alloc> {
};

Here client::_Alloc is custom_allocator< T, T1, T2, T3, T4> but client_base::alloc_type is custom_allocator< T3, T1, T2, T3, T4>.

rebind (policy clone) is a powerful idiom to create an indirection for template types to bind together and construct new types on the fly without prior knowledge of a class template, e.g. how many template parameters it requires to instantiate and it puts no limit on the number of template parameters an abiding class template has.

References:

1. Policy Clone
2. Template Typedef, Herb Sutter, GotW #79