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

侵入式数据结构需要从它打算存储的元素中获得帮助来存储它们。

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

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

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

侵入式数据结构的一个例子是可变元素的有序列表。如果元素发生变化，列表需要重新排序，因此列表对象必须侵犯元素的隐私权以获得它们的合作。也就是说。元素必须知道它所在的列表，并通知它更改。

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

一个非侵入性的列表将不会被告知，并且将不得不弄清楚什么改变了，以及它自己是如何改变的。

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

非侵入性:

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;

个人而言，我更喜欢侵入式设计，因为它的透明度。