I've looked at the problem a dozen different ways over the years, and the only solution I've found that works every time is to re-architect my solution to not use a circular reference.

多年来,我已经用十几种不同的方式查看了这个问题,我发现每次都能解决的唯一解决方案是重新构建我的解决方案,而不是使用循环引用。

Edit:

Can you expand? For example, how would you deal with a parent-child relation when the child needs to know about/access the parent? – OB OB

你能扩展吗?例如,当孩子需要了解/访问父母时,您将如何处理父子关系? - OB OB

As I said, the only good solution is to avoid such constructs unless you are using a runtime that can deal with them safely.

正如我所说,唯一的好解决方案是避免使用这样的结构,除非你使用的运行时可以安全地处理它们。

That said, if you must have a tree / parent-child data structure where the child knows about the parent, you're going to have to implement your own, manually called teardown sequence (i.e. external to any destructors you might implement) that starts at the root (or at the branch you want to prune) and does a depth-first search of the tree to remove references from the leaves.

也就是说,如果你必须有一个树/父子数据结构,孩子知道父母,你将不得不实现自己的,手动调用的拆解序列(即你可能实现的任何析构函数的外部)在根(或您想要修剪的分支)并对树进行深度优先搜索以从叶中删除引用。

It gets complex and cumbersome, so IMO the only solution is to avoid it entirely.

它变得复杂和繁琐,因此IMO唯一的解决方案是完全避免它。

Here is a solution I've seen:

这是我见过的解决方案:

Add a method to each object to tell it to release its references to the other objects, say call it Teardown().

向每个对象添加一个方法,告诉它释放对其他对象的引用,比如称之为Teardown()。

Then you have to know who 'owns' each object, and the owner of an object must call Teardown() on it when they're done with it.

然后你必须知道谁拥有每个对象,并且对象的所有者在完成它时必须在其上调用Teardown()。

If there is a circular reference, say A <-> B, and C owns A, then when C's Teardown() is called, it calls A's Teardown, which calls Teardown on B, B then releases its reference to A, A then releases its reference to B (destroying B), and then C releases its reference to A (destroying A).

如果有一个循环引用,比如A < - > B,C拥有A,那么当调用C的Teardown()时,它会调用A的Teardown,它在B上调用Teardown,B然后释放它对A的引用,A然后释放它引用B(破坏B),然后C释放它对A的引用(破坏A)。

I guess another method, used by garbage collectors, is "mark and sweep":

我猜垃圾收集器使用的另一种方法是“标记和扫描”:

1. Set a flag in every object instance

在每个对象实例中设置一个标志

2. Traverse the graph of every instance that's reachable, clearing that flag

遍历每个可到达的实例的图形,清除该标志

3. Every remaining instance which still has the flag set is unreachable, even if some of those instances have circular references to each other.

仍然具有设置标志的每个剩余实例都是不可达的,即使这些实例中的一些实例具有彼此的循环引用。

I'd like to suggest a slightly different method that occured to me, I don't know if it has any official name:

我想建议一个稍微不同的方法发生在我身上,我不知道它是否有任何正式名称:

Objects by themeselves don't have a reference counter. Instead, groups of one or more objects have a single reference counter for the entire group, which defines the lifetime of all the objects in the group.

自己的对象没有引用计数器。相反,一个或多个对象的组具有整个组的单个引用计数器,其定义组中所有对象的生存期。

In a similiar fashion, references share groups with objects, or belong to a null group.

以类似的方式,引用与对象共享组,或属于空组。

A reference to an object affects the reference count of the (object's) group only if it's (the reference) external to the group.

对象的引用仅影响(对象)组的引用计数(如果它是组的外部(引用))。

If two objects form a circular reference, they should be made a part of the same group. If two groups create a circular reference, they should be united into a single group.

如果两个对象形成循环引用,则它们应成为同一组的一部分。如果两个组创建循环引用,则它们应合并为一个组。

Bigger groups allow more reference-freedom, but objects of the group have more potential of staying alive while not needed.

更大的群体允许更多的参考自由,但群体的对象更有可能在不需要时保持活力。

I have always redesigned to avoid the issue. One of the common cases where this comes up is the parent child relationship where the child needs to know about the parent. There are 2 solutions to this

我总是重新设计以避免这个问题。出现这种情况的常见情况之一是父子关系,孩子需要知道父母的关系。有两个解决方案

1. Convert the parent to a service, the parent then does not know about the children and the parent dies when there are no more children or the main program drops the parent reference.

   将父项转换为服务,父项不知道子项,父项在没有子项或主程序删除父项引用时死亡。

2. If the parent must have access to the children, then have a register method on the parent which accepts a pointer that is not reference counted, such as an object pointer, and a corresponding unregister method. The child will need to call the register and unregister method. When the parent needs to access a child then it type casts the object pointer to the reference counted interface.

   如果父级必须有子级访问权限,则在父级上有一个register方法,该方法接受一个非引用计数的指针,例如对象指针和相应的取消注册方法。孩子需要调用注册和取消注册方法。当父级需要访问子级时,它会键入将对象指针强制转换为引用计数接口。

When using reference counting, what are possible solutions/techniques to deal with circular references?

使用引用计数时,有哪些可能的解决方案/技术来处理循环引用?

Three solutions:

1. Augment naive reference counting with a cycle detector: counts decremented to non-zero values are considered to be potential sources of cycles and the heap topology around them is searched for cycles.

   使用循环检测器增加初始引用计数:递减到非零值的计数被认为是潜在的循环源,并且在它们周围的堆拓扑中搜索循环。

2. Augment naive reference counting with a conventional garbage collector like mark-sweep.

   使用传统的垃圾收集器(如标记扫描)增加简单的引用计数。

3. Constrain the language such that its programs can only ever produce acyclic (aka unidirectional) heaps. Erlang and Mathematica do this.

   限制语言使其程序只能生成非循环(也称为单向)堆。 Erlang和Mathematica这样做。

4. Replace references with dictionary lookups and then implement your own garbage collector that can collect cycles.

   用字典查找替换引用,然后实现可以收集周期的垃圾收集器。

i too am looking for a good solution to the circularly reference counted problem.

我也在寻找循环引用计数问题的良好解决方案。

i was stealing borrowing an API from World of Warcraft dealing with achievements. i was implicitely translating it into interfaces when i realized i had circular references.

我正在偷取借用魔兽世界中的API来处理成就。当我意识到我有循环引用时,我隐含地将其转换为接口。

Note: You can replace the word achievements with orders if you don't like achievements. But who doesn't like achievements?

注意:如果您不喜欢成就,可以用订单替换成就一词。但谁不喜欢成就?

There's the achievement itself:

有成就本身:

IAchievement = interface(IUnknown)
   function GetName: string;
   function GetDescription: string;
   function GetPoints: Integer;
   function GetCompleted: Boolean;

   function GetCriteriaCount: Integer;
   function GetCriteria(Index: Integer): IAchievementCriteria;
end;

And then there's the list of criteria of the achievement:

然后是成就标准清单:

IAchievementCriteria = interface(IUnknown)
   function GetDescription: string;
   function GetCompleted: Boolean;
   function GetQuantity: Integer;
   function GetRequiredQuantity: Integer;
end;    

All achievements register themselves with a central IAchievementController:

所有成就都使用中央IAchievementController注册:

IAchievementController = interface
{
   procedure RegisterAchievement(Achievement: IAchievement);
   procedure UnregisterAchievement(Achievement: IAchievement);
}

And the controller can then be used to get a list of all the achievements:

然后控制器可用于获取所有成就的列表:

IAchievementController = interface
{
   procedure RegisterAchievement(Achievement: IAchievement);
   procedure UnregisterAchievement(Achievement: IAchievement);

   function GetAchievementCount(): Integer;
   function GetAchievement(Index: Integer): IAchievement;
}

The idea was going to be that as something interesting happened, the system would call the IAchievementController and notify them that something interesting happend:

我的想法是,当有趣的事情发生时,系统会调用IAchievementController并通知他们发生了一些有趣的事情:

IAchievementController = interface
{
   ...
   procedure Notify(eventType: Integer; gParam: TGUID; nParam: Integer);
}

And when an event happens, the controller will iterate through each child and notify them of the event through their own Notify method:

当事件发生时,控制器将遍历每个子节点并通过自己的Notify方法通知它们事件:

IAchievement = interface(IUnknown)
   function GetName: string;
   ...

   function GetCriteriaCount: Integer;
   function GetCriteria(Index: Integer): IAchievementCriteria;

   procedure Notify(eventType: Integer; gParam: TGUID; nParam: Integer);
end;

If the Achievement object decides the event is something it would be interested in it will notify its child criteria:

如果Achievement对象决定事件是它感兴趣的东西,它将通知其子标准:

IAchievementCriteria = interface(IUnknown)
   function GetDescription: string;
   ...
   procedure Notify(eventType: Integer; gParam: TGUID; nParam: Integer);
end;    

Up until now the dependancy graph has always been top-down:

到目前为止,依赖图始终是自上而下的:

 IAchievementController --> IAchievement --> IAchievementCriteria

But what happens when the achievement's criteria have been met? The Criteria object was going to have to notify its parent `Achievement:

但是,当达到成就标准时会发生什么? Criteria对象必须通知其父级“成就:

 IAchievementController --> IAchievement --> IAchievementCriteria
                                    ^                      |
                                    |                      |
                                    +----------------------+

Meaning that the Criteria will need a reference to its parent; the who are now referencing each other - memory leak.

意味着标准需要引用其父母;谁现在互相引用 - 内存泄漏。

And when an achievement is finally completed, it is going to have to notify its parent controller, so it can update views:

当一项成就最终完成时,它将不得不通知其父控制器,因此它可以更新视图:

 IAchievementController --> IAchievement --> IAchievementCriteria
      ^                      |    ^                      |
      |                      |    |                      |                                        
      +----------------------+    +----------------------+

Now the Controller and its child Achievements circularly reference each other - more memory leaks.

现在,Controller及其子成就循环引用了彼此 - 更多的内存泄漏。

i thought that perhaps the Criteria object could instead notify the Controller, removing the reference to its parent. But we still have a circular reference, it just takes longer:

我认为也许Criteria对象可以通知Controller,删除对其父级的引用。但是我们仍然有一个循环引用,只需要更长的时间:

 IAchievementController --> IAchievement --> IAchievementCriteria
      ^                      |                          |
      |                      |                          |                                        
      +<---------------------+                          |
      |                                                 |
      +-------------------------------------------------+

The World of Warcraft solution

Now the World of Warcraft api is not object-oriented friendly. But it does solve any circular references:

现在魔兽世界api不是面向对象友好的。但它确实解决了任何循环引用:

1. Do not pass references to the Controller. Have a single, global, singleton, Controller class. That way an achievement doesn't have to reference the controller, just use it.

   不要将引用传递给Controller。拥有一个单一的全局单例Controller类。这样,成就不必参考控制器,只需使用它。

   Cons: Makes testing, and mocking, impossible - because you have to have a known global variable.

   缺点:进行测试和嘲弄是不可能的 - 因为你必须有一个已知的全局变量。

2. An achievement doesn't know its list of criteria. If you want the Criteria for an Achievement you ask the Controller for them:

   成就不知道其标准清单。如果您想要成就标准,请向Controller询问:

    IAchievementController = interface(IUnknown)
        function GetAchievementCriteriaCount(AchievementGUID: TGUID): Integer;
        function GetAchievementCriteria(Index: Integer): IAchievementCriteria;
    end;
   

   Cons: An Achievement can no longer decide to pass notifications to it's Criteria, because it doesn't have any criteria. You now have to register Criteria with the Controller

   缺点:成就不能再决定将通知传递给它的标准,因为它没有任何标准。您现在必须向Controller注册Criteria

3. When a Criteria is completed, it notifies the Controller, who notifies the Achievement:

   当标准完成后,它会通知控制器,控制器通知成就:

    IAchievementController-->IAchievement      IAchievementCriteria
         ^                                              |
         |                                              |
         +----------------------------------------------+
   

   Cons: Makes my head hurt.

   缺点:让我的头受伤。

i'm sure a Teardown method is much more desirable that re-architecting an entire system into a horribly messy API.

我确信将整个系统重新构建为一个非常混乱的API,更加可取的是Teardown方法。

But, like you wonder, perhaps there's a better way.

但是,就像你想知道的那样,也许有更好的方法。

Put things into a hierarchy

Having weak references is one solution. The only other solution I know of is to avoid circular owning references all together. If you have shared pointers to objects, then this means semantically that you own that object in a shared manner. If you use shared pointers only in this way, then you can hardly get cyclic references. It does not occur very often that objects own each other in a cyclic manner, instead objects are usually connected through a hierarchical tree-like structure. This is the case I'll describe next.

弱引用是一种解决方案。我所知道的唯一其他解决方案是避免循环拥有所有引用。如果您有共享指向对象的指针,那么这在语义上意味着您以共享方式拥有该对象。如果仅以这种方式使用共享指针,那么很难获得循环引用。对象通常不会以循环方式彼此拥有,而是通常通过分层树状结构连接。这是我接下来要描述的情况。

Dealing with trees

If you have a tree with objects having a parent-child relationship, then the child does not need an owning reference to its parent, since the parent will outlive the child anyways. Hence a non-owning raw back pointer will do. This also applies to elements pointing to a container in which they are situated. The container should, if possible, use unique pointers or values instead of shared pointers anyways, if possible.

如果您的树具有父子关系的对象,则子对象不需要对其父对象的拥有引用,因为父对象无论如何都会比对象更长。因此,非拥有的原始后退指针将执行。这也适用于指向它们所在容器的元素。如果可能的话,容器应尽可能使用唯一的指针或值而不是共享指针。

Emulating garbage collection

If you have a bunch of objects that can wildly point to each other and you want to clean up as soon as some objects are not reachable, then you might want to build a container for them and an array of root references in order to do garbage collection manually.

如果你有一堆对象可以疯狂地指向对方并且你想在一些对象无法访问时立即清理,那么你可能想为它们构建一个容器和一个根引用数组以便做垃圾手动收集。

Use unique pointers, raw pointers and values

In the real world I have found that the actual use cases of shared pointers are very limited and they should be avoided in favor of unique pointers, raw pointers, or -- even better -- just value types. Shared pointers are usually used when you have multiple references pointing to a shared variable. Sharing causes friction and contention and should be avoided in the first place, if possible. Unique pointers and non-owning raw pointers and/or values are much easier to reason about. However, sometimes shared pointers are needed. Shared pointers are also used in order to extend the lifetime of an object. This does usually not lead to cyclic references.

在现实世界中,我发现共享指针的实际用例非常有限,应该避免使用独特的指针,原始指针,或者 - 甚至更好 - 只是值类型。当您有多个指向共享变量的引用时,通常会使用共享指针。共享会导致摩擦和争用,如果可能的话,首先应该避免。唯一指针和非拥有原始指针和/或值更容易推理。但是,有时需要共享指针。共享指针也用于延长对象的生命周期。这通常不会导致循环引用。

Bottom line

Use shared pointers sparingly. Prefer unique pointers and non-owning raw pointers or plain values. Shared pointers indicate shared ownership. Use them in this way. Order your objects in a hierarchy. Child objects or objects on the same level in a hierarchy should not use owning shared references to each other or to their parent, but they should use non-owning raw pointers instead.

谨慎使用共享指针。首选独特的指针和非拥有的原始指针或普通值。共享指针表示共享所有权。以这种方式使用它们。在层次结构中排序对象。层次结构中同一级别的子对象或对象不应使用彼此或其父级的共享引用,但它们应使用非拥有原始指针。

No one has mentioned that there is a whole class of algorithms that collect cycles, not by doing mark and sweep looking for non-collectable data, but only by scanning a smaller set of possibly circular data, detecting cycles in them and collecting them without a full sweep.

没有人提到有一整类算法可以收集周期,而不是通过标记和扫描寻找不可收集的数据,而只是通过扫描一小组可能的循环数据,检测它们中的周期并收集它们而不需要全扫。

To add more detail, one idea for making a set of possible nodes for scanning would be ones whose reference count was decremented but which didn't go to zero on the decrement. Only nodes to which this has happened can be the point at which a loop was cut off from the root set.

为了添加更多细节,制作一组可能的扫描节点的一个想法是,其引用计数递减但在递减时没有变为零。只有发生这种情况的节点才能成为从根集中切断循环的点。

Python has a collector that does that, as does PHP.

Python有一个收集器可以做到这一点,就像PHP一样。

I'm still trying to get my head around the algorithm because there are advanced versions that claim to be able to do this in parallel without stopping the program...

我仍然试图了解算法,因为有高级版本声称可以并行执行此操作而不会停止程序...

In any case it's not simple, it requires multiple scans, an extra set of reference counters, and decrementing elements (in the extra counter) in a "trial" to see if the self referential data ends up being collectable.

在任何情况下,它都不简单,它需要在“试验”中进行多次扫描,一组额外的参考计数器和递减元素(在额外计数器中)以查看自引用数据是否最终可收集。

Some papers: "Down for the Count? Getting Reference Counting Back in the Ring" Rifat Shahriyar, Stephen M. Blackburn and Daniel Frampton http://users.cecs.anu.edu.au/~steveb/downloads/pdf/rc-ismm-2012.pdf "A Unified Theory of Garbage Collection" by David F. Bacon, Perry Cheng and V.T. Rajan http://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf

一些论文:“为伯爵计算?获得参考计数”Rifat Shahriyar,Stephen M. Blackburn和Daniel Frampton http://users.cecs.anu.edu.au/~steveb/downloads/pdf/rc- ismm-2012.pdf“统一垃圾收集理论”,David F. Bacon,Perry Cheng和VT Rajan http://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf

There are lots more topics in reference counting such as exotic ways of reducing or getting rid of interlocked instructions in reference counting. I can think of 3 ways, 2 of which have been written up.

在引用计数中有更多的主题,例如减少或去除引用计数中的互锁指令的奇特方法。我可以想到3种方法,其中2种已被写出来。

If you need to store the cyclic data, for a snapShot into a string,

如果需要存储循环数据,将snapShot存储为字符串,

I attach a cyclic boolean, to any object that may be cyclic.

我将循环布尔值附加到任何可能是循环的对象。

Step 1: When parsing the data to a JSON string, I push any object.is_cyclic that hasn't been used into an array and save the index to the string. (Any used objects are replaced with the existing index).

步骤1:当将数据解析为JSON字符串时,我将任何尚未使用的object.is_cyclic推送到数组中并将索引保​​存到字符串中。 (任何使用的对象都将替换为现有索引)。

Step 2: I traverse the array of objects, setting any children.is_cyclic to the specified index, or pushing any new objects to the array. Then parsing the array into a JSON string.

第2步:遍历对象数组,将所有children.is_cyclic设置为指定的索引,或将任何新对象推送到数组。然后将数组解析为JSON字符串。

NOTE: By pushing new cyclic objects to the end of the array, will force recursion until all cyclic references are removed..

注意:通过将新的循环对象推送到数组的末尾,将强制递归,直到删除所有循环引用。

Step 3: Last I parse both JSON strings into a single String;

第3步:最后我将两个JSON字符串解析为单个字符串;

Here is a javascript fiddle... https://jsfiddle.net/7uondjhe/5/

这是一个javascript小提琴... https://jsfiddle.net/7uondjhe/5/

function my_json(item) {

var parse_key = 'restore_reference', 
    stringify_key = 'is_cyclic';

var referenced_array = [];


var json_replacer = function(key,value) {

            if(typeof value == 'object' && value[stringify_key]) {
                var index = referenced_array.indexOf(value);

                if(index == -1) {
                    index = referenced_array.length;
                    referenced_array.push(value);
                };

                return {
                    [parse_key]: index
                }
            }
            return value;
}

var json_reviver = function(key, value) {

        if(typeof value == 'object' && value[parse_key] >= 0) {
                return referenced_array[value[parse_key]];
        }
        return value;
}
var unflatten_recursive = function(item, level) {
        if(!level) level = 1;
        for(var key in item) {
            if(!item.hasOwnProperty(key)) continue;
            var value = item[key];

            if(typeof value !== 'object') continue;

            if(level < 2 || !value.hasOwnProperty(parse_key)) {
                unflatten_recursive(value, level+1);
                continue;
            }

            var index = value[parse_key];
            item[key] = referenced_array[index];

        }
};


var flatten_recursive = function(item, level) {
        if(!level) level = 1;
        for(var key in item) {
            if(!item.hasOwnProperty(key)) continue;
            var value = item[key];

            if(typeof value !== 'object') continue;

            if(level < 2 || !value[stringify_key]) {
                flatten_recursive(value, level+1);
                continue;
            }

            var index = referenced_array.indexOf(value);

            if(index == -1) (item[key] = {})[parse_key] = referenced_array.push(value)-1; 
            else (item[key] = {})[parse_key] = index;
        }
};


return {

    clone: function(){ 
        return JSON.parse(JSON.stringify(item,json_replacer),json_reviver)
},

    parse: function() {
            var object_of_json_strings = JSON.parse(item);
            referenced_array = JSON.parse(object_of_json_strings.references);
            unflatten_recursive(referenced_array);
            return JSON.parse(object_of_json_strings.data,json_reviver);
    },

    stringify: function() {
            var data = JSON.stringify(item,json_replacer);
            flatten_recursive(referenced_array);
            return JSON.stringify({
                        data: data,
                        references: JSON.stringify(referenced_array)
                });
    }
}
}

There are couple of ways I know of for walking around this:

我知道有几种方法可以解决这个问题:

The first (and preferred one) is simply extracting the common code into third assembly, and make both references use that one

第一个(也是首选的)只是将公共代码提取到第三个程序集中,并使两个引用都使用那个

The second one is adding the reference as "File reference" (dll) instead of "Project reference"

第二个是将引用添加为“文件引用”(dll)而不是“项目引用”

Hope this helps

希望这可以帮助