在C++中的持久化数据结构

Question

在C++中的持久化数据结构

c++clojurepersistenceimmutability

21

是否有类似Clojure中的持久化数据结构在C++中的实现？

- Miguel

1

C++没有垃圾回收机制，这使得构建此类结构变得非常复杂。如果您不关心内存泄漏（或已经集成了垃圾回收器），那么就很容易了。 - Greg Hewgill

2

哇，冷静点，兄弟。查找“Clojure”并不难；而且我通常不会夸耀自己没有听说过一门处于函数式编程前沿的语言。虽然我不是它的铁粉，但我觉得提到它的问题被贬低是很奇怪的。（尽管我完全赞同你建议重新评估需求，而不是把另一种语言的风格硬塞到C++中）。 - Jonathan Sterling

相关：https://dev59.com/NHE85IYBdhLWcg3wejfn，https://dev59.com/XnVC5IYBdhLWcg3wZwXj - amit kumar

1

持久化数据结构无法创建循环。例如，如果您创建了A，则可以创建指向A的B，但是您需要修改A才能创建循环。持久化数据结构是不可变的，因此在C++中实现它们只需要一个简单的引用计数即可。 - ivant

3个回答

2

~~实现持久化数据结构的主要难点确实是缺乏垃圾回收机制。~~

如果没有适当的垃圾回收机制，那么你可以得到一个糟糕的机制（即引用计数），但这意味着你需要特别小心地避免创建循环引用。

这改变了结构的核心。例如，考虑二叉树。如果你创建一个节点的新版本，那么你需要其父节点的新版本来访问它（等等...）。现在，如果关系是双向的（孩子<->父母），那么实际上你将复制整个结构。这意味着你将有一个父亲->孩子的关系，或者反过来（不太常见）。

我可以想到实现二叉树或B-Tree。但对于如何获得适当的数组，我几乎看不到头绪。

另一方面，在多线程环境中拥有高效的持久化数据结构确实是非常重要的。

- Matthieu M.

1

循环引用在数据结构中（例如二叉树）并不是一个问题。但在持久化集合中，节点不能引用其父节点；如果这样做，每次写操作都会使整个树失效。 - Joshua Warner

@JoshuaWarner: 我同意，我在下一个段落中谈到了这一点，但没有得出明显的结论：如果构建良好，则不可能存在循环引用，并且没有循环引用时，shared_ptr方案就足够了，无需全面使用垃圾回收器。 - Matthieu M.

0

如果我理解问题正确，您所寻求的是在不实际支付复制费用的情况下复制对象，只有在需要时才进行。对任一对象的更改都不会损坏另一个对象。这被称为“写时复制”。

如果这就是您要找的，那么可以使用共享指针（请参见Boost中的shared_ptr作为一种实现）相当容易地在C++中实现。最初，副本将与源共享所有内容，但一旦进行更改，对象共享指针的相关部分将被替换为指向新创建的深度复制对象的其他共享指针。

（我意识到这个解释很模糊 - 如果这确实是您的意思，答案可以详细说明）。

- Hexagon

Copy-on-write（写时复制）是@Miguel所寻找的功能，但它会导致集合在重复写入时性能表现不佳。 - Joshua Warner

在写时复制中，“深拷贝”使其不适用于函数式编程。函数式编程中的数据结构是持久化数据结构。由于它们是不可变的，如果您想要“修改”它，则会创建一个新的“副本”（新版本），旧版本仍然可用。当只有部分结构不同（例如列表的“头”）时，制作整个副本将浪费内存。相反，两个版本共享公共部分（例如列表的“尾”）。 - Siu Ching Pong -Asuka Kenji-

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user4842163 · Accepted Answer

我自己写了一个，但是 immer库是一个相当全面的例子，它专门受到clojure的启发。几年前，我听了约翰·卡马克的演讲后，他一直在跳上函数式编程的列车，我感到非常兴奋，然后自己写了一个。他似乎能够想象一个围绕不可变数据结构旋转的游戏引擎。虽然他没有详细说明，而且似乎只是他脑海中的一个模糊想法，但他认真考虑这个想法，并且似乎认为开销不会大幅削减帧速率足以让我对探索这个想法感到兴奋。

实际上，我将其用作某种优化细节，这可能看起来有些矛盾（不可变性会有开销），但我指的是特定的上下文。如果我绝对想要做到这一点：

// We only need to change a small part of this huge data structure.
HugeDataStructure transform(HugeDataStructure input);

我希望这个函数不会产生任何副作用，以便它能够线程安全且永远不容易被误用。因此，我别无选择，只能复制庞大的数据结构（可能跨越一千兆字节）。

在这种情况下，拥有一小组不可变数据结构非常有帮助，因为它通过仅浅复制和引用未更改的部分使上述情况相对便宜。话虽如此，我主要使用一个不可变数据结构，它基本上是一个随机访问序列，如下所示：

正如其他人提到的那样，确实需要一些关注和调整以及全面的测试和许多VTune会话来使其线程安全和高效，但是在我付出努力之后，它确实使事情变得更加容易。

除了使用这些结构创建无副作用函数时的自动线程安全性外，您还可以获得像非破坏性编辑、轻松撤消系统、轻松异常安全性（无需通过作用域保护回滚引起的任何副作用的函数来回滚），以及允许用户复制和粘贴数据和实例而不占用太多内存，直到/除非他们修改所粘贴内容的额外奖励。实际上，我发现这些奖励在日常使用中比线程安全性更有用。

我使用“暂态”（又名“生成器”）作为表达对数据结构的更改的方法，如下所示：

Immutable transform(Immutable input)
{
    Transient transient(input);

    // make changes to mutable transient.
    ...

    // Commit the changes to get a new immutable
    // (this does not touch the input).
    return transient.commit();
}

我甚至有一个不可变的图像库，用于图像编辑，以使非破坏性编辑变得微不足道。它使用类似上面结构的策略，通过将图像视为平铺来实现：

当一个瞬态被修改并且我们得到一个新的不可变对象时，只有改变的部分会被唯一化。其余的瓦片将进行浅复制（仅为32位索引）。

我在像网格和视频处理这样的性能关键领域确实使用它们。需要微调每个块应存储多少数据（太多会浪费处理和内存，深度复制太多数据；太少会浪费处理和内存，浅层复制太多指针并频繁线程锁定）。

我不使用它们进行光线追踪，因为那是最极端的性能关键领域之一，即使有微小的开销也会影响用户体验（他们实际上会对2％范围内的性能差异进行基准测试和注意）。但大多数情况下，它们足够高效，并且当您可以整体左右地复制这些巨大的数据结构以简化线程安全、撤消系统、非破坏性编辑等时，这是一个相当棒的好处，而无需担心爆炸性的内存使用和明显的延迟。