43

trying to learn more about how the standard library is actually implemented I'm inspecting all containers in visual studio.. Here I see some curious structure:

In some base class of a std::list<> The following typedef is found

typedef typename _Alloc::template rebind<_Ty>::other _Alty;

Where "_Alloc" corresponds with the allocator template argument (and _Ty the contained type). I have trouble finding a good explanation of this "keyword". Best thing I've found so far is that it is part of the allocator interface. Though even cppreference isn't very good in explaining this.

What does this template rebind<> do? And why is it necessary at that location?

John Gordon
  • 2,576
  • 3
  • 24
  • 29
paul23
  • 8,799
  • 12
  • 66
  • 149
  • 1
    Related, see [Why is allocator::rebind necessary when we have template template parameters?](http://stackoverflow.com/q/12362363) – jww Aug 13 '16 at 03:07

4 Answers4

50

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.
Dietmar Kühl
  • 150,225
  • 13
  • 225
  • 380
  • Wait, but that would mean that (when the list is `std::list`); `rebind` becomes redundant? as it would convert "T" to "T" type? – paul23 Jan 03 '13 at 23:27
  • @paul23: If `_Ty` is the template argument, rather than something like `typedef _Node<_T> _Ty`, could be useful to make sure that the allocator creates the appropriate types. Although I'm pretty sure that `A` in `std::list` needs to be able to deal with `T` objects, an allocator of a different may be passed in. I'm not sure about the standard requirements. It may be an extension to support allocators for different types. – Dietmar Kühl Jan 03 '13 at 23:38
  • List of T allocates nodes containing T as a member. So the T allocator is useless to it directly. Instead it makes a new one. Your comment does not make sense to me @paul23 – Yakk - Adam Nevraumont Jan 03 '13 at 23:41
  • @Yakk: I think the allocator for type `T` is used to pull out some types defined in the containers, e.g., `std::list::reference`. However, it seems that `std::list >` compiles. If the allocator isn't rebound, the `reference` type in the above list would be `long&` rather than `int&`. – Dietmar Kühl Jan 03 '13 at 23:47
  • The standard requires (in Table 99) that `A::value_type` is the same type as `std::list::value_type` i.e. is the same type as `T`, so it's undefined to instantiate e.g. `std::list>` ... but at least libstdc++ (and maybe other impls) allow it as an extension and rebind the allocator internally. I can't remember why they allow it though! – Jonathan Wakely Jan 04 '13 at 03:05
  • Also `reference` is a bad example ... in C++11 allocators don't need to define `reference` or `const_reference` and even if they do provide them containers are not allowed to use the allocator's typedefs. The point is valid regarding the `pointer` type and `long*` and `int*` though. – Jonathan Wakely Jan 04 '13 at 03:08
  • I came across this question when I was learning about allocators. I would just like to mention for future readers like me that it is better practice to use [allocator_traits](https://en.cppreference.com/w/cpp/memory/allocator_traits) when working with allocators. Especially in C++17 and newer where many members of [allocator](https://en.cppreference.com/w/cpp/memory/allocator) are getting deprecated/removed. Here is a simple linked list that uses rebind through `std::allocator_traits`: https://godbolt.org/z/c4WK3Y – Michal Sep 03 '20 at 20:48
10

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
E_net4
  • 27,810
  • 13
  • 101
  • 139
Foggzie
  • 9,691
  • 1
  • 31
  • 48
6

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.

MichaelMoser
  • 3,172
  • 1
  • 26
  • 26
-1

please check this http://www.cplusplus.com/reference/memory/allocator/

you will see

rebind<...> is actually a member of class allocator which is part of STL without giving source code of the implementation.

as you see, rebind<...> is also a template and it deserve a type to let the allocator class knows what is in my rebind member.

so back to your statement: typedef typename _Alloc::template rebind<_Ty>::other _Alty; if you omitted the template: typedef typename _Alloc::rebind<_Ty>::other _Alty; you can easy understand that rebind is member of _Alloc, but compiler can NOT understand.

Given the nature of rebind being the template, template rebind<_Ty> is needed and is treated as the whole not two parts.

Tony
  • 89
  • 10