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

Question

我见过术语“侵入式”用于描述列表和堆栈等数据结构，但它是什么意思？

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

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

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

Answer 1

让我重新表述一下。当您将某些内容放入该数据结构中时，该“某些内容”会以某种方式意识到它位于该数据结构中。将元素添加到数据结构会更改元素。

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

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

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

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

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

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

Answer 2

非侵入性：

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;

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

当保存的项目具有连接它们所需的指针或引用时，对象会被更改以为数据结构腾出空间，这称为“侵入式数据结构”。例如，侵入式链表中的每个节点或对象都将包含一个指向紧随其后的节点的指针。另一方面，“非侵入式数据结构”使连接或组织机制与数据片段保持分离。数据结构本身在保存的片段之外保留自己的引用或指针，因此它负责链接。由于侵入式数据结构不需要不同的节点对象，因此内存效率更高；但是，它们确实需要更改要存储的对象，这可能并不总是可行。

Answer 3