C++ Template Class Circular Dependency

Question

During my spare time (as a learning exercise) I've been working on creating some templated containers and allocators in C++, similar to the ones provided as part of the Standard Template Library.

So far the containers I've made are Singly Linked List, Doubly Linked List, Stack, and Queue. The Stack and Queue both use the Singly Linked List as their internal structure, since I store both the head and tail pointers.

Now comes my first allocator class, the Pool Allocator. Internally it uses one of my Stack objects to Acquire and Release the pre-allocated objects. I would now like to use this Pool Allocator in conjuction with my Singly Linked List and Doubly Linked List in order to pre-allocate the internal Node objects which store the data. It seems to me like this now creates a circular dependency issue in my project.

My normal method of solving dependency issues like this on non-templated classes usually involves forward declarations, pointers, and splitting implementation into a cpp file. The problem seems to arise because I can't split template code declarations and implementations into their respective .h and .cpp files.

Some code for further reference:

SinglyLinkedList.h:

#include "PoolAllocator.h" //Adding this line creates a compile error

template<typename T> class SinglyLinkedList
{
private:
     Node<T> *_Head, *_Tail;
public:
     void PushFront( T *obj )
     {
          //Allocate new node object and set it as _Head
     }

     void PushBack( T *obj )
     {
          //Allocate new node object and set it as _Tail
     }

     T *PopFront()
     {
          //Remove _Head and return node data
     }
};

Stack.h:

#include "SinglyLinkedList.h"

template<typename T> class Stack
{
private:
     SinglyLinkedList<T> _List;
public:
     void Push( T *obj )
     {
          _List.PushFront( obj );
     }

     T *Pop ()
     {
          return _List.PopFront();
     }
};

PoolAllocator.h:

#include "Stack.h"

template<typename T> class PoolAllocator
{
private:
     Stack<T> _Pool;
public:
     void Initialize( unsigned int capacity )
     {
          //Dynamically allocate a bunch of T and push them onto _Pool
     }

     T *Acquire()
     {
          //Remove an item from _Pool and return it
     }

     void Release( T *obj )
     {
          //Push the object back onto the _Pool
     }

     void Dispose()
     {
          //Free all memory from _Pool
     }
};

I am a bit unsure on the best way to solve this issue. The only way I can think of would be to make the Pool Allocator not use any of my container classes. I suppose I could make an internal linked list class that is exclusive to the allocator class, but that seems like unnecessary code duplication.

If anyone has any insight on this I would be very glad to hear it. I hope I covered everything thoroughly enough and provided an acceptable code example. If there is any missing information please let me know. Thanks in advance.

Answer 1

If I understand you correctly, you have two problems:

1. You are effectively telling the compiler that a linked list contains a pool allocator, and a pool allocator contains a stack (which contains a linked list), so instantiating any one of those objects would be telling the compiler to allocate an infinitely-recursive set of objects.

2. Since your list allocates from your pool allocator and your pool allocator allocates from a list, nothing actually allocates nodes from the free store (e.g. operators new and delete).

Circular dependencies are bad logic. You need to break one of the dependencies. Since the linked lists' dependencies on your pool allocator is by design, you need to break the other dependency: the fact that pool allocator contains a linked list (in the stack data member) that contains a pool allocator. That last part is the root of your problem.

One way to do this is to make the allocator type a template parameter of your container classes, and then make a special allocator class just for the pool allocator's internal stack. So you'd have these types:

template <typename T>

  class Node { /* ... */ };


template <typename T, class A = PoolAllocator <T>>

  class SinglyLinkedList {

    A _Allocator;

    Node <T> * _Head;
    Node <T> * _Tail;

    /* ... */

  };


template <typename T, class A = PoolAllocator <T>>

  class DoublyLinkedList {

    A _Allocator;

    Node <T> * _Head;
    Node <T> * _Tail;

    /* ... */

  };


template <typename T, class A = PoolAllocator <T>>    

  class Stack {

    SinglyLinkedList <T, A> _List;

    /* ... */

  };


template <typename T>

  class PoolAllocator <T> {

    Stack <T, FreeStoreAllocator <T>> _Pool;

    /* ... */

  };


template <typename T>

  class FreeStoreAllocator {

    public:

    Node <T> * AllocateNode () const { return new Node <T>; }

    void DeallocateNode (Node <T> * p) const { delete p; }

  };

It might be a good idea to give the list classes a constructor that will give the user of the list the option to initialize its allocator data member (by value).

You could also give the stack a constructor that will take and pass an instance of the allocator to its internal list's constructor, for the same reason.