从矢量中清除元素

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

使用remove/erase idiom：

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

什么情况是，在vector年初被移除（number_in）并返回remove压块从值不同的元素迭代器到该范围之后的第一个元素。然后erase删除这些元素（谁的值是未指定的）。

Answer 2

您可以从结尾开始或在元素被擦除时更新结束。

这将是这个样子：

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); 
         endIter = myNumbers_in.end(); 
       } 
     } 

    } 

Answer 3

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

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 ::载体一起使用std::remove_if： ：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()); 

而不是编写你自己的函数在这种情况下你co ULD使用std::remove：

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

Answer 4

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

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

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

Answer 5

1. 您可以重复使用索引访问，

2. 为了避免为O（n^2）复杂 可以用两个指标，我 - 电流测试指标，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()); 
}