在 C++ 中以 O(log n) 查找具有查找和插入/删除的索引容器

Question

我正在 C++ 中寻找一个索引容器，它具有以下属性：

• 获取 O(log n) 中第 k 个位置的元素
• 在 O(log n) 中的第 k 个位置插入一个元素
• 删除 O(log n) 中第 k 个位置的元素

我正在考虑使用类似的地图的解决方法，但我无法弄清楚。Java 中还有一个名为TreeList的容器，它具有上述属性。

Answer 1

您需要一个订单统计树。它是一个二叉搜索树，可以跟踪每个子树的大小，并且该信息可用于在对数时间内执行您需要的操作。C++标准库没有实现这样的数据结构，所以需要自己实现或者使用其他库。在GNU基于策略的数据结构扩展包括这一点。