Стирание элементов из вектора

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

Что происходит, что remove компакты элементы, которые отличаются от значения должны быть удалены (number_in) в начале vector и возвращает итератора к первому элементу после этого диапазона. Затем erase удаляет эти элементы (значение who не указано).

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

Вместо того чтобы писать свой собственный функтор в этом случае, вы пакетирования используют 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, но решает вашу задачу.

Использование чистого СТЛ вы можете сделать это следующим образом (это похоже на ответ на Моти в):

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