如何初始化模板类的哨兵节点的值？

Question

在

Node

容器中提供

Tree

：

#include <iostream>

template <class T>
class Tree {
    struct Node {
        Node(T val) : left(new Node()), right(new Node()), val(val) { /* value node */ }
        Node() : left(nullptr), right(nullptr) { /* sentinal node */ }
        Node *left, *right;
        T val;
    };

public:
    T insert(T val) {
        Node node(val);
        return node.val;
    }
};

int main() {
    Tree<int> tree;
    std::cout << tree.insert(42);
}

当我使用

new Node()

创建哨兵节点时，它会使用默认构造函数

val

初始化

T()

成员。但是，

T

，可能没有默认构造函数。

如何在不调用

T

默认构造函数的情况下创建哨兵节点？

Answer 1

为了防止值类型被初始化，可以将类型

T

替换为对齐存储。为了简单起见，它利用了标准类型特征，

std::aligned_storage

。这样，只能显式地构造对象。

template <typename T>
struct Node
{
  std::aligned_storage_t<sizeof(T), alignof(T)>  storage;
  Node*  left;
  Node*  right;
};

但是，这种设计有一个副作用：节点的构造操作需要操作对齐存储的位以允许构造值对象。这增加了实现的复杂性，并且需要引入其他组件（标准组件或从头开始创建的组件）来处理位操作。

另一种方法是保留原始值类型，但默认使用假构造函数对其进行初始化。 MSVC 库使用此技术来实现所有基于节点的容器。

template <typename T>
struct Node
{
  T      value = fake_constructor<T>();
  Node*  left;
  Node*  right;
};

虽然这种设计看似有效，但上述两种方法都有一个重要的副作用：哨兵节点占用的空间不受指针数量的限制，指针是允许与其他节点链接所需的唯一成员属性，但与类型

T

大小成正比。这意味着，如果用户指定一个尺寸特别大的值类型，哨兵节点将需要大量的空间来实例化，导致容器对象消耗与全节点相同的内存量，即使序列完全是空的。而且，如果直接在容器对象中实例化哨兵节点，内存占用可能会变成。

解决这个问题的唯一方法就是将节点接口分为两个类，一个是仅包含指针的

NodeBase

类，另一个是继承于前者并引入value属性的

Node

类。因此，哨兵节点是基类的实例，可以嵌入到容器中或在构造时动态分配，而所有其他节点都是派生类的实例。

struct NodeBase
{
  NodeBase*  left;
  NodeBase*  right;
};

template <typename T>
struct Node
 : public NodeBase
{
  T  value;
};

这为哨兵节点节省了大量空间，并且不需要解决方法来阻止值类型的初始化。唯一的困难是需要将

NodeBase*

指针转换为

Node<T>*

指针，反之亦然。由于第一种类型转换是隐式的，因此只有第二种情况需要由实现来处理。