c++ - 为什么 erase+remove 比 remove 更高效

Question

我正在编写 C++ 代码来解决 Leetcode 中的这个问题:https://leetcode.com/problems/remove-element/

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example 1:

Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.

我有两个解决方案:

解决方案 A:

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

解决方案 B:

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

在我看来，方案B应该比方案A快。然而，结果却恰恰相反:

解决方案 A 花费了 0 毫秒，而解决方案 B 花费了 4 毫秒。

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

Answer 1

对于普通可破坏类型的 vector (int 就是这样一种类型)，erase(it, end()) 通常只是一个 size 成员的减量(或指针成员，取决于实现策略)几乎不需要时间。 4 毫秒是一个非常非常小的差异。它很容易由机器的状态引起。而且我不希望如此小的差异能够重现。

如果你真的想从 vector 中删除元素，请使用第一个版本。如果您真的想做 std::remove 做的事情(您可能不想做)，请使用第二个版本。性能不是这里的问题。