C++ 侵入式列表

Intrusive lists

提问by Konrad

I've not been able to find too much information about them online. What are they and when are they typically used?

我在网上找不到太多关于它们的信息。它们是什么以及它们通常何时使用？

Thanks.

谢谢。

回答by Konrad

An intrusive list is one where the pointer to the next list node is stored in the same structure as the node data. This is normally A Bad Thing, as it ties the data to the specific list implementation. Most class libraries (for example, the C++ Standard Library) use non-intrusive lists, where the data knows nothing about the list (or other container) implementation.

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

回答by nhed

I actually like the intrusive model

我实际上喜欢侵入式模型

1. Its better on memory (not many small allocations for things to point at other things)
2. It allows you to have an object that exist in multiple containers
3. It allows you to find an element with one search mode (hash) but then find the next element in lexographic order (this is notthe same as #2, but it can be also acomplished boost's multi_index_container, but note that multi_index_container has certain shortcomings that are non-issues with intrusive)

1. 它在内存上更好（用于指向其他事物的小分配不多）
2. 它允许您拥有一个存在于多个容器中的对象
3. 它可以让你找到一个搜索模式（散），但后来发现词素文字顺序的下一个元素的元素（这是不一样的＃2，但它也可以acomplished升压转换器的multi_index_container的，但要注意的multi_index_container有一定的不足之处在于不存在侵入性问题）

Intrusive is GOOD
You just need to know what you are doing (which is true for any container)

Intrusive is GOOD
你只需要知道你在做什么（这对于任何容器都是正确的）

回答by Ziezi

Here is a brief description that is valid for lists as well:

以下是对列表也有效的简要说明：

I. Intrusive containers.

I. 侵入式容器。

Object to be stored contains additional information to allow integration in container. Example:

struct Node
{
    Node* next;   // additional
    Node* prev;   // information 
    T data;
} 

1. Pros:

• stores the objects themselves.


• doesn't involve memory management.


• iteration is faster.
• better exception guarantees.
• predictability in insertion and deletion of objects. (no additional (non-predictable) memory management is required.)
• better memory locality.

2. Cons:

• contains additional data for container integration. (every store type must be adapted (modified) to the container requirements.)
• caution with possible side effects when changing the contents of the stored object.(especially for associative containers.)
• lifetime management of the inserted object, independently from the container.
• object can be possibly disposed before erased from the container leading to iterator invalidation.
• intrusive containers are NON-copyable and NON-assignable.

要存储的对象包含允许在容器中集成的附加信息。例子：

struct Node
{
    Node* next;   // additional
    Node* prev;   // information 
    T data;
} 

1. 优点：

• 存储对象本身。


• 不涉及内存管理。


• 迭代速度更快。
• 更好的异常保证。
• 对象插入和删除的可预测性。（不需要额外的（不可预测的）内存管理。）
• 更好的内存局部性。

2. 缺点：

• 包含用于容器集成的附加数据。（每种商店类型都必须适应（修改）到容器要求。）
• 更改存储对象的内容时要小心可能产生的副作用。（特别是对于关联容器。）
• 插入对象的生命周期管理，独立于容器。
• 对象可能会在从容器中擦除之前被释放，从而导致迭代器失效。
• 侵入式容器是不可复制和不可分配的。

II. Non-instrusive containers (C++ standard containers)

二、非侵入式容器（C++ 标准容器）

Object doesn't "know" and contain details about the container in which is to be stored. Example:

struct Node
{
    T data;
}

1. Pros:

• does not containe additional information regarding the container integration.
• object's lifetime managed by the container. (less complex.)

2. Cons:

• store copies of values passed by the user. (inplace construction possible.)
• an object can belong only to one container. (or the contaier should store pointers to objects.)
• overhead on storing copies. (bookkeeping on each allocation.)
• non-copyable or non-movable objects CAN'T be stored in non-intrusive containers.
• can't store derived object and still maintain its original type. (slicing - looses polymorphism.)

对象不“知道”并包含有关要存储在其中的容器的详细信息。例子：

struct Node
{
    T data;
}

1. 优点：

• 不包含有关容器集成的附加信息。
• 由容器管理的对象的生命周期。（不太复杂。）

2. 缺点：

• 存储用户传递的值的副本。（可以就地施工。）
• 一个对象只能属于一个容器。（或者容器应该存储指向对象的指针。）
• 存储副本的开销。（每次分配的簿记。）
• 不可复制或不可移动的对象不能存储在非侵入式容器中。
• 无法存储派生对象并仍保持其原始类型。（切片 - 失去多态性。）

回答by alta

Intrusives lists are lists where objects are themselves heads or cells of lists. They are good or bad things depending of context.

侵入式列表是对象本身是列表的头部或单元的列表。根据上下文，它们是好是坏。

Inside some defined module (unsecable group of classes working together) it may be the BEST mean to tie relationships between classes. They allow no-cost direct and full management of common relationships like unicity (ex: apples does not apears two times in appletrees, and this does not need any key for this, and apples does not belong to two distincts trees), they are navigable in both directions (direct accès to appletree given an apple and to apples given some appletree). All basic operations are O(1) (no search in some external container).

在某些已定义的模块（一起工作的不可分割的类组）中，它可能是将类之间的关系联系起来的最佳方法。它们允许免费直接和完全管理诸如 unicity 之类的常见关系（例如：苹果不会在苹果树中出现两次，这不需要任何密钥，并且苹果不属于两个不同的树），它们是可导航的在两个方向（直接访问给定一个苹果的苹果树和给定一些苹果树的苹果）。所有基本操作都是 O(1)（不在某些外部容器中搜索）。

Intrusive list are VERY BAD between two Modules. Because they will be tied together, and modules justification is management of code independance.

两个模块之间的侵入式列表非常糟糕。因为它们将被捆绑在一起，并且模块的理由是代码独立性的管理。

回答by Ash

It surprising how so many people get this completely wrong (such as the answer from Ziezi). People seem to over-complicate things when it's really pretty simple.

令人惊讶的是，这么多人完全错了（例如 Ziezi 的回答）。当事情真的很简单时，人们似乎把事情复杂化了。

In an intrusive linked list there is no explicit 'Node' struct/class. Instead the 'Data' struct/class itself contains a next and prev pointer/reference to other Data in the linked list.

在侵入式链表中，没有明确的“节点”结构/类。相反，“数据”结构/类本身包含指向链表中其他数据的下一个和上一个指针/引用。

For example (intrusive linked list node):

例如（侵入式链表节点）：

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

Notice how the next and prev pointers sit alongside and intrudeon the private data fields of the entity such as fieldA. This 'violates' the separation of concerns enforced by standard linked lists (see below) but has benefits in greatly reducing the amount of list walking to locate specific nodes as well as lower memory allocations.

请注意 next 和 prev 指针如何并排并侵入实体的私有数据字段，例如 fieldA。这“违反”了由标准链表（见下文）强制执行的关注点分离，但有利于大大减少列表遍历以定位特定节点的数量以及较低的内存分配。

In an intrusive linked list, the 'linked list' itself is often virtual, there is normally no need to create a linked list struct/class at all.

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

Instead you can simply store a head pointer to the first Data item in some owner/manager. This manager also contains Add/Remove functions to update pointers as needed. For more info see https://gameprogrammingpatterns.com/spatial-partition.html

相反，您可以简单地将指向第一个数据项的头指针存储在某个所有者/管理器中。该管理器还包含添加/删除函数以根据需要更新指针。有关更多信息，请参阅https://gameprogrammingpatterns.com/spatial-partition.html

Having a single pair of next/prev pointers dictates that each object can only belong to one list. However you can of course add multiple pairs of next/prev pointers as needed (or define an array of next/prev pointers) to support objects in multiple lists.

拥有一对 next/prev 指针表明每个对象只能属于一个列表。但是，您当然可以根据需要添加多对 next/prev 指针（或定义 next/prev 指针数组）以支持多个列表中的对象。

In a non-intrusive (ie standard) linked list the next/prev pointers are part of a dedicated 'node' entity and the actual Data entity simply a field in that node.

在非侵入式（即标准）链表中，next/prev 指针是专用“节点”实体的一部分，而实际数据实体只是该节点中的一个字段。

For example (non intrusive linked list node and data):

例如（非侵入式链表节点和数据）：

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

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

Notice how the next/prev pointers do not intrudeon the actual Data entity and the separation of concerns is maintained.

请注意 next/prev 指针如何不侵入实际的 Data 实体并保持关注点分离。

Update:

更新：

You may see other sites such as https://www.data-structures-in-practice.com/intrusive-linked-lists/use a 'List' struct (actually a Node) that contains next/prev pointers and is the single intrusive field in the 'Data' struct/class.

您可能会看到其他站点，例如https://www.data-structures-in-practice.com/intrusive-linked-lists/使用包含 next/prev 指针的“列表”结构（实际上是一个节点），并且是单个“数据”结构/类中的侵入性字段。

This does hide the next/prev pointers from the Data, however it suffers from the need to perform pointer arithmetic simply to access the actual Data associated with the List (Node).

这确实隐藏了数据的下一个/上一个指针，但是它需要执行指针算术来访问与列表（节点）关联的实际数据。

This approach adds needless complexity in my option (over simply embedding next/prev fields directly) just for the the dubious goal of hiding the next/prev pointers. If you need intrusive lists, keep them simple as possible. (Also, in managed memory languages it is difficult or impossible to do pointer arithmetic anyway.)

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