c++ - 随机访问时至少为 O(ln N) 且删除时至少为 O(ln N) 的数据结构 [NOT DUPLICATE]

Question

没有标准的容器可以开箱即用地提供这种保证，需要一些额外的操作（例如，像 Jerry Coffin 建议的那样），它不是重复的。

---

是否有任何现成的数据结构/容器，在随机访问时至少为 O(ln N)，在删除时至少为 O(ln N)？（stl/升压/等）

容器内元素的顺序并不重要。

此类操作可能会连续发生，例如：

1. 按索引随机访问（索引也是随机的， rand()%size() ）

2. 删除此项目

3. 按索引随机访问（索引也是随机的， rand()%size() ）

4. 删除此项目

ETC...

Answer 1

由于您说排序无关紧要，因此您可以使用向量在恒定时间内完成这两项操作。

随机访问（显然）是恒定时间。

可以通过将要删除的元素与最后一个元素交换，然后删除最后一个元素来完成恒定时间内的删除。