C++按索引删除vector元素效率低于Python，求高效实现方案

你的原C++代码效率低的核心原因是：每次调用erase都会将删除位置后的所有元素向前移动，如果要删除的索引数量多或者无序，多次移动会产生大量内存拷贝，时间复杂度达到O(n*m)（n是vector大小，m是删除索引数），远不如Python列表推导式的O(n)级效率。

下面给出几种高效的实现方式：

方案1：原地删除（排序后从后往前删） #

如果必须原地修改vector，先对删除索引排序，再从后往前删除，这样每次删除后面的元素时，不会影响前面待删除索引的位置，也不需要维护偏移量remove_cnt，同时减少元素移动的次数：

#include <algorithm>
#include <vector>

// 先对删除索引排序并去重（避免重复删除同一索引）
std::sort(remove_index.begin(), remove_index.end());
auto unique_end = std::unique(remove_index.begin(), remove_index.end());
remove_index.erase(unique_end, remove_index.end());

// 反向遍历删除，从后往前删不影响前面的索引
for (auto it = remove_index.rbegin(); it != remove_index.rend(); ++it) {
    size_t idx = *it;
    if (idx < mylist.size()) { // 确保索引合法
        mylist.erase(mylist.begin() + idx);
    }
}

这种方式的时间复杂度是O(m log m + n)，排序占O(m log m)，所有erase操作总共移动的元素数是n - m，比原代码的多次移动高效得多。

方案2：创建新vector（类似Python列表推导式） #

如果允许创建新vector，这种方式通常是最高效的，直接复制需要保留的元素，避免原vector的元素移动：

2.1 哈希集合快速查找（适合删除索引数量不多的场景） #

#include <unordered_set>
#include <vector>

// 将删除索引存入哈希集合，O(1)时间查找
std::unordered_set<size_t> remove_set(remove_index.begin(), remove_index.end());
std::vector<YourType> new_mylist;
// 预分配空间，避免vector多次扩容的开销
new_mylist.reserve(mylist.size() - remove_set.size());

for (size_t i = 0; i < mylist.size(); ++i) {
    if (!remove_set.count(i)) {
        new_mylist.push_back(mylist[i]);
    }
}

// 替换原vector（swap是O(1)操作）
mylist.swap(new_mylist);

时间复杂度O(n + m)，空间复杂度O(m)，哈希查找的速度很快，适合大多数场景。

2.2 双指针遍历（适合删除索引已排序或数量极大的场景） #

如果删除索引已经排序，或者不想用哈希集合（避免哈希冲突），可以用双指针法：

#include <algorithm>
#include <vector>

// 先排序去重删除索引
std::sort(remove_index.begin(), remove_index.end());
auto unique_end = std::unique(remove_index.begin(), remove_index.end());
remove_index.erase(unique_end, remove_index.end());

std::vector<YourType> new_mylist;
new_mylist.reserve(mylist.size() - remove_index.size());

size_t remove_ptr = 0;
for (size_t i = 0; i < mylist.size(); ++i) {
    // 跳过需要删除的索引
    if (remove_ptr < remove_index.size() && i == remove_index[remove_ptr]) {
        ++remove_ptr;
    } else {
        new_mylist.push_back(mylist[i]);
    }
}

mylist.swap(new_mylist);

时间复杂度O(n + m log m)，空间复杂度主要来自排序，整体稳定高效，适合删除索引数量极大的情况。

为什么原Python代码更快？ #

Python的列表推导式本质是创建新列表，只遍历一次原列表，把需要保留的元素复制进去，和上面的方案2逻辑一致，而你的原C++代码是多次原地删除，每次都要移动大量元素，自然效率不如Python。

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