Циркулярная зависимость класса шаблонов C++

Question

В свободное время (в качестве учебного упражнения) я работал над созданием шаблонов и распределителей на языке C++, аналогичных тем, которые были предоставлены как часть стандартной библиотеки шаблонов.

Пока что контейнеры, которые я изготовил, представляют собой единый связанный список, двойной связанный список, стек и очередь. Стек и Очередь используют единый связанный список как свою внутреннюю структуру, так как я храню указатели на голове и хвосте.

Теперь наступает мой первый класс распределителя, пул-распределитель. Внутри он использует один из моих объектов Stack для получения и освобождения предварительно выделенных объектов. Теперь я хотел бы использовать этот Pool Allocator в сочетании с моим Singlely Linked List и Doubly Linked List, чтобы предварительно выделить внутренние объекты Node, которые хранят данные. Мне кажется, что теперь это создает проблему круговой зависимости в моем проекте.

Мой обычный метод решения проблем зависимостей, подобных этому в не-шаблонных классах, обычно включает в себя форвардные объявления, указатели и разделение реализации в файл cpp. Проблема, похоже, возникает из-за того, что я не могу разделить объявления и реализации кода шаблона в свои файлы .h и .cpp.

Некоторый код для дальнейшего использования:

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 
    } 
}; 

Я бит неуверен в лучшем пути к solv e этот вопрос. Единственный способ, которым я могу думать, это сделать, чтобы Pool Allocator не использовал ни один из моих классов контейнеров. Я полагаю, что я мог бы создать внутренний связанный класс списка, который является исключительным для класса распределителя, но это похоже на ненужное дублирование кода.

Если у кого-то есть понимание, я был бы очень рад это услышать. Надеюсь, я достаточно тщательно рассмотрел и предоставил приемлемый пример кода. Если есть какая-либо недостающая информация, пожалуйста, дайте мне знать. Заранее спасибо.

Answer 1

Если я вас правильно понимаю, у вас есть две проблемы:

1. Вы эффективно рассказывающие компилятор, что связанный список содержит бассейн аллокатора и бассейн Распределитель содержит стек (который содержит связанный список), поэтому создание экземпляра любого из этих объектов подсказывает компилятору выделить бесконечно-рекурсивный набор объектов.

2. Поскольку ваш список выделяется из распределителя пулов, а распределитель пулов выделяет из списка, ничто фактически не выделяет узлы из свободного хранилища (например, операторы new и delete).

Круговые зависимости - это плохая логика. Вам нужно разбить одну из зависимостей. Поскольку зависимости связанных списков от вашего распределителя пулов по дизайну, вам нужно разбить другую зависимость: тот факт, что распределитель пулов содержит связанный список (в элементе данных стека), который содержит распределитель пула. Последняя часть - это корень вашей проблемы.

Один из способов сделать это, чтобы распределитель напечатал параметр шаблона ваших классов контейнеров, а затем создайте специальный класс распределителя только для внутреннего стека распределителя пула. Таким образом, вы должны были бы эти типы:

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; } 

    }; 

Это может быть хорошей идеей, чтобы дать классы список, состоящий из конструктора, который даст пользователю из списка опцию для инициализации его элемент данных распределителя (по стоимости).

Вы также можете предоставить стек конструктору, который по той же причине возьмет и передаст экземпляр распределителя его внутреннему конструктору списка.