C++程序设计：原理与实践（进阶篇）（原书第2版）

27.9　实例：侵入式容器

C++标准库容器（如vector和map）是非侵入式容器（non-intrusive container），即它们不要求容器内的数据以单个元素的形式被访问，而是对容器整体进行操作。这也是它们为什么有那么好的通用性——适用于所有内置类型和用户自定义类型，只要类型支持拷贝操作即可。另外一类容器被称为侵入式容器（intrusive container），在C和C++中都很常用。下面我们将通过一个非侵入式的容器来说明C风格struct、指针和动态内存分配的使用。

我们可以定义一个支持如下九个操作的双向链表：

基本设计思路是使用户只需提供List*和Link*指针就能完成这些操作。这意味着可以大幅修改这些操作的实现，而无须修改用户程序。显然，我们在命名上受到了STL的影响。List和Link显然可以简单定义如下：

下面是List的图示：

我们目的不是介绍高明的描述技术或者高明的算法，因此本节并未展示这些。但是，请注意程序中并未提及Link所保存的数据（List中的元素）。回过头看一下程序，我们发现Link和List非常像抽象类。Link保存的数据会随后提供。Link*和List*有时被称为不透明类型处理工具，即我们可以在不了解Link和List的内部结构的情况下，使用Link*和List*来处理List中的元素。 ...