为什么擦除+删除比删除更有效

Question

我正在编写C++来解决这个问题，从leetcode：https://leetcode.com/problems/remove-element/

给定数组nums和值val，移除该值的所有实例并返回新的长度。

不要为另一个数组分配额外的空间，您必须用O（1）个额外内存修改输入数组。

元素的顺序可以更改。你在新长度之外留下什么并不重要。

您的函数应该返回长度=2，nums的前两个元素为2。

在返回长度之外留下什么并不重要。

我有两个解决方案：

解决方案A：

int removeElement(vector<int>& nums, int val) {
    nums.erase(remove(begin(nums), end(nums), val), end(nums));
    return nums.size();
}

int removeElement(vector<int>& nums, int val) {
    auto it = std::remove(nums.begin(), nums.end(), val);
    return it - nums.begin();
}

我不知道为什么remove+erase比remove快。

Answer 1

对于基本可毁类型的向量(int就是这样一种类型），erase(it,end())通常只是大小成员（或指针成员，取决于实现策略）的减量，几乎不需要时间。4毫秒是非常非常小的差别。它很容易由机器的状态引起。而且我不会指望这么小的差别会是可复制的。

如果您想真正从矢量中删除元素，请使用第一个版本。如果您真的想做std::remove做的事情（您可能不做），那么就使用第二个版本。性能不是这里的问题。