从向量中删除元素

Question

我想使用erase方法从向量中清除一个元素。但是问题在于该元素不能保证仅在向量中出现一次。它可能出现多次，而我需要清除所有的实例。我的代码大致如下：

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

这段代码在迭代 vector 的同时修改了其结尾，导致程序崩溃。有什么更好的方法可以实现目标吗？也就是说，是否有任何不需要多次迭代向量或创建一个向量副本的方法来完成此操作？

- Naveen

Answer 1

使用remove/erase习语：

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

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

---

编辑：在更新一个失效的链接时，我发现从C++20开始，有独立的std::erase和std::erase_if函数可以用于容器，并且可以大大简化事情。

- Motti

---

std::remove()函数会移动元素，以便覆盖需要删除的元素。该算法不会改变容器的大小，如果删除了n个元素，则未定义最后的n个元素是什么。 - wilhelmtell

“erase-remove”这个习语在Scott Meyers的书《Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library》中的第32条中有所描述。 - Alessandro Jacopson

这样的STL“成语”让我在小项目中使用Python。 - Johannes Overmann

@TamaMcGlinn，这段代码并不会移除 end()，它会移除在 begin() 和 end() 之间的所有元素。如果 begin() 等于 end()，则该范围内没有任何元素，因此不会删除任何东西（erase 同理）。 - Motti

亲爱的C++委员会：std::vector<T>.remove(T&v)有什么问题？这并不像是一个罕见的用例！我是一位30年的C++老手，在经历了五年的间歇期后回到C＃/Java领域。这种丑陋的事情是何时发生的，我需要从哪里开始阅读才能了解C++发生了什么？ - Robin Davies

Answer 2

调用erase将使迭代器失效，你可以使用：

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

- dalle

---

为什么要使用自己的函数对象，当你可以使用equal_to呢？ :-P http://www.sgi.com/tech/stl/equal_to.html - C. K. Young

顺便提一下，使用remove来调用erase是这样做的标准方法。 - Konrad Rudolph

我认为他确实这样做了。但是如果使用自己的函数对象，他应该使用remove_if。或者只需使用不带函数对象的remove。 - Johannes Schaub - litb

刚刚用拼写出来的代码在编程比赛中帮了我一个大忙，而“只需使用删除擦除习惯用语”却没有。 - user529758

Answer 3

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

- sergdev

Answer 4

自 C++20 开始，有 std::erase 和 std::erase_if 函数可以使用，它们结合了删除-擦除惯用语。

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

或者

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

- Eduard Rostomyan

Answer 5

根据您的目的，使用 std::set 可能比 std::vector 更好。

它只允许每个元素出现一次。如果添加多次，则仍将只有一个实例可供删除。这将使删除操作变得轻松简单。 与向 vector 添加元素相比，erase 操作的时间复杂度也更低，但是在 set 上添加元素较慢，因此可能不会带来太大的优势。

当然，如果您对元素添加到向量中的次数或顺序感兴趣，则此方法无法解决。

- Laserallan

Answer 6

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

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:

- kfc

---

看起来像是编译器浏览器 :) - undefined

Answer 7

您可以使用find方法，然后使用erase方法来删除特定元素。

例如：

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

- Rohan