具有快速插入/删除的阵列

Question

我正在寻找一个存储元素数组并支持这些操作的数据结构:

1. 访问给定索引处的元素
2. 在给定索引处添加或删除元素(从而转移以下元素)

数组在O(1)中执行第一个操作,但第二个操作采用O(n),而链接列表执行相反的操作.是否存在中间数据结构？比方说,可以在O(lg n)或O(n ^ epsilon)"最坏情况"时间内进行两种操作？

请注意,我不是要求平衡的二叉搜索树.每次添加/删除新元素时,键(索引)都会被更改和移位.例如,删除最小元素会将所有其他元素的索引减少1.

Answer 1

有“AVL-Array”，一种 STL 风格的容器，可以在O(log n)中执行这两个操作。

它建立在 AVL 树之上，但它仍然不是关联容器，而是顺序容器。
它支持[]带有vector语义的索引访问。

请注意，AVL-Array 并没有实现搜索树，而是实现了一个恰好
以树形式出现的顺序容器。索引、迭代、插入和删除都执行您期望的
操作vector。

你可以在这里找到它