为什么在 C++ 标准库中使用列表/树节点的基类？

Question

列表（例如和）libstdc++和其他树libc++的内部节点（至少）由两部分构建：节点基类；以及节点类本身。例如，而不是：listforward_list

struct sl_full_node {
  sl_full_node *p;
  int value;
};

...我们会看到类似的东西：

struct sl_node_base {
  sl_node_base *p;
};

struct sl_node : sl_node_base {
  int value;
};

这个习惯用法的一个简单、独立的示例可以在 2008 年的单链表提案中找到。这种方法有什么好处？

Answer 1

所有 STL 容器都需要提供end()哨兵。这意味着，如果支持双向迭代，则必须有一个有效的尾后位置，可以通过迭代器接口在该位置上执行递减操作。在这一部分中，仅处理允许双向迭代的基于节点的容器，因此该std::forward_list容器将暂时被忽略。

如果end()哨兵简单地由任何哨兵值（例如空指针）表示，则不可能执行上述递减操作以移动到前一个节点。解决此问题的一种方法是使用“虚拟节点”。

在 libstdc++ 和 libc++ 实现中，该节点是静态分配的，以便它在对象的整个生命周期中都存在于容器中，并且即使序列完全为空，也允许有效的尾后位置。值得注意的是，使用“序列”一词是为了指容器中所有值的有序迭代，无论节点是线性排列还是在更复杂的图中结构化（std::set）。

如果通过分配全节点来实现结果，这会导致两个副作用：

• 虚拟节点占用的空间不受指针数量的限制，指针是允许与其他节点链接所需的唯一成员属性，但与类型大小成正比T；
• 如果类型T直接存储在节点中，那么在构造对象时，应该找到一个方法以避免T对象构造。

最后一个问题可以通过用T对齐存储替换类型来解决，但这并不能解决占用空间的问题。这种情况使得有必要为虚拟节点引入一个特定的结构，该结构仅包含指向完整节点的指针。然而，创建这样的结构会导致指向完整节点的指针和指向虚拟节点的指针之间的互操作性问题。此外，全节点可以解释为添加了存储的虚拟节点，这一事实表明它们之间的继承关系是有意义的。

因此，它实现了一种表示基本节点的结构，并且可以被实例化以获得虚拟节点，以及一个从表示完整节点的前一个结构派生的结构。

例子：

    struct _List_node_base
    {
      _List_node_base* _M_next;
      _List_node_base* _M_prev;
    };

    template <typename _Tp>
    struct _List_node : public _List_node_base
    {
      _Tp _M_data;
    };

类似的推理可以应用于std::forward_list容器，但是容器需要一个before_begin()哨兵，可以通过迭代器接口在其上执行增量操作。