如何在迭代时从向量中删除元素？

Question

我想使用擦除方法从向量中清除元素。 但这里的问题是，不能保证该元素在向量中只出现一次。 它可能会出现多次，我需要清除所有这些。 我的代码是这样的：

void erase(std::vector<int>& myNumbers_in, int number_in)
{
    std::vector<int>::iterator iter = myNumbers_in.begin();
    std::vector<int>::iterator endIter = myNumbers_in.end();
    for(; iter != endIter; ++iter)
    {
        if(*iter == number_in)
        {
            myNumbers_in.erase(iter);
        }
    }
}

int main(int argc, char* argv[])
{
    std::vector<int> myNmbers;
    for(int i = 0; i < 2; ++i)
    {
        myNmbers.push_back(i);
        myNmbers.push_back(i);
    }

    erase(myNmbers, 1);

    return 0;
}

这段代码显然会崩溃，因为我在迭代向量时更改了向量的末尾。 实现这一目标的最佳方法是什么？ 即，有没有一种方法可以做到这一点，而无需多次迭代向量或创建向量的另一个副本？

Answer 1

1. 您可以使用索引访问进行迭代，

2. 避免 O(n^2) 复杂度
   您可以使用两个索引，i - 当前测试索引，j - 索引
   存储下一项，并在循环结束时存储新的向量大小。

代码：

void erase(std::vector<int>& v, int num)
{
  size_t j = 0;
  for (size_t i = 0; i < v.size(); ++i) {
    if (v[i] != num) v[j++] = v[i];
  }
  // trim vector to new size
  v.resize(j);
}

在这种情况下，您不会使迭代器失效，复杂度为 O(n)，并且代码非常简洁，您不需要编写一些辅助类，尽管在某些情况下使用辅助类可以受益于更灵活的代码。

此代码不使用 erase 方法，但解决了您的任务。

使用纯 stl，您可以通过以下方式执行此操作（这类似于 Motti 的答案）：

#include <algorithm>

void erase(std::vector<int>& v, int num) {
    vector<int>::iterator it = remove(v.begin(), v.end(), num);
    v.erase(it, v.end());
}

Answer 2

根据您这样做的原因，使用 std::set 可能是比 std::vector 更好的主意。

它允许每个元素仅出现一次。 如果多次添加，则无论如何都只会删除一个实例。 这将使擦除操作变得微不足道。
擦除操作的时间复杂度也比向量低，但是，在集合上添加元素速度较慢，因此可能没有太大优势。

如果您对元素添加到向量中的次数或添加元素的顺序感兴趣，这当然不起作用。

Answer 3

自 有 std::erase 和 std::erase_if >C++20 结合了删除-擦除习惯用法。

std::vector<int> nums;
...
std::erase(nums, targetNumber);

或者

std::vector<int> nums;
...
std::erase_if(nums, [](int x) { return x % 2 == 0; }); 

Answer 4

如果您按如下方式更改代码，则可以进行稳定的删除。

void atest(vector<int>& container,int number_in){
for (auto it = container.begin(); it != container.end();) {
    if (*it == number_in) {
        it = container.erase(it);
    } else {
        ++it;
    }
  }
}

然而，也可以使用诸如以下的方法。

void btest(vector<int>& container,int number_in){
   container.erase(std::remove(container.begin(), container.end(), number_in),container.end());
}

如果我们必须保留序列的顺序（例如，如果我们按照某些有趣的属性对其进行排序），那么我们可以使用上述方法之一。 但是，如果序列只是一袋值，我们根本不关心其顺序，那么我们可能会考虑从序列末尾移动单个元素来填充创建时的每个新间隙：

void ctest(vector<int>& container,int number_in){
  for (auto it = container.begin(); it != container.end(); ) {
   if (*it == number_in) {
     *it = std::move(container.back());
     container.pop_back();
   } else {
     ++it;
  }
 }
}

以下是它们的基准结果：
CLang 15.0：

Gcc 12.2：

Answer 5

您可以使用 find 以及随后的 erase 方法来删​​除特定元素。

例如：

auto ite = std::find(yourVector.begin(),yourVector.end(),element);
yourVector.erase(ite); 

Answer 6

调用擦除将使迭代器无效，您可以使用：

void erase(std::vector<int>& myNumbers_in, int number_in)
{
    std::vector<int>::iterator iter = myNumbers_in.begin();
    while (iter != myNumbers_in.end())
    {
        if (*iter == number_in)
        {
            iter = myNumbers_in.erase(iter);
        }
        else
        {
           ++iter;
        }
    }

}

或者您可以使用 std::remove_if 与函子和 std::vector::erase 一起使用：

struct Eraser
{
    Eraser(int number_in) : number_in(number_in) {}
    int number_in;
    bool operator()(int i) const
    {
        return i == number_in;
    }
};

std::vector<int> myNumbers;
myNumbers.erase(std::remove_if(myNumbers.begin(), myNumbers.end(), Eraser(number_in)), myNumbers.end());

在这种情况下，您可以使用 std::remove：

std::vector<int> myNumbers;
myNumbers.erase(std::remove(myNumbers.begin(), myNumbers.end(), number_in), myNumbers.end());

在 C++11 中，您可以使用 lambda 而不是函子：

std::vector<int> myNumbers;
myNumbers.erase(std::remove_if(myNumbers.begin(), myNumbers.end(), [number_in](int number){ return number == number_in; }), myNumbers.end());

在 C++17 中 std::experimental::erase 和 std::experimental::erase_if 也可用，在 C++20 中它们（最终）重命名为 std::erase 和 std::erase_if（注意：在 Visual Studio 2019 中，您需要将 C++ 语言版本更改为最新的实验版本以获得支持）：

std::vector<int> myNumbers;
std::erase_if(myNumbers, Eraser(number_in)); // or use lambda

或者：

std::vector<int> myNumbers;
std::erase(myNumbers, number_in);

Answer 7

从 C++20 开始，有独立的 std::erase 和 std::erase_if 函数适用于容器并大大简化事情：

std::erase(myNumbers, number_in);
// or
std::erase_if(myNumbers, [&](int x) { return x == number_in; });

在 C++20 之前，使用 擦除删除习惯用法：

std::vector<int>& vec = myNumbers; // use shorter name
vec.erase(std::remove(vec.begin(), vec.end(), number_in), vec.end());
// or
vec.erase(std::remove_if(vec.begin(), vec.end(), [&](int x) {
    return x == number_in;
}), vec.end());

发生的情况是 std::remove 压缩与值不同的元素被删除（number_in）在向量的开头，并将迭代器返回到该范围之后的第一个元素。 然后erase删除这些元素（其值未指定）。