我正在寻找一种数据结构（或多个结构），它可以让我保留一个有序的整数列表，没有重复，索引和值在同一范围内。
我需要四个主要操作才能高效，按重要性粗略排序：
使用一个数组，我在 O(1) 处有 1，但 2 是 O(N)，插入和删除是昂贵的（我相信也是 O(N)）。
链表有 O(1) 的插入和删除（一旦你有了节点），但 1 和 2 是 O(N)，因此否定了收益。
我尝试保留两个数组 a[index]=value 和 b[value]=index，它们将 1 和 2 变为 O(1)，但将 3 和 4 变为更昂贵的操作。
有没有更适合这个的数据结构？
我会使用红黑树将键映射到值。这为 1、3、4 提供了 O(log(n))。它还按排序顺序维护键。
对于 2，我将使用哈希表将值映射到键，从而为您提供 O(1) 性能。它还增加了 O(1) 开销，用于在红黑树中添加和删除键时保持哈希表更新。
使用二进制搜索的排序数组怎么样？
插入和删除很慢。但考虑到数据是纯整数这一事实，如果您使用 C 或 C++，则可以通过调用 memcpy() 来优化。如果您知道数组的最大大小，您甚至可以避免在使用数组期间进行任何内存分配，因为您可以将其预分配到最大大小。
“最佳”方法取决于您需要存储多少项目以及与查找相比您需要插入/删除的频率。如果你很少插入或删除一个排序数组，使用 O(1) 访问值肯定会更好，但如果你经常插入和删除东西，二叉树可能比数组更好。在任何情况下，对于足够小的 n，数组最有可能击败树。
如果关注存储大小，那么数组也比树好。树还需要为它们存储的每个项目分配内存，并且内存分配的开销可能很大，因为您只存储小值（整数）。
如果您从已排序的数组或带有内存（取消）分配的树中插入/删除，您可能想要分析更快的情况，即整数的复制。
我不知道您使用的是什么语言，但如果是 Java，您可以利用LinkedHashMap或类似的 Collection。它具有 List 和 Map 的所有优点，为大多数操作提供恒定的时间，并且具有大象的内存占用。:)
如果您不使用 Java，LinkedHashMap 的想法可能仍然适用于解决您的问题的可用数据结构。
使用向量进行数组访问。
使用地图作为搜索索引，将下标插入向量。
树形图怎么样？log(n) 用于描述的操作。
我非常喜欢平衡二叉树。它们有时比哈希表或其他结构慢，但它们更容易预测；它们通常O(log n)适用于所有操作。我建议使用Red-black tree或AVL tree。
How to achieve 2 with RB-trees? We can make them count their children with every insert/delete operations. This doesn't make these operationis last significantly longer. Then getting down the tree to find the i-th element is possible in log n time. But I see no implementation of this method in java nor stl.
如果您在 .NET 中工作，那么根据 MS 文档http://msdn.microsoft.com/en-us/library/f7fta44c.aspx
两者的不同之处在于内存使用和插入/移除速度。SortedList 使用的内存比 SortedDictionary 少。如果从排序数据中一次性填充 SortedList，则它比 SortedDictionary 更快。因此，这取决于哪种情况最适合您。
此外，您对 Linked List 的论点并不是真正有效的，因为它可能是 O(1) 的插入，但是您必须遍历列表才能找到插入点，所以实际上不是。