数据结构的“侵入性"是什么意思? [英] What does it mean for a data structure to be "intrusive"?

问题描述

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

I've seen the term intrusive used to describe data structures like lists and stacks, but what does it mean?

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

Can you give a code example of an intrusive data structure, and how it differs from a non-intrusive one?

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

Also, why make it intrusive (or, non-intrusive)? What are the benefits? What are the disadvantages?

推荐答案

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

An intrusive data structure is one that requires help from the elements it intends to store in order to store them.

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

Let me reword that. When you put something into that data structure, that "something" becomes aware of the fact that it is in that data structure, in some way. Adding the element to the data structure changes the element.

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

For instance, you can build a non-intrusive binary tree, where each node have a reference to the left and right sub-trees, and a reference to the element value of that node.

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

Or, you can build an intrusive one where the references to those sub-trees are embedded into the value itself.

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

An example of an intrusive data structure would be an ordered list of elements that are mutable. If the element changes, the list needs to be reordered, so the list object has to intrude on the privacy of the elements in order to get their cooperation. ie. the element has to know about the list it is in, and inform it of changes.

ORM 系统通常围绕侵入性数据结构，以尽量减少对大型对象列表的迭代.例如，如果您检索数据库中所有员工的列表，然后更改其中一个员工的名称，并希望将其保存回数据库，则员工对象更改时会告知侵入性员工列表，因为对象知道它在哪个列表中.

ORM-systems usually revolve around intrusive data structures, to minimize iteration over large lists of objects. For instance, if you retrieve a list of all the employees in the database, then change the name of one of them, and want to save it back to the database, the intrusive list of employees would be told when the employee object changed because that object knows which list it is in.

非侵入式列表不会被告知，并且必须弄清楚发生了什么变化以及它是如何自己改变的.

A non-intrusive list would not be told, and would have to figure out what changed and how it changed by itself.

这篇关于数据结构的“侵入性"是什么意思?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！