C++中基于二进制索引快速移除vector元素的最优方法

目前已有大量技术讨论聚焦于根据给定索引快速移除vector中元素的方案，本问题属于该场景的变种需求：

• 存储元素的目标vector定义如下：

std::vector <double> numbers{ 100, 200, 300, 400, 500, 600 };

• 与vector元素一一对应的二进制标记数组：

std::vector<bool> idxs{ 0, 1, 0, 1, 0, 1 };

核心需求：当vector中可能包含百万级元素时，最快移除所有索引值为0对应位置元素的方法是什么？

尝试过的错误实现：使用remove_if()编写的逻辑存在问题，代码如下：

numbers.erase(std::remove_if(numbers.begin(), numbers.end(), [](bool b)->bool
    {
        return b == 1;
    }), numbers.end());

std::remove_if的谓词参数，接收的是遍历过程中当前位置的vector元素本身，不是标记值也不是索引。上述错误代码的lambda入参声明为bool类型，和numbers存储的double类型不匹配，且全程没有关联外部的idxs标记数组，逻辑完全不成立。

百万级元素场景下性能最高的方案依然是标准库的erase-remove惯用法，只需要修正谓词逻辑，同步遍历标记数组即可。该方案为单次顺序遍历，时间复杂度O(n)，缓存友好性极强，标准库内部实现已经做了极致优化，性能优于绝大多数手写的元素搬移逻辑。

// 标记数组迭代器，和numbers同步遍历
auto idx_iter = idxs.begin();
numbers.erase(
    std::remove_if(numbers.begin(), numbers.end(), [&idx_iter](double /*当前元素值，不需要使用*/) {
        // 标记为0的元素需要移除，谓词返回true代表当前元素待删除
        bool need_remove = !(*idx_iter);
        ++idx_iter;
        return need_remove;
    }),
    numbers.end()
);

执行完成后，numbers中剩余元素为200,400,600，和标记数组中值为1的位置完全对应。

额外性能优化建议 #

• 禁止使用“遍历标记数组找到待删索引，逐个调用erase删除单个元素”的写法：该写法每次删除都会搬移后续所有元素，时间复杂度退化为O(n²)，百万级元素场景下性能会比erase-remove方案低两个数量级。
• 如果使用C++20及以上版本，可以用std::ranges::remove_if配合views::zip绑定两个容器同步遍历，代码更简洁，优化效果和传统写法一致：

  auto [res_iter, _] = std::ranges::remove_if(
      std::views::zip(numbers, idxs),
      [](const auto& elem_pair) { return !std::get<1>(elem_pair); }
  );
  numbers.erase(res_iter.base(), numbers.end());
  

• std::vector<bool>是位压缩特化容器，单元素读取性能略低于std::vector<char>，如果标记数组完全可控，换成char类型存储标记可以获得微小的性能提升，但整体差距极小，不需要特意调整。

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