需要帮助在 C++ 中选择正确的数据结构

Question

仅限 C++

我有一个按一定顺序维护的元素列表。顺序是动态改变的，并且元素可以随时添加/删除。我需要有效地添加/删除或修改元素位置，还需要通过元素的位置随机访问元素。

例如：- 有 5 个元素 - A、B、C、D、E

事件1：-添加A和B
第 0 个位置 - A
第 1 个位置 - B

事件2：- 在第 1 个位置添加 C
0 - A
1 - C
2 - B

事件3：- 将A移至1
0 - C
1 - A
2 - B

为了支持这一点，我可以使用 std::list （插入/删除在任何地方都是恒定的），但没有随机访问。

如果我使用 std::deque/std::vector，则存在随机访问，但移位元素需要线性时间。

任何人都可以为该型号推荐一款 DS 吗？ 是否可以仅使用一台 DS 来完成此操作，还是我需要使用多个 DS。任何建议将不胜感激。

Answer 1

平衡二叉搜索树，其中元素由其索引隐式键控（通过维护子树大小），可用于实现动态数组，该数组允许在任意索引处插入和删除以及范围更新和查询

O(log N)

。