满足有序迭代、索引访问、值删除的高效C++数据结构选型

结合你的需求和性能要求，最优选择是保留原std::vector<int>存储元素，同时额外维护一个大小为n的数组（比如std::vector<int> val_to_idx），用来记录每个值对应的当前索引。这个组合能让三个核心操作都达到O(1)或近似O(1)的时间复杂度，完美适配你的场景。

各需求的实现方式 #

• 顺序迭代：直接遍历原vector即可，和你现在的用法完全一致，时间复杂度O(n)，符合要求。
• 索引访问特定元素：直接用vec[idx]，O(1)时间，原生vector的优势完全保留。
• 按值删除特定元素：假设要删除的值是target，步骤如下：
  1. 通过反向数组拿到target的当前索引：int idx = val_to_idx[target];
  2. 把vector的最后一个元素last_val = vec.back()移动到idx的位置：vec[idx] = last_val;
  3. 更新反向数组中last_val对应的索引：val_to_idx[last_val] = idx;
  4. 调用vec.pop_back()（因为最大大小固定，只是逻辑删除，也可以标记无效，但pop_back()是O(1)操作）
     整个过程是O(1)时间，彻底解决了原生vector按值删除需要遍历找索引（O(n)）和移动元素（O(n)）的性能问题。

初始化步骤 #

以你的示例vec = {4, 1, 2, 0, 3}为例，初始化反向数组时：

std::vector<int> val_to_idx(n);
for (int i = 0; i < n; ++i) {
    val_to_idx[vec[i]] = i;
}

这样val_to_idx[4] = 0，val_to_idx[1] = 1，以此类推，后续删除操作时动态更新这个数组即可。

为什么这个方案最优？ #

• 完全保留了vector的顺序迭代和随机访问优势，这两个操作的性能是所有容器里顶尖的。
• 反向数组的额外空间开销是O(n)，对于存储0到n-1的场景来说完全可接受，而且是一次性初始化，后续维护成本极低。
• 按值删除操作从原生vector的O(n)降到了O(1)，完美匹配你对性能的要求。
• 因为从不添加元素，pop_back()是安全且高效的，不需要处理扩容或插入的复杂逻辑。

内容的提问来源于stack exchange，提问作者s1624210