A question about C++ template syntax (STL library source code)

Question

I am reading STL source code right now. Though I understand the meat in what I am reading in stl_list.h, I want to fully understand the following snippet (mainly related to the template syntax, I think).

template

class _List_base {
  ...
  typedef typename _Alloc::template rebind<_List_node<_Tp> >::other _Node_Alloc_type; //(1).

  ...
  typedef _Alloc allocator_type;
  get_allocator() const
  { return allocator_type(*static_cast<
                          const _Node_Alloc_type*>(&this->_M_impl)); }  // (2)
  ...
};

Can someone explain why we need a "template" following _Alloc in line (1)? (and giving a full explanation of this line?)

Can someone explain why we can cast _Node_Alloc_type to _Alloc in line (2)?

Answer 1

The template keyword is needed to identify the name rebind as a class template. Without it, rebind could be considered a variable or a constant (in this case a type due to the typename keyword) and the following < could be interpreted as a less-than operator.

This is somewhat similar to the typename keyword (which is of course necessary to identify other as a type).

Every allocator is required to provide a meta-function (i.e. a class template) called rebind that returns the same allocator but for a different type. In other words,

Alloc<T>::rebind<U>::other

names the same type as

Alloc<U>

The second part of your question is difficult to answer without more context. What is the type of _M_impl? How is that type defined?

Answer 2

It looks like the gcc implementation of std::list. In that case, the context is:

struct _List_impl : public _Node_Alloc_type { ... };
_List_impl _M_impl;

And you forgot to write the return type of the member function:

typedef _Alloc allocator_type;
allocator_type
get_allocator() const
{ return allocator_type(*static_cast<const _Node_Alloc_type*>(&this->_M_impl)); }

---

Answer for (1)

When adding a node in a list of type _Tp, what really needs to be allocated is not an object _Tp but a list node containing _Tp (a _List_node<_Tp>).

So the std::list needs to be able allocate a _List_node<_Tp> but it has been provided an allocator for _Tp. This is where the template typedef rebind comes in handy: it makes it possible to get an allocator for type U from an allocator for type T.

Using this rebind, we get an _Alloc<_List_node<_Tp> > from the type _Alloc<_Tp>.

---

Answer for (2) in the source file as comment:

// NOTA BENE
// The stored instance is not actually of "allocator_type"'s
// type.  Instead we rebind the type to
// Allocator<List_node<Tp>>, which according to [20.1.5]/4
// should probably be the same.  List_node<Tp> is not the same
// size as Tp (it's two pointers larger), and specializations on
// Tp may go unused because List_node<Tp> is being bound
// instead.
//
// We put this to the test in the constructors and in
// get_allocator, where we use conversions between
// allocator_type and _Node_Alloc_type. The conversion is
// required by table 32 in [20.1.5].

It is assumed that _Alloc's type is the same as _Node_Alloc_type as per the C++ Standard; hence the static_cast asserts the conversion is legal.