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

Я хочу очистить элемент от вектора с помощью метода 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;
}

этот код, очевидно, аварийно завершает работу, потому что я изменяю конец вектора во время итерации через него. Каков наилучший способ достичь этого? Т. е. есть ли способ сделать это без перебора вектор несколько раз или создание еще одной копии вектора?

4 84
c++ castle-windsor vector erase

4 ответа:

использовать удалить/стереть идиома:

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 удаляет эти элементы (значение ВОЗ не указано).

138

вызов 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());
47

  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 метод, но решает вашу задачу.

используя pure stl вы можете сделать это следующим образом (это похоже на ответ Мотти):

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

в зависимости от того, почему вы делаете это, используя std:: set может быть лучше, чем std::vector.

Это позволяет каждому элементу произойти только один раз. Если вы добавите его несколько раз, в любом случае будет только один экземпляр для удаления. Это сделает операцию стирания тривиальной. Операция стирания также будет иметь меньшую временную сложность, чем на векторе, однако добавление элементов происходит медленнее на множестве, поэтому это может быть не так много преимуществ.

Это курс не будет работать, если вы заинтересованы в том, сколько раз элемент был добавлен в ваш вектор или порядок элементов были добавлены.

3