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

Я хочу очистить элемент от вектора, используя метод стирания. Но проблема здесь в том, что элемент не гарантированно встречается в векторе только один раз. Это может присутствовать несколько раз, и мне нужно очистить их все. Мой код примерно такой:

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

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

Источник

8 ответов

Решение

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

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

Источник

Вызов 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());
Источник

  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, вы можете сделать это следующим образом (это похоже на ответ 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());
}
Источник

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

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

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

Источник

Существуют std::erase и std::erase_if начиная с C++20 , которые сочетают в себе идиому удаления-стирания.

      std::vector<int> nums;
...
std::erase(nums, targetNumber);

или же

      std::vector<int> nums;
...
std::erase_if(nums, [](int x) { return x % 2 == 0; });
Источник

Если вы измените свой код следующим образом, вы можете выполнить стабильное удаление.

      void atest(vector<int>& container,int number_in){
for (auto it = container.begin(); it != container.end();) {
    if (*it == number_in) {
        it = container.erase(it);
    } else {
        ++it;
    }
  }
}

Однако можно также использовать способ, подобный следующему.

      void btest(vector<int>& container,int number_in){
   container.erase(std::remove(container.begin(), container.end(), number_in),container.end());
}

Если мы должны сохранить порядок нашей последовательности (скажем, если мы сохраняем ее отсортированной по какому-то интересному свойству), то мы можем использовать одно из вышеперечисленных. Но если последовательность — это просто набор значений, порядок которых нас совершенно не волнует, то мы могли бы подумать о перемещении отдельных элементов из конца последовательности, чтобы заполнить каждый новый пробел по мере его создания:

      void ctest(vector<int>& container,int number_in){
  for (auto it = container.begin(); it != container.end(); ) {
   if (*it == number_in) {
     *it = std::move(container.back());
     container.pop_back();
   } else {
     ++it;
  }
 }
}

Ниже приведены их результаты тестов: CLang 15.0:

Gcc 12.2:

Источник

Вы можете использоватьfindи, следовательно,eraseметод для удаления определенного элемента.

Например:

      auto ite = std::find(yourVector.begin(),yourVector.end(),element);
yourVector.erase(ite);
Источник

Чтобы стереть 1-й элемент, вы можете использовать:

vector<int> mV{ 1, 2, 3, 4, 5 }; 
vector<int>::iterator it; 

it = mV.begin(); 
mV.erase(it);
Источник
Другие вопросы по тегам