c++ - 树状队列

Question

我正在实现一个类似解释器的项目，为此我需要一个奇怪的小调度队列。因为我想尝试避免重新发明轮子，所以我希望有人能给我引用类似的结构或现有的工作。我知道我可以简单地实例化多个队列，我只是在寻找其他可能比我有更好想法的人的观点；)

我设想它可能会像这样工作:该结构是一棵单根树。你得到一种“insert_iterator”到根，然后将元素推到它上面(例如下面示例中的 a 和 b)。但是，您也可以随时将迭代器拆分为多个迭代器，从而有效地创建分支。这些分支不能再次合并到一个队列中，但是您可以从队列的前面开始弹出元素(同样，使用一种“visitor_iterator”)直到可以丢弃空分支(由您自行决定)。

            x -> y -> z
a -> b -> { g -> h -> i -> j }
            f -> b

有什么想法吗？使用队列池来实现自己的结构似乎是一个相对简单的结构，但我遵循“先思考，后编码”的策略:)

谢谢

编辑:我想我应该添加一些额外的背景信息。这与问题无关，但我认为这可能有助于澄清我的目标。非常粗略地说，这个结构背后的想法是它基本上用于调度计算......一个分支可以以 COMMIT 或 ROLLBACK 结束。如果 x -> ...、g -> ... 或 f -> ... 中的任何一个以 COMMIT 结束，则

a -> b

以及以 COMMIT 结束的分支按顺序执行。例如

x -> y -> z -> COMMIT

但是，a -> b 只会在至少有一个分支被提交时执行一次。如果所有三个分支都以 ROLLBACK 结尾，则整个树将被丢弃，包括初始事件 a -> b。

感谢您到目前为止的出色回答!我会在回到家后立即详细查看它们。

Answer 1

Boost Graph Library包含一个称为不相交集的数据结构，它模拟您在此处需要的结构(一组相互关联的集合)。

将此数据结构视为森林的另一种方式。森林是树木的不相交 union 体。