是否有 C++ 的版本？ STL 的关联数据结构针对大量部分副本进行了优化？

Question

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

然而，我担心复制每套的成本会高得令人望而却步。相反，我希望每个新创建的节点集都利用父节点集的所有适当部分。简而言之，我很高兴复制该集合的 O(log n)，但不是 O(n)。

STL 关联数据结构是否有任何变体可以提供此类部分复制优化？也许在Boost中？当然，这样的数据结构在 Haskell 或 OCaML 中实现起来很简单，但在 C++ 中则需要更多的努力。

Answer 1

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

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

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

Answer 2

这在 C++ 中几乎是不可能的，因为不可变的概念
容器不存在。你可能知道你不会做任何改变，
并且某种形式的共享表示会更好，但是
编译器和库没有，并且没有办法传达这一点
给他们。

Answer 3

每个节点都包含集合，我认为它是作为平衡实现的
二叉搜索树。此后每个节点的集合应保持固定
节点的创建，然后用于创建该节点的子节点。

这是一个非常独特的案例。我建议使用 std::vector 代替。 （不是真的！）代码创建的节点仍然可以使用set，并在最后一秒切换到vector。然而，向量更小，并且只需要少量的内存分配（如果您使用reserve，则一次），使得算法快得多 。

typedef unsigned int treekeytype;
typedef std::vector<unsigned int> minortreetype;
typedef std::pair<treekeytype, minortreetype> majornode
typedef std::set<treekeytype, minortreetype> majortype;
majortype majortree;

void func(majortype::iterator perform) {
     std::set<unsigned int> results;
     results.assign(perform->second.begin(), perform->second.end());
     majortree[perform->first+1].assign(results.begin(), results.end()); //the only change is here
     majortype::iterator next = majortree.find(perform->first+1);
     func(next);
}

您甚至可以使用 std::lower_bound 和 std::upper_bound 仍然获得 O(log(n)) 内存访问，因为它的排序方式仍然与集合相同，这样你就不会损失任何效率。只要您不需要频繁插入/移除，这就是纯粹的增益。

但是，我担心复制每套内容的成本过高。

如果这种恐惧是由于每个集合包含与其父节点几乎相同的节点而引起的，并且数据成本高昂（复制或在内存中，以两者为准），并且仅更改了少数节点，则使子树包含 std::shared_pointers 而不是数据本身。这意味着数据本身不会被复制，只会复制指针。

我意识到这不是你提出这个问题的目的，但正如 JamesKanze 所说，我知道没有这样的容器。除了可能对 STL 的 rope 类进行奇怪且危险的使用之外。请注意，我说的是 STL，而不是标准 C++ 库。他们是不同的。