数据结构是“侵入性”意味着什么？

我已经看到用于描述数据结构（如列表和堆栈）的术语intrusive ，但这是什么意思？

你能给出一个侵入式数据结构的代码示例，以及它与非侵入式数据结构有什么不同？

另外，为什么让它侵入（或非侵入性）？ 有什么好处？ 有什么缺点？

Answer 1

一个侵入式的数据结构是需要来自它打算存储的元素的帮助来存储它们的。

让我再说一遍。 当你将某些东西放入数据结构中时，这个“某些东西”会以某种方式意识到它在这个数据结构中的事实。 将元素添加到数据结构会更改元素。

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

或者，您可以创build一个侵入式的引用，将这些子树的引用embedded到值本身中。

一个侵入式数据结构的例子将是一个有序的可变元素列表。 如果元素发生变化，列表需要重新sorting，所以列表对象必须侵入元素的隐私才能获得合作。 即。 元素必须知道它所在的列表，并通知其变化。

ORM系统通常围绕着侵入式的数据结构，最大限度地减less对大型对象列表的迭代。 例如，如果您检索数据库中所有员工的列表，然后更改其中一个员工的姓名，并且想要将其保存回数据库，则会在员工对象发生更改时通知员工侵入性列表，因为对象知道它在哪个列表中。

一个非侵入性的名单将不会被告知，并将不得不弄清楚改变了什么，以及改变了它自己。

Answer 2

在侵入性容器中，数据本身负责存储容器的必要信息。 这意味着一方面数据types需要根据其存储方式进行专门化，另一方面则意味着数据“知道”数据的存储方式，因此可以稍微优化一些。

非侵入式：

template<typename T> class LinkedList { struct ListItem { T Value; ListItem* Prev; ListItem* Next; }; ListItem* FirstItem; ListItem* LastItem; [...] ListItem* append(T&& val) { LastItem = LastItem.Next = new ListItem{val, LastItem, nullptr}; }; }; LinkedList<int> IntList; 

侵入：

 template<typename T> class LinkedList { T* FirstItem; T* LastItem; [...] T* append(T&& val) { T* newValue = new T(val); newValue.Next = nullptr; newValue.Prev = LastItem; LastItem.Next = newValue; LastItem = newValue; }; }; struct IntListItem { int Value; IntListItem* Prev; IntListItem* Next; }; LinkedList<IntListItem> IntList; 

我个人更喜欢侵入式的devise，因为它的透明度。