c++ - 数据结构为 "intrusive"意味着什么？

Question

我见过 intrusive 一词用来描述列表和堆栈等数据结构，但它是什么意思？

您能否给出一个侵入式数据结构的代码示例，以及它与非侵入式数据结构的区别？

另外，为什么要使其具有侵入性(或非侵入性)？有什么好处？有什么缺点？

Answer 1

侵入式数据结构是一种需要它打算存储的元素的帮助才能存储它们的结构。

让我改写一下。当您将某些东西放入该数据结构中时，该“某物”会以某种方式意识到它在该数据结构中的事实。将元素添加到数据结构中会更改元素。

例如，您可以构建一个非侵入式二叉树，其中每个节点都有一个对左右子树的引用，以及对该节点元素值的引用。

或者，您可以构建一个侵入式，其中对这些子树的引用嵌入到值本身中。

侵入式数据结构的一个示例是可变元素的有序列表。如果元素发生变化，则列表需要重新排序，因此列表对象必须侵入元素的隐私才能获得它们的合作。 IE。元素必须知道它所在的列表，并通知它变化。

ORM 系统通常围绕侵入式数据结构展开，以最大限度地减少对大型对象列表的迭代。例如，如果您检索数据库中所有员工的列表，然后更改其中一个的名称，并希望将其保存回数据库，那么当员工对象发生更改时，就会告知侵入性员工列表，因为对象知道它在哪个列表中。

一个非侵入性的列表不会被告知，并且必须弄清楚发生了什么变化以及它是如何变化的。