Another curiously recurring template pattern.

Question

template <class Data, class Allocator = std::allocator<Node> >
class Node : public Data {
  // ...
};

The question is simple, how to make the above code compile? The intention is to give Node a possibility to allocate other Nodes (and to provide a default allocator).

Answer 1

You can't write it like that:

template <class Data, class Allocator>
class Node;

template <class Data, class Allocator = 
  std::allocator<Node<Data, std::allocator<Node<...> >
class Node : public Data {
  // ...
};

Because the default argument will have to repeat itself. You can use a tag-type, though

struct DefaultAllocatorTag { };

template<typename Alloc, typename Node>
struct SelectAllocator {
  typedef Alloc type;
};

template<typename Node>
struct SelectAllocator<DefaultAllocatorTag, Node> {
  typedef std::allocator<Node> type;
};

template <class Data, class Allocator = DefaultAllocatorTag >
class Node : public Data {
  typedef typename SelectAllocator<Allocator, Node>::type 
    NodeAllocator;
};

If it is applicable, i would determine the allocator in the container, though. Like this:

template<typename Data, typename Allocator = std::allocator<Data> >
struct Container {
  struct Node : Data { 
    typedef typename Allocator::template rebind<Node>::other NodeAllocator;
    ...
  };
  ...
};

Answer 2

How about this?:

#include <memory>

template<class Data>
class NodeImpl : public Data
{
};

template<class Data, class Allocator = std::allocator< NodeImpl<Data> > >
class Node : public NodeImpl<Data>
{
};

class MyAllocator
{
};

class MyDataClass
{
};

int main()
{
    Node<MyDataClass> node;

    Node<MyDataClass, MyAllocator> node_with_alloc;

    return 0;
}

Answer 3

Finally I solved it! The solution is to delay specialization of the default allocator until inside of the class where Node is already defined:

template <class Data, template<class T> class TAllocator = std::allocator >
class Node : public Data {
  typedef TAllocator<Node> Allocator;
  // ...
};

Answer 4

Another solution. This one seems to be more typical. Ie. vector and smart pointer implementations are using something similar. The idea is to privately inherit from the allocator:

template <class Data, template <class N> class Allocator = std::allocator>
class Node : public Data, private Allocator<Node<Data, Allocator> > {
  // ...
};

The bonus is that in inheritance declaration we can already use Node.