Nested class as a template parameter

Question

I try to write a custom STL-style container. For the sake of simplicity, let's say it's a list. I looked up the standard way to define such a container:

template <typename T, typename A = std::allocator<T> > class mylist;

Now, I want to manage the nodes of the list using a nested class:

(inside mylist)
class node {
    T data;
    node *next;
}

It is my understanding that I need not put a template specifier in front of the definition of node as the compiler will instantiate separate classes mylist<T,A>::node for each combination of mylist's template parameters.

However, now I need to allocate memory not only for the data of type T itself, but also for their wrapper node. Thus, I would like the default template parameter to be of type std::allocator<mylist<T>::node>. At that point, though, mylist has not yet been declared and the compiler is understandably upset:

error: `mylist' was not declared in this scope

How would one resolve this conundrum? There are two constraints:

• Normally, I would declare the missing class without fully declaring its contents. However, since it is nested inside the very thing I want to declare, this is not an option.
• I need node to be nested as it needs to access the allocator instance of mylist. E.g., I have operator= declared on node where a lot of memory management happens recursively. This might be overkill for a list and you could do that from within mylist, thereby dropping the parametric dependence of node on A, but it is crucial for the data structure I'm implementing.

Answer 1

It doesn't matter what the default allocator's type argument is, just the actual type. You can use rebind_alloc from std::allocator_traits:

Alloc::rebind<T>::other if present, otherwise Alloc<T, Args> if this Alloc is Alloc<U, Args>

to get what you need:

template <typename T, typename A = std::allocator<T> >
class mylist {
    class node { ... };

    using NodeAlloc = typename std::allocator_traits<A>::template rebind_alloc<node>;
};

And then use NodeAlloc to get your nodes. In this way, if the user doesn't specify an allocator, you would get the default std::allocator<T> and then use std::allocator<node>. This is precisely what you want, without having to expose node.

Answer 2

I need node to be nested as it needs to access the allocator instance of mylist

Don't be so sure. They can be friends:

template <typename, class> class list;

template <typename T>
struct node {
    // ...
};

template <typename T, class Alloc=std::allocator<T> >
class list {
    friend node<T>;
    // ...
};

If you don't want node to be accessible outside of your file, just omit it in your header file (.h / .hpp).