高效的数据结构，用于快速随机访问、搜索、插入和删除

我正在寻找一种数据结构（或多个结构），它可以让我保留一个有序的整数列表，没有重复项，并且索引和值在同一范围内。

我需要四个主要操作才能高效，按重要性的粗略顺序排列：

1. 从给定索引中获取值
2. 查找给定值的索引
3. 在给定索引处插入值
4. 删除给定索引处的值

使用数组，我的 1 的复杂度为 O(1)，但 2 的复杂度为 O(N)，并且插入和删除的成本很高（我相信也是 O(N)）。

链表的插入和删除时间复杂度为 O(1)（一旦有了节点），但 1 和 2 的时间复杂度为 O(N)，因此抵消了收益。

我尝试保留两个数组 a[index]=value 和 b[value]=index，这将 1 和 2 变成 O(1)，但将 3 和 4 变成成本更高的操作。

有没有更适合这个的数据结构？

我会用一个红黑树 http://en.wikipedia.org/wiki/Red-black_tree将键映射到值。这为 1、3、4 提供了 O(log(n))。它还按排序顺序维护键。

对于 2，我将使用哈希表将值映射到键，这将为您提供 O(1) 性能。它还增加了 O(1) 开销，用于在红黑树中添加和删除键时保持哈希表更新。