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

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

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

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

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

Answer 3

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

Используя чистый 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());
}

Answer 4

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

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

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