6

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

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

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

4

3 回答 3

1

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

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

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

于 2011-10-04T17:06:04.070 回答
0

这在 C++ 中几乎是不可能的，因为不存在不可变容器的概念。您可能知道您不会进行任何更改，并且某种共享表示会更可取，但编译器和库不会，并且无法与他们沟通。

于 2011-10-04T16:31:56.060 回答
0

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

这是一个非常独特的案例。我建议改用 std::vector 。（真的没有！）创建节点的代码仍然可以使用 a set，并在最后一秒切换到 a vector。但是，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_boundandstd::upper_bound仍然获得 O(log(n)) 内存访问，因为它的排序仍然与集合相同，因此您不会失去任何效率。只要您不需要频繁插入/删除，这就是纯粹的收益。

然而，我担心复制每套产品的成本过高。

如果这种担心是因为每个集合都包含与其父节点大部分相同的节点，并且数据成本很高（复制或在内存中，无论哪个），只有少数节点发生了变化，那么让子树包含std::shared_pointers而不是数据本身。这意味着数据本身不会被复制，只有指针。

我意识到这不是您提出问题的目的，但正如 JamesKanze 所说，我不知道这样的容器。除了可能是对 STLrope类的奇怪和危险的使用。请注意，我说的是 STL，而不是标准 C++ 库。他们是不同的。

于 2011-10-04T17:05:27.727 回答