小开

侵入式列表是指指向下一个列表节点的指针存储在与节点数据相同的结构中的列表。这通常是一件坏事，因为它将数据绑定到特定的列表实现。大多数类库(例如，C++标准程式库)使用非侵入式列表，其中的数据对列表(或其他容器)的实现一无所知。

小开

我其实挺喜欢这种打扰型的。

它在内存方面更好(对事物的小分配不多) 指向其他事物)
它允许您拥有一个同时存在于多个容器中的对象。
它允许您使用一种搜索模式(hash)查找一个元素，然后按照词法顺序查找下一个元素
- 这是没有和 # 2相同的，但是它可以用助推器的 multi_index_container来完成，但是请注意，multi_index_container有一些缺点，这些缺点对于侵入式容器来说是没有问题的。

打扰是好事

你只需要知道你在做什么(对于任何容器都是如此)。

小开

入侵列表是对象本身就是列表的头或单元格的列表。它们是好事还是坏事取决于上下文。

在一些已定义的模块(不可分割的类组合在一起工作)中，它可能是绑定类之间关系的最佳方法。它们允许无成本直接和全面管理共同的关系，如统一性(例如: 苹果不出现两次在苹果树，这不需要任何关键，苹果不属于两个不同的树) ，它们可以在两个方向导航(直接访问苹果树给予一个苹果和苹果给予一些苹果树)。所有基本操作都是 O (1)(在某些外部容器中不进行搜索)。

两个模块之间的入侵列表非常糟糕。因为它们将被绑定在一起，而模块对齐是代码独立性的管理。

小开

下面是一个对列表也有效的简短描述:

侵入性容器

要存储的对象包含允许在容器中集成的附加信息。例如:
Struct Node
{
节点 * next;//附加
节点 * prev;//信息
T 数据;
}
1. 优点:

储存物品本身。

不涉及内存管理。

迭代更快。

更好的例外担保。

对象插入和删除的可预测性(不需要额外的(不可预测的)内存管理)

更好的内存位置。

2. 缺点:

包含用于容器集成的附加数据。 (每种存储类型都必须根据集装箱的要求进行调整(修改)。)

更改储存物件的内容时要小心，避免可能出现的副作用(尤其是关联容器)

独立于容器的插入对象的生存期管理。

对象可能在从容器中擦除之前被释放，从而导致迭代器失效。

侵入式容器是不可复制和不可分配的。

非侵入性容器(C + + 标准容器)

对象不“知道”并且包含有关要存储在其中的容器的详细信息。示例:
Struct Node
{
T 数据;
}
1. 优点:

不包含关于容器集成的其他信息。

由容器管理的对象的生存期。(不太复杂。)

2. 缺点:

存储用户传递的值的副本(尽可能替换构造)

一个对象只能属于一个容器(或者容器应该存储指向对象的指针)

存储副本的开销(每次分配的簿记)

~~不可复制或不可移动的对象 CA N 不存储在非侵入性容器中。~~

不能存储派生对象并仍然保持其原始类型(切片-松散多态性)

小开

令人惊讶的是，竟然有这么多人完全搞错了(比如 Ziezi 的答案)。人们似乎把事情过于复杂了，其实事情很简单。

在侵入式链表中，没有显式的“ Node”结构/类。相反，“ Data”结构/类本身包含一个指向链表中其他 Data 的 next 和 prev 指针/引用。

例如(侵入式链表节点) :

struct Data {
Data *next;
Data *prev;
int fieldA;
char * fieldB;
float fieldC;
}

注意实体的私有数据字段(如 fieldA)上的下一个和 prev 指针与 打扰了是如何并排放置的。这“违反”了标准链表(见下文)的关注点分离，但有利于大大减少定位特定节点的链表遍历量，以及降低内存分配。

在侵入式链表中，“链表”本身通常是虚拟的，通常根本不需要创建链表结构/类。

相反，您可以简单地在某个所有者/管理者中存储指向第一个 Data 项的头指针。此管理器还包含添加/删除函数，以根据需要更新指针。欲了解更多信息，请参见 < a href = “ https://gameProgrammingpatns.com/space-parttion.html”rel = “ norefrer”> https://gameprogrammingpatterns.com/spatial-partition.html

拥有一对 next/prev 指针意味着每个对象只能属于一个列表。当然，您可以根据需要添加多对 next/prev 指针(或者定义一个 next/prev 指针数组) ，以支持多个列表中的对象。

在非侵入(即标准)链表中，下一个/prev 指针是专用“节点”实体的一部分，而实际的 Data 实体只是该节点中的一个字段。

例如(非侵入性链表节点和数据) :

struct Data {
int fieldA;
char * fieldB;
float fieldC;
}


struct Node {
Node *next;
Node *prev;
Data *data;
}

注意实际数据实体和关注点分离上的 next/prev 指针 不要打扰是如何维护的。

更新:

您可能会看到其他站点(如 https://www.data-structures-in-practice.com/intrusive-linked-lists/)使用“ List”结构(实际上是一个 Node) ，它包含 next/prev 指针，是“ Data”结构/类中的单个侵入字段。

这确实会对 Data 隐藏下一个/prev 指针，但是它需要执行指针算法来访问与 List (Node)关联的实际数据。

这种方法在我的选项中增加了不必要的复杂性(而不是直接嵌入 next/prev 字段) ，只是为了达到隐藏 next/prev 指针的可疑目的。如果您需要干扰列表，请尽可能使它们保持简单。(另外，在托管内存语言中，无论如何都很难或不可能进行指针算术。)

侵扰名单

1. 优点:

2. 缺点:

非侵入性容器(C + + 标准容器)

1. 优点:

2. 缺点: