C++ 从向量中删除元素

Erasing elements from a vector

提问by Naveen

I want to clear a element from a vector using the erase method. But the problem here is that the element is not guaranteed to occur only once in the vector. It may be present multiple times and I need to clear all of them. My code is something like this:

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

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;
}

This code obviously crashes because I am changing the end of the vector while iterating through it. What is the best way to achieve this? I.e. is there any way to do this without iterating through the vector multiple times or creating one more copy of the vector?

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

回答by Motti

Use the remove/erase idiom:

使用删除/擦除习语：

std::vector<int>& vec = myNumbers; // use shorter name
vec.erase(std::remove(vec.begin(), vec.end(), number_in), vec.end());

What happens is that removecompacts the elements that differ from the value to be removed (number_in) in the beginning of the vectorand returns the iterator to the first element after that range. Then eraseremoves these elements (whose value is unspecified).

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

回答by dalle

Calling erase will invalidate iterators, you could use:

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

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;
        }
    }

}

Or you could use std::remove_iftogether with a functor and std::vector::erase:

或者您可以将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());

Instead of writing your own functor in this case you could use std::remove:

在这种情况下，您可以使用std::remove ，而不是编写自己的函子：

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

In C++11 you could use a lambda instead of a functor:

在 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());

In C++17 std::experimental::eraseand std::experimental::erase_ifare also available, in C++20 these are (finally) renamed to std::eraseand std::erase_if:

在 C++17 中std::experimental::erase和std::experimental::erase_if也可用，在 C++20 中它们（最终）重命名为std::erase和std::erase_if：

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

or:

或者：

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

回答by sergtk

1. You can iterate using the index access,

2. To avoid O(n^2) complexity you can use two indices, i - current testing index, j - index to store next item and at the end of the cycle new size of the vector.

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

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

code:

代码：

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);
}

In such case you have no invalidating of iterators, complexity is O(n), and code is very concise and you don't need to write some helper classes, although in some case using helper classes can benefit in more flexible code.

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

This code does not use erasemethod, but solves your task.

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

Using pure stl you can do this in the following way (this is similar to the Motti's answer):

使用纯 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());
}

回答by Laserallan

Depending on why you are doing this, using a std::setmight be a better idea than std::vector.

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

It allows each element to occur only once. If you add it multiple times, there will only be one instance to erase anyway. This will make the erase operation trivial. The erase operation will also have lower time complexity than on the vector, however, adding elements is slower on the set so it might not be much of an advantage.

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

This of course won't work if you are interested in how many times an element has been added to your vector or the order the elements were added.

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

回答by Amit Vujic

To erase 1st element you can use:

要擦除第一个元素，您可以使用：

vector<int> mV{ 1, 2, 3, 4, 5 }; 
vector<int>::iterator it; 

it = mV.begin(); 
mV.erase(it);