Xóa các phần tử khỏi một vector

Question

Tôi muốn xóa phần tử khỏi véc-tơ bằng phương pháp xóa. Nhưng vấn đề ở đây là phần tử không được bảo đảm chỉ xảy ra một lần trong vectơ. Nó có thể được trình bày nhiều lần và tôi cần phải xóa tất cả chúng. Mã của tôi là một cái gì đó như thế này:

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

Mã này rõ ràng là bị treo vì tôi đang thay đổi phần cuối của vector trong khi iterating qua nó. cách tốt nhất để đạt được điều này là gì? I E. là có cách nào để làm điều này mà không cần lặp qua vector nhiều lần hoặc tạo thêm một bản sao của véc-tơ?

Answer 1

Sử dụng remove/erase idiom:

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

gì xảy ra là remove máy ảnh compact các yếu tố khác với giá trị phải được loại bỏ (number_in) vào đầu của vector và trả về iterator đến phần tử đầu tiên sau phạm vi đó. Sau đó, erase xóa các phần tử này (giá trị của ai không được chỉ định).

Answer 2

Bạn có thể bắt đầu từ cuối hoặc cập nhật kết thúc khi một phần tử bị xóa.

Nó sẽ giống như thế này:

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

Calling xóa sẽ làm mất hiệu lực lặp, bạn có thể sử dụng:

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

} 

Hoặc bạn có thể sử dụng std::remove_if cùng với một functor và std :: vector: : xóa:

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

Thay vì viết functor của riêng bạn trong trường hợp này bạn đồng ULD sử dụng std::remove:

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

Answer 4

Tùy thuộc vào lý do bạn thực hiện việc này, sử dụng std::set có thể là một ý tưởng tốt hơn so với std :: vector.

Nó cho phép mỗi phần tử chỉ xảy ra một lần. Nếu bạn thêm nó nhiều lần, sẽ chỉ có một ví dụ để xóa. Điều này sẽ làm cho hoạt động xóa không đáng kể. Hoạt động xóa cũng sẽ có độ phức tạp thời gian thấp hơn so với trên vectơ, tuy nhiên, việc thêm các phần tử chậm hơn trên tập hợp để nó có thể không có nhiều lợi thế.

Điều này tất nhiên sẽ không hoạt động nếu bạn quan tâm đến số lần một phần tử đã được thêm vào vectơ của bạn hoặc thứ tự các phần tử được thêm vào.

Answer 5

1. Bạn có thể lặp lại bằng cách sử dụng truy cập chỉ mục,

2. Để tránh O (n^2) phức tạp bạn có thể sử dụng hai chỉ số, i - hiện tại chỉ số xét nghiệm, j - chỉ số để cửa hàng mục tiếp theo và ở cuối chu kỳ mới của vectơ.

mã:

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

Trong trường hợp này bạn không có hủy bỏ hiệu lực của vòng lặp, độ phức tạp là O (n), và mã là rất súc tích và bạn không cần phải viết một số lớp helper, mặc dù trong một số trường hợp sử dụng các lớp trợ giúp có thể được hưởng lợi trong mã linh hoạt hơn.

Mã này không sử dụng phương thức erase nhưng giải quyết được tác vụ của bạn.

Sử dụng STL tinh khiết bạn có thể làm điều này theo cách sau (điều này cũng tương tự như câu trả lời của 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()); 
}