nhe*_*hed 36
我其实喜欢这种侵入式模型
侵入是好的
你只需要知道你在做什么(任何容器都是如此)
小智 35
侵入式列表是指向下一个列表节点的指针存储在与节点数据相同的结构中的列表.这通常是一个坏事,因为它将数据绑定到特定的列表实现.大多数类库(例如,C++标准库)使用非侵入式列表,其中数据对列表(或其他容器)实现一无所知.
Ash*_*Ash 16
令人惊讶的是，这么多人完全错了（例如 Ziezi 的回答）。当事情真的很简单时，人们似乎把事情复杂化了。
在侵入式链表中，没有明确的“节点”结构/类。相反，“数据”结构/类本身包含指向链表中其他数据的下一个和上一个指针/引用。
例如（侵入式链表节点）：
struct Data {
Data *next;
Data *prev;
int fieldA;
char * fieldB;
float fieldC;
}
请注意 next 和 prev 指针如何并排并侵入实体的私有数据字段，例如 fieldA。这“违反”了由标准链表（见下文）强制执行的关注点分离，但有利于大大减少列表遍历以定位特定节点的数量以及较低的内存分配。
在侵入式链表中，“链表”本身通常是虚拟的，通常根本不需要创建链表结构/类。
相反，您可以简单地将指向第一个数据项的头指针存储在某个所有者/管理器中。该管理器还包含添加/删除函数以根据需要更新指针。有关更多信息，请参阅https://gameprogrammingpatterns.com/spatial-partition.html
拥有一对 next/prev 指针表明每个对象只能属于一个列表。但是，您当然可以根据需要添加多对 next/prev 指针（或定义 next/prev 指针数组）以支持多个列表中的对象。
在非侵入式（即标准）链表中，next/prev 指针是专用“节点”实体的一部分，而实际数据实体只是该节点中的一个字段。
例如（非侵入式链表节点和数据）：
struct Data {
int fieldA;
char * fieldB;
float fieldC;
}
struct Node {
Node *next;
Node *prev;
Data *data;
}
请注意 next/prev 指针如何不侵入实际的 Data 实体并保持关注点分离。
更新：
您可能会看到其他站点，例如https://www.data-structures-in-practice.com/intrusive-linked-lists/使用包含 next/prev 指针的“列表”结构（实际上是一个节点）并且是单个“数据”结构/类中的侵入性字段。
这确实隐藏了数据的下一个/上一个指针，但是它需要执行指针算术来访问与列表（节点）关联的实际数据。
这种方法在我的选项中增加了不必要的复杂性（而不是简单地直接嵌入 next/prev 字段），只是为了隐藏 next/prev 指针的可疑目标。如果您需要侵入式列表，请尽可能使它们简单。（此外，在托管内存语言中，无论如何都很难或不可能进行指针运算。）
以下是对列表有效的简要说明:
要存储的对象包含允许在容器中集成的其他信息.例:
struct Node { Node* next; // additional Node* prev; // information T data; }1.优点:
- 存储对象本身.
- 不涉及内存管理.
- 迭代更快.
- 更好的例外保证.
- 插入和删除对象的可预测性.(不需要额外的(不可预测的)内存管理.)
- 更好的记忆局部性.
2.缺点:
- 包含容器集成的其他数据.(每种商店类型必须根据容器要求进行调整(修改).)
- 更改存储对象的内容时可能会产生副作用(特别是对于关联容器.)
- 插入对象的生命周期管理,独立于容器.
- 在从容器中删除之前,可能会丢弃对象,从而导致迭代器失效.
- 侵入式容器是不可复制的和不可分配的.
对象不"知道"并包含有关要存储的容器的详细信息.例:
struct Node { T data; }1.优点:
- 不包含有关容器集成的其他信息.
- 对象的生命周期由容器管理.(不太复杂.)
2.缺点:
- 存储用户传递的值的副本.(可以进行现场施工.)
- 一个对象只能属于一个容器.(或者容器应该存储指向对象的指针.)
- 存储副本的开销.(每次分配的簿记.)
不可复制或不可移动的对象不能存储在非侵入式容器中.- 无法存储派生对象并仍保持其原始类型.(切片 - 失去多态性.)
小智 5
侵入式列表是对象本身就是列表的头部或单元格的列表。它们是好是坏，取决于上下文。
在某些已定义的模块（无法分类的类一起工作）中，绑定类之间的关系可能是最好的方法。它们允许免费和直接地全面管理诸如unicity之类的常见关系（例如：苹果在Appletree中不两次，并且不需要任何密钥，并且Apple不属于两个不同的树），它们是可导航的双向（直接访问appletree给出了一个苹果和访问了apples给出了一个appletree）。所有基本操作均为O（1）（在某些外部容器中不进行搜索）。
侵入式列表在两个模块之间非常差。因为它们将被绑在一起，所以模块的合理性就是代码独立性的管理。