数据结构"侵入性"是什么意思？

Question

我已经看到用于描述列表和堆栈等数据结构的术语intrusive,但它是什么意思？

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

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

Answer 1

侵入式数据结构需要来自其打算存储的元素的帮助才能存储它们.

让我改写一下.当你在数据结构中添加某些内容时,"某些东西"会以某种方式意识到它在数据结构中的事实.将元素添加到数据结构会更改元素.

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

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

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

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;

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