從矢量中清除元素

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