是否有针对众多部分副本优化的C++ STL关联数据结构的版本？

Question

随着算法的进展,我有一棵大树.每个节点都包含set,我认为它是作为平衡二叉搜索树实现的.在创建该节点的子节点之前,每个节点的集合在该节点创建之后应保持固定.

但我担心复制每一套都非常昂贵.相反,我希望每个新创建的节点集合利用父节点集合的所有适当部分.简而言之,我很高兴复制集合的O(log n)而不是O(n).

STL的关联数据结构是否有任何变体可以提供这种部分复制优化？也许在Boost？当然,在Haskell或OCaML中实现这样的数据结构是微不足道的,但是在C++中需要更多的努力.

Answer 1

我知道建议一种不同的语言通常不会有成效，但 Haskell 的标准容器库正是这样做的。我记得看过一个视频（是 Simon Peyton Jones？），讨论了这个确切的问题，以及对于给定程序员的努力，Haskell 解决方案最终如何比 C++ 解决方案快得多。当然，这是针对一个特定问题，该问题有很多包含很多共享元素的集合。

关于这个主题有相当多的研究。如果您正在寻找关键字，我建议搜索“函数式数据结构”而不是“不可变数据结构”，因为大多数函数式范例通常受益于不变性。像手指树这样的结构正是为了解决这个问题而开发的。

据我所知，没有 C++ 库可以实现这些数据结构。没有什么可以阻止您阅读相关论文（或 Haskell 源代码，大约 1k 行用于Data.Set包含测试）并自己实现它，但我知道这不是您想听到的。您还需要对共享节点进行某种引用计数，对于如此深的结构，这可能比简单的垃圾收集器具有更高的开销。