C++：为无默认构造函数的类分配哨兵节点的方案（参考MSVC STL）

问题背景 #

你定义了带模板的红黑树节点结构：

template <typename value_type>
struct rb_node {
    rb_node   *left;
    rb_node   *right;
    rb_node   *parent;
    value_type val;
    enum _Node_color { Black, Red } color;
};

但当value_type为无默认构造函数的Test类时，无法直接创建静态哨兵节点：

class Test {
private:
    int v;

public:
    explicit Test(int x) : v(x) {}
    bool operator<(const Test & t) const noexcept { return t.V() > v; }
    int V() const noexcept { return v; }
};

// 编译错误：Test无默认构造函数，无法初始化val成员
static const rb_node<Test> sentinel_node;

不修改Test类的通用解决方案 #

1. 分离控制数据与值存储 #

将红黑树的结构控制字段（指针、颜色）和值字段拆分，让哨兵节点仅包含控制部分：

• 定义基类rb_node_base：

  struct rb_node_base {
      rb_node_base *left;
      rb_node_base *right;
      rb_node_base *parent;
      enum _Node_color { Black, Red } color;
  };
  

• 模板子类继承基类并添加值成员：

  template <typename value_type>
  struct rb_node : public rb_node_base {
      value_type val;
  };
  

  哨兵节点使用rb_node_base类型，无需初始化value_type；实际数据节点使用rb_node<Test>，正常构造值成员。

2. 动态分配并跳过值构造 #

不使用静态哨兵，在红黑树初始化时动态分配节点内存，仅初始化控制字段，跳过value_type的构造：

// 分配内存但不构造Test对象
rb_node<Test>* sentinel = static_cast<rb_node<Test>*>(operator new(sizeof(rb_node<Test>)));
// 手动初始化控制字段
sentinel->left = sentinel;
sentinel->right = sentinel;
sentinel->parent = sentinel;
sentinel->color = rb_node<Test>::Black;
// 注意：绝对不能访问sentinel->val，它未被构造

销毁时直接释放内存，避免调用Test的析构函数：

operator delete(sentinel);

MSVC STL的实现方式 #

MSVC STL通过标记区分节点类型+编译技巧绕开构造检查解决问题：

1. 节点结构设计 #

_Tree_node包含_Isnil标记，用于区分普通数据节点和哨兵（head）节点：

template <class _Value_type, class _Voidptr>
struct _Tree_node {
    using _Nodeptr   = _Rebind_pointer_t<_Voidptr, _Tree_node>;
    using value_type = _Value_type;
    _Nodeptr _Left;
    _Nodeptr _Parent;
    _Nodeptr _Right;
    char _Color;
    char _Isnil; // 标记是否为哨兵节点
    value_type _Myval = _Returns_exactly<value_type>(); // 编译技巧
};

2. 核心技巧：绕开默认构造检查 #

_Returns_exactly<value_type>()是一个编译期辅助工具，它提供一个合法的初始化表达式，让编译器认为_Myval可以被初始化，但实际上在创建哨兵节点时，这个初始化不会被执行。

3. 哨兵节点的创建流程 #

在_Alloc_sentinel_and_proxy函数中：

• 通过分配器动态分配节点内存
• 仅初始化控制字段（_Left、_Parent、_Right、_Color、_Isnil），将_Isnil设为true
• 完全跳过_Myval的构造，因为哨兵节点不需要存储值
• 后续代码访问_Myval前会先检查_Isnil标记，确保不会访问未构造的成员

内容的提问来源于stack exchange，提问作者himu