c++ - C++中的订单维护数据结构

Question

我正在寻找一种可以有效解决 Order-maintenance problem 的数据结构.换句话说，我需要高效地

• 插入(在中间)，
• 删除(在中间)，
• 比较容器中元素的位置。

我找到了讨论这个问题的好文章:

• Two Algorithms for Maintaining Order in a List ,
• Two Simplified Algorithms for Maintaining Order in a List .

算法非常有效(对于所有操作，某些状态为 O(1))，但它们似乎并不简单，我想知道是否有这些或类似数据结构的开源 C++ 实现.

我见过 related topic ，建议了一些时间复杂度为 O(log n) 的更简单的方法，用于所有操作，但这里我正在寻找现有的实现。

如果有其他一些流行语言的示例，那也很好，这样我至少可以在尝试自己实现之前进行试验。

详情

我要去

• 维护一个指向对象的指针列表，
• 有时我需要更改对象的顺序(删除+插入)，
• 给定一个对象子集，我需要能够快速对它们进行排序并以正确的顺序处理它们。

注意

标准排序容器(std::set、std::map)不是我想要的，因为它们会为我维持秩序，但我需要自己订购元素。类似于我对 std::list 所做的，但位置比较将是线性的，这是 Not Acceptable 。

Answer 1

如果您同时在寻找易于实现且高效的解决方案，您可以使用平衡二叉搜索树(AVL 或红黑树)构建此结构。您可以按如下方式实现操作:

• insert(X, Y)(按总顺序在 Y 之后立即插入 X) - 如果为 X 没有右 child 设置X的右 child 为Y，否则让Z为 Root过的树的最左边节点X.right(表示最低的 Z = X.right.left.left.left... 不为 NULL)并将其设置为 的左 child Z 为 Y。必要时保持平衡。您可以看到总复杂度为 O(log n)。
• delete(X) - 只需从树中删除节点 X 即可。复杂度 O(log n)。
• compare(X,Y) - 找到从 X 到根的路径以及从 Y 到根的路径。您可以从这两条路径中找到 Z ，即 X 和 Y 的最低共同祖先。现在，您可以比较 X 和 Y 取决于它们是在 Z 的左子树还是右子树(它们不能从那时起，Z 将不再是它们的最低共同祖先)。复杂度 O(log n)。

所以你可以看到这种实现的优点是所有操作的复杂度都是 O(log n) 并且很容易实现。