当使用引用计数时，处理循环引用的可能解决方案/技术有哪些？
最为人所知的解决方案是使用弱引用，然而许多与此主题相关的文章表明还有其他方法，但它们不断重复弱引用的示例。这让我想知道，这些其他方法是什么？
我并不是在询问替代引用计数的方案，而是在使用引用计数时解决循环引用的方案。
这个问题不涉及任何特定的问题/实现/语言，而是一个普遍性的问题。
有哪些解决循环引用的方案？
16
- OB OB
1
23对于循环引用的解决方案，请参见这里。 :-) - Chris W. Rea
13个回答
11
多年来，我以各种方式研究了这个问题，唯一的解决方案是重新设计我的解决方案，不使用循环引用。
编辑：
你能详细说明吗？例如，在子项需要知道/访问父项的父子关系时，您将如何处理？– OB OB
正如我所说，除非您使用可以安全处理此类结构的运行时，否则避免使用这样的结构是唯一的好方法。
话虽如此，如果您必须拥有子节点了解父节点的树/父子数据结构，那么您将不得不手动实现自己的拆卸序列（即在任何析构函数之外调用），从根部（或您想要修剪的分支）开始对树进行深度优先搜索，以便从叶子中删除引用。
这变得复杂而繁琐，因此我认为唯一的解决方案是完全避免使用它。
- Randolpho
4
1+1 我也是。有关示例方法，请参见我在另一个问题上的答案：http://stackoverflow.com/questions/1047877/how-i-do-for-work-with-objects-with-composition/1047956#1047956 - Fredrik Mörk
2你能详细说明一下吗？例如，当子级需要了解/访问父级时，您会如何处理父子关系？ - OB OB
@ChrisW：原问题中提到了弱引用。OB OB正在寻找替代方案。 - Randolpho
如果您将父级链接明确标记为“parent”，那么您就知道它不是子链接，该怎么办？ - Adrian
5
这里是我见过的一种解决方案：
为每个对象添加一个方法，告诉它释放对其他对象的引用，比如称之为Teardown()。
然后您必须知道谁“拥有”每个对象，并且对象的所有者在完成对其的操作后必须调用Teardown()。
如果存在循环引用，比如A <-> B，并且C拥有A，则当调用C的Teardown()时，它会调用A的Teardown，这将调用B的Teardown，B然后释放其对A的引用，A然后释放其对B的引用（销毁B），然后C释放其对A的引用（销毁A）。
- Alex Black
5
我认为在大多数情况下，您希望从对象的析构函数中调用teardown。显式调用teardown有点类似于手动销毁对象。（当拆除对象时，如何知道没有其他人在使用该对象？） - OB OB
是的，你是对的，在对象的析构函数中调用 Teardown。然而，调用 Teardown 并不一定会销毁对象，如果其他人仍然持有该对象的引用，则它将继续存在。只有当引用计数达到0时，对象才会被销毁。 - waterlooalex
让我来纠正一下：调用对象的 Teardown 方法并不一定会销毁它，但是它意味着该对象不再有用，这与调用 Dispose() 方法类似。由于该对象已释放了对其依赖对象的引用，因此不能安全地使用它。 - waterlooalex
@Alex Black：如果有两个对象 C 和 D 都拥有 A，那么当 C 调用 Teardown()，而 D 仍然希望 A 存活时怎么办？你必须在对象 A 中设置一个计数器，忽略除最后一次外的所有 Teardown 调用。 - alpav
@alpav：我们所做的是避免了这种情况。只有C或D中的一个可以拥有A。比如说，如果C拥有A而D没有，但是D有对A的引用，那么你必须设计你的代码，使得在C消失后D不能再访问A，其中一种方法是让D归C所有。 - waterlooalex
2
我猜垃圾回收器使用的另一种方法是“标记和清除”：
- 在每个对象实例中设置一个标记
- 遍历可到达的每个实例的图形，清除该标记
- 仍然带有该标记的每个剩余实例都是不可访问的，即使其中一些实例彼此具有循环引用。
- ChrisW
5
3我不是在寻找替代引用计数的方法，而是想寻求解决循环引用问题的方案。请注意保持原意和简洁易懂，不要添加任何解释或其他内容。 - OB OB
你试图解决的循环引用问题是什么？是垃圾回收的问题，还是其他问题？如果问题是垃圾回收，那么替代方案不就等同于解决方案吗？ - ChrisW
@ChrisW：是的，问题通常出在垃圾回收上。有许多垃圾回收方法。其中之一是引用计数，另一个是标记-清除。标记-清除是引用计数的替代方法示例，而弱引用则是解决循环引用问题的方法示例，同时仍使用引用计数作为垃圾回收方法。希望你能看出区别。 - OB OB
如果您想仅使用一流的引用来完成此操作，那么您需要一种检测循环引用的方法。Alex Black的方法可以实现这一点：假装推迟了所有被引用对象所指向的内容，如果在这个试验中导致原始对象的被取消引用，则它就是一个循环引用。我不确定，但也许这是一种昂贵的方法：比标记和清除法更昂贵，特别是在病态/长链情况下。 - ChrisW
1你实际上可以将垃圾收集器与引用计数结合使用。如果可能的话，引用计数会立即清理掉对象，而垃圾收集器处理循环引用（如果大多数对象都通过引用计数自动删除，则垃圾收集器需要处理的工作量更少！） - Grant Peters
2
我想提出一种稍有不同的方法，我不知道它是否有任何正式名称：
对象本身没有引用计数器。相反，一个或多个对象的组具有整个组的单个引用计数器，该计数器定义了组中所有对象的生命周期。
类似地，引用与对象共享组，或属于空组。
对对象的引用仅在它是组外部的引用时才会影响（对象的）组的引用计数。
如果两个对象形成循环引用，则它们应该成为同一组的一部分。如果两个组创建循环引用，则它们应该合并为一个组。
更大的组允许更多的引用自由度，但组中的对象在不需要时可能会保持活动状态。
对象本身没有引用计数器。相反，一个或多个对象的组具有整个组的单个引用计数器，该计数器定义了组中所有对象的生命周期。
类似地，引用与对象共享组，或属于空组。
对对象的引用仅在它是组外部的引用时才会影响（对象的）组的引用计数。
如果两个对象形成循环引用，则它们应该成为同一组的一部分。如果两个组创建循环引用，则它们应该合并为一个组。
更大的组允许更多的引用自由度，但组中的对象在不需要时可能会保持活动状态。
- OB OB
3
这相当于说明你的引用中哪些是“弱”的：如果一个引用指向同一组中的对象，则该引用是“弱”的；否则，它指向不同组中的对象，因此该引用是“强”的。 - ChrisW
1是的，只有当您具有对持有对对象B的弱引用的对象A的外部引用，并且未以其他方式引用B时，B仍将保持活动状态（这是所需的行为）。您无法使用“普通”弱引用实现此目的。 - OB OB
听起来很像为应用程序的不同部分拥有离散内存池（这样您可以一次性删除整个池，然后只需清理指向该池的指针），这在游戏中很常见，并添加引用计数（我猜这将解决清理指针的问题）。 - Grant Peters
2
将事物放入层次结构中
拥有弱引用是一种解决方案。我知道的另外一个解决方案是尽可能避免循环拥有引用。如果您拥有指向对象的共享指针，则从语义上来说，这意味着您以共享的方式拥有该对象。如果您只以这种方式使用共享指针，则几乎不可能出现循环引用。通常不会出现对象彼此循环拥有的情况，而是通过分层树状结构连接的。下面我将描述这种情况。
处理树形结构
如果您有一个具有父子关系的对象树，则子对象不需要拥有其父对象的所有权引用，因为父对象总是会比子对象存活更长时间。因此，非所有权的原始反向指针就足够了。对于指向它们所在容器的元素也适用此规则。容器应尽可能使用唯一指针或值，而不是共享指针。
模拟垃圾回收
如果您有一堆可以随意相互引用的对象，并且您希望在某些对象不可达时立即清理它们，则您可能希望为它们构建一个容器和一个根引用数组，以便手动进行垃圾回收。
使用唯一指针、原始指针和值
在现实世界中，我发现共享指针的实际用途非常有限，应该避免使用，而应优先选择唯一指针、原始指针或更好的只使用值类型。通常情况下，共享指针是在多个引用指向共享变量时使用的。共享会引起摩擦和争用，因此应尽可能避免使用它。唯一指针和非所有权的原始指针和/或值比较容易理解。但是，有时需要使用共享指针。通常使用共享指针来延长对象的生存期，这通常不会导致循环引用。
底线
请谨慎使用共享指针。优先使用唯一指针、非所有权的原始指针或纯值。共享指针表示共享所有权。请按此方式使用。将您的对象按照层次结构排序。处于层次结构中的子对象或同级对象不应相互拥有共享所有权引用，也不应该拥有指向其父对象的共享所有权引用，而应使用非所有权的原始指针代替。
- Ralph Tandetzky
1
Y Combinator
我曾经写过一种编程语言，其中每个对象都是不可变的。因此，一个对象只能包含指向早期创建的对象的指针。由于所有引用都指向过去，因此不可能存在任何循环引用，并且引用计数是管理内存的完全可行的方法。
那么问题来了，“如何创建自引用的数据结构而不产生循环引用？”好吧，函数式编程一直在使用固定点/Y组合子来编写递归函数，当您只能引用先前编写的函数时。请参见：https://en.wikipedia.org/wiki/Fixed-point_combinator
那个维基百科页面很复杂，但概念并不那么复杂。就数据结构而言，它的工作原理如下：
假设您想要创建一个Map<String,Object>，其中映射中的值可以引用映射中的其他值。那么，您不是实际存储这些对象，而是存储函数，这些函数会根据给定映射的指针按需生成这些对象。
object = map.get(key)，这将调用一个私有方法 _getDefinition(key)，该方法返回此函数并调用它。Object get(String key) {
var definition = _getDefinition(key);
return definition == null ? null : definition(this);
}
因此，该映射具有对定义值函数的引用。该函数不需要引用映射，因为它将作为参数传递映射。
当调用该定义时，它返回一个新对象，该对象确实在某个地方具有指向映射的指针，但是映射本身没有指向此对象的指针，因此不存在循环引用。
- Matt Timmermans
1
没有人提到过一类算法，它们通过扫描可能存在循环的数据集合来检测和回收循环引用，而不是通过标记和扫描寻找不可回收的数据。
更详细地说，一种生成可能节点集合的想法是：对引用计数进行递减操作，但递减后未达到零。只有发生这种情况的节点才可能是从根节点截断循环的点。
Python 和 PHP 都有实现这种算法的垃圾回收器。
我仍在努力理解这个算法，因为有高级版本声称能够在程序不停止的情况下并行执行...
无论如何，这并不简单，需要多次扫描、额外的引用计数器以及在“试验”中递减元素（在额外计数器中），以查看自引用数据是否最终可回收。
更详细地说，一种生成可能节点集合的想法是：对引用计数进行递减操作，但递减后未达到零。只有发生这种情况的节点才可能是从根节点截断循环的点。
Python 和 PHP 都有实现这种算法的垃圾回收器。
我仍在努力理解这个算法，因为有高级版本声称能够在程序不停止的情况下并行执行...
无论如何，这并不简单，需要多次扫描、额外的引用计数器以及在“试验”中递减元素（在额外计数器中），以查看自引用数据是否最终可回收。
一些论文： "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
参考计数还有很多其他主题，例如减少或消除参考计数中交错指令的奇特方法。我可以想到三种方法，其中两种已经被写出。
- Josh S
0
我也在寻找解决循环引用计数问题的好方法。
我从魔兽世界中借鉴了一个处理成就的API，当我将其隐式转换为接口时，意识到我有循环引用。
注意：如果您不喜欢成就，可以将单词成就替换为订单。但是谁不喜欢成就呢？
这里有成就本身：
IAchievement = interface(IUnknown)
function GetName: string;
function GetDescription: string;
function GetPoints: Integer;
function GetCompleted: Boolean;
function GetCriteriaCount: Integer;
function GetCriteria(Index: Integer): IAchievementCriteria;
end;
然后就是成就的标准清单：
IAchievementCriteria = interface(IUnknown)
function GetDescription: string;
function GetCompleted: Boolean;
function GetQuantity: Integer;
function GetRequiredQuantity: Integer;
end;
所有成就都会在中央的
IAchievementController注册自己：IAchievementController = interface
{
procedure RegisterAchievement(Achievement: IAchievement);
procedure UnregisterAchievement(Achievement: IAchievement);
}
然后控制器可以用来获取所有成就的列表：
IAchievementController = interface
{
procedure RegisterAchievement(Achievement: IAchievement);
procedure UnregisterAchievement(Achievement: IAchievement);
function GetAchievementCount(): Integer;
function GetAchievement(Index: Integer): IAchievement;
}
原本的想法是，当发生有趣的事情时，系统会调用 IAchievementController 并通知他们发生了什么有趣的事情：
IAchievementController = interface
{
...
procedure Notify(eventType: Integer; gParam: TGUID; nParam: Integer);
}
当一个事件发生时，控制器将遍历每个子元素，并通过它们自己的Notify方法通知它们：
IAchievement = interface(IUnknown)
function GetName: string;
...
function GetCriteriaCount: Integer;
function GetCriteria(Index: Integer): IAchievementCriteria;
procedure Notify(eventType: Integer; gParam: TGUID; nParam: Integer);
end;
如果“成就”对象决定事件是它感兴趣的内容，它将通知“它的”子标准：
IAchievementCriteria = interface(IUnknown)
function GetDescription: string;
...
procedure Notify(eventType: Integer; gParam: TGUID; nParam: Integer);
end;
到目前为止，依赖图一直都是自顶向下的：
IAchievementController --> IAchievement --> IAchievementCriteria
但是当达成成就的标准时会发生什么呢？`Criteria`对象必须通知其父级`Achievement`：
IAchievementController --> IAchievement --> IAchievementCriteria
^ |
| |
+----------------------+
这意味着
Criteria需要引用其父级；现在它们互相引用- 内存泄漏。当一个成就最终完成时，它将不得不通知其父控制器，以便更新视图：
IAchievementController --> IAchievement --> IAchievementCriteria
^ | ^ |
| | | |
+----------------------+ +----------------------+
现在Controller和它的子类Achievements相互引用，导致更多的内存泄漏。
我认为也许Criteria对象可以通知Controller，从而删除对其父级的引用。但我们仍然有一个循环引用，只是时间更长了：
IAchievementController --> IAchievement --> IAchievementCriteria
^ | |
| | |
+<---------------------+ |
| |
+-------------------------------------------------+
魔兽世界的解决方案
现在，魔兽世界的 API 并不友好于面向对象编程。但它确实解决了任何循环引用的问题：
不要传递对
Controller的引用。有一个单一的、全局的、单例的Controller类。这样，成就就不必“引用”控制器，只需“使用”它。缺点：使测试和模拟变得不可能——因为你必须有一个已知的全局变量。
成就不知道它的标准列表。如果你想要
Achievement的Criteria，你可以向Controller询问：IAchievementController = interface(IUnknown) function GetAchievementCriteriaCount(AchievementGUID: TGUID): Integer; function GetAchievementCriteria(Index: Integer): IAchievementCriteria; end;缺点：一个
Achievement不能再决定将通知传递给它的Criteria，因为它没有任何标准。现在你必须向Controller注册Criteria。当一个
Criteria完成时，它会通知Controller，然后Controller会通知Achievement：IAchievementController-->IAchievement IAchievementCriteria ^ | | | +----------------------------------------------+缺点：让我头疼。
我相信，与将整个系统重新架构成一个非常混乱的 API 相比，使用 Teardown 方法肯定更加理想。
但是，就像你在思考的那样，也许有更好的方法。
- Ian Boyd
0
如果您需要存储循环数据，以便将其快照到字符串中，
我会将一个循环布尔值附加到任何可能是循环的对象上。
步骤1： 在将数据解析为JSON字符串时，我将任何未使用过的object.is_cyclic推入数组并将索引保存到字符串中。（任何已使用的对象都将替换为现有索引）。
步骤2：我遍历对象数组，将任何children.is_cyclic设置为指定的索引，或将任何新对象推入数组。然后将数组解析为JSON字符串。
注意：通过将新的循环对象推到数组末尾，将强制递归，直到删除所有循环引用为止。
步骤3：最后，我将两个JSON字符串解析为单个字符串；
这里是一个JavaScript fiddle... 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)
});
}
}
}
- anonymous
0
我一直在重新设计以避免这个问题。其中一个常见的情况是父子关系，其中子项需要了解父项。有两种解决方案：
将父项转换为服务，然后父项不再知道子项，当没有更多子项或主程序删除父项引用时，父项就会死亡。
如果父项必须访问子项，则在父项上有一个注册方法，该方法接受一个指针，该指针不是引用计数的，例如对象指针，以及相应的注销方法。子项将需要调用注册和注销方法。当父项需要访问子项时，它将把对象指针强制转换为引用计数接口。
- William Egge
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接