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

Question

在

libstdc++

和

libc++

中，列表的内部节点（例如

list

和

forward_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替换为对齐存储来解决，但这并不能解决占用空间的问题。这种情况使得有必要为虚拟节点引入一个特定的结构，该结构只包含指向完整节点的指针。然而，创建这样的结构会导致指向ful节点的指针和指向dummy节点的指针之间的互操作性问题。此外，完整节点可以解释为添加了存储的虚拟节点，这一事实表明它们之间可能存在继承关系。

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

std::forward_list

容器，但是，它需要一个

before_begin()

哨兵，可以通过迭代器接口在其上执行增量操作。