构建非循环依赖关系的最简单,最有效的数据结构是什么？

Question

我正在尝试构建一个序列来确定销毁对象的顺序.我们可以假设没有周期.如果对象A在其(A)构造期间使用对象B,则对象B在对象A的销毁期间仍应可用.因此,所需的破坏顺序是A,B.如果另一个对象C在其(C)构造期间也使用对象B,则所需的顺序是A,C,B.通常,只要对象X仅被销毁在构造过程中使用该对象的所有其他对象之后,破坏是安全的.

如果到目前为止我们的销毁订单是AECDBF,我们现在得到一个X(我们从来不知道最先发生的结构是什么顺序,它是在飞行中发现的),它在构造过程中使用C和F,然后我们可以通过将X放在列表中当前较早的前一个C或F(恰好是C)之前获得新的安全订单.所以新订单将是AB X CDEF.

在X示例的上下文中,链接列表似乎不合适,因为将涉及大量线性扫描以确定哪个更早,C或F.数组将意味着慢插入,这将是更常见的操作之一.优先级队列实际上没有合适的接口,没有,"在这些项目中最早的一个之前插入此项目"(我们事先不知道正确的优先级,以确保它在较低优先级元素之前插入并且不打扰其他条目).

构造所有对象,计算所需的顺序,并且序列将被迭代一次并按顺序被破坏.不需要进行任何其他操作(实际上,在使用任何数据结构来确定顺序之后,可以将其复制到平面阵列中并丢弃).

编辑:只是为了澄清,第一次使用对象的是它的构造时间.因此,如果A使用B,则E使用B,当E尝试使用B时,它已经被创建.这意味着堆栈不会提供所需的顺序.当我们想要AEB时,AB将成为ABE.

编辑2:我正在尝试建立顺序'我去'以保持算法到位.我宁愿避免建立一个大的中间结构,然后将其转换为最终结构.

编辑3:我太复杂了; p

Answer 1

由于依赖关系始终在依赖于它们的对象之前初始化,并且在这些对象被销毁之后仍然可用,因此以完全相反的初始化顺序销毁对象应始终是安全的.因此,您只需要一个链接列表,在初始化对象时将其添加到其中,然后逐步销毁,并为每个对象请求初始化其初始化之前尚未初始化的所有依赖项.

因此,对于每个对象的初始化:

• 初始化self,初始化未初始化的依赖关系
• 将self添加到破坏列表的前面(如果你正在使用堆栈,则将self推入堆栈)

并且为了销毁,只需从前面走向链接列表(或从堆栈中弹出项目直到空),随时随地销毁.因此,按照B,A,C顺序初始化的第一段中的例子将按照C,A,B的顺序销毁 - 这是安全的; 您的编辑中的示例将按照B,A,E(不是A,B,E,因为A取决于B)的顺序初始化,因此按照E,A,B的顺序销毁,这也是安全的.