【面试题】如何高效删除 C++ vector 中所有下标为偶数的元素？

在 C++ 中，若要高效删除 std::vector 里所有下标为偶数的元素，可以采用以下几种方法

方法一：反向遍历删除元素

从向量的末尾开始反向遍历，这样在删除元素时不会影响后续元素的索引。此方法的时间复杂度为 ，因为每个元素最多被访问和移动一次。

#include <iostream>
#include <vector>void removeEvenIndexElements(std::vector<int>& vec) {for (auto it = vec.rbegin(); it != vec.rend(); ++it) {if ((vec.rend() - it - 1) % 2 == 0) {vec.erase((it + 1).base());}}
}int main() {std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};removeEvenIndexElements(vec);for (int num : vec) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

代码解释：

1. 反向迭代器：使用 rbegin() 和 rend() 进行反向遍历，这样删除元素时不会影响后续元素的索引。
2. 计算原始索引：通过 (vec.rend() - it - 1) 计算当前元素在正向迭代时的索引。
3. 删除元素：若索引为偶数，则使用 erase() 函数删除该元素。

方法二：使用 std::remove_if 和 erase 组合

这种方法利用 std::remove_if 将需要保留的元素移动到向量的前面，然后使用 erase 删除多余的元素。时间复杂度同样为 

#include <iostream>
#include <vector>
#include <algorithm>void removeEvenIndexElements(std::vector<int>& vec) {auto newEnd = std::remove_if(vec.begin(), vec.end(), [&](const auto&, auto index = 0) mutable {return (index++) % 2 == 0;});vec.erase(newEnd, vec.end());
}int main() {std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};removeEvenIndexElements(vec);for (int num : vec) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

代码解释：

1. std::remove_if：使用 Lambda 表达式作为谓词，判断元素的索引是否为偶数。若为偶数，则将该元素移动到向量的末尾。
2. erase：删除 newEnd 到向量末尾的所有元素。

性能比较

两种方法的时间复杂度均为 ，但反向遍历删除元素的方法在删除元素时可能会有更多的元素移动操作，而 std::remove_if 方法则是先将需要保留的元素移动到前面，最后一次性删除多余的元素，因此在某些情况下，std::remove_if 方法可能会更高效。

C/C++学习网站

C/C++学习君羊：1021486511