1

在业余时间（作为学习练习），我一直致力于在 C++ 中创建一些模板化容器和分配器，类似于标准模板库中提供的那些。

到目前为止，我制作的容器是单链表、双链表、堆栈和队列。Stack 和 Queue 都使用单链表作为它们的内部结构，因为我存储了头指针和尾指针。

现在是我的第一个分配器类，池分配器。在内部，它使用我的 Stack 对象之一来获取和释放预分配的对象。我现在想将此池分配器与我的单链表和双链表结合使用，以便预先分配存储数据的内部节点对象。在我看来，现在这样在我的项目中创建了一个循环依赖问题。

我在非模板类上解决此类依赖问题的常规方法通常涉及前向声明、指针和将实现拆分为 cpp 文件。问题似乎出现了，因为我无法将模板代码声明和实现拆分为各自的 .h 和 .cpp 文件。

一些代码供进一步参考：

单链表.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
     }
};

堆栈.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();
     }
};

池分配器.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
     }
};

我有点不确定解决这个问题的最佳方法。我能想到的唯一方法是让池分配器不使用我的任何容器类。我想我可以创建一个分配器类独有的内部链表类，但这似乎是不必要的代码重复。

如果有人对此有任何见解，我将很高兴听到。我希望我足够彻底地涵盖了所有内容并提供了一个可接受的代码示例。如果有任何缺失的信息，请告诉我。提前致谢。

4

1 回答 1

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

  };

为列表类提供一个构造函数可能是一个好主意，该构造函数将为列表的用户提供初始化其分配器数据成员（按值）的选项。

出于同样的原因，您还可以为堆栈提供一个构造函数，该构造函数将获取分配器的实例并将其传递给其内部列表的构造函数。

于 2015-06-18T15:16:42.317 回答