Блог

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

 void erase(std::vector<int>amp; 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;
}
  

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

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

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

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

Редактировать: при обновлении мертвой ссылки я обнаружил, что начиная с C 20 существуют автономные функции std::erase и std::erase_if функции, которые работают с контейнерами и значительно упрощают работу.

Вызов erase приведет к аннулированию итераторов, вы могли бы использовать:

 void erase(std::vector<int>amp; 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());
  

В C 11 вы могли бы использовать лямбда-выражение вместо функтора:

 std::vector<int> myNumbers;
myNumbers.erase(std::remove_if(myNumbers.begin(), myNumbers.end(), [number_in](int number){ return number == number_in; }), myNumbers.end());
  

В C 17 также доступны std ::experimental::erase и std ::experimental::erase_if, в C 20 они (наконец) переименованы в std ::erase и std ::erase_if (примечание: в Visual Studio 2019 вам нужно будет изменить версию языка C к последней экспериментальной версии для поддержки):

 std::vector<int> myNumbers;
std::erase_if(myNumbers, Eraser(number_in)); // or use lambda
  

или:

 std::vector<int> myNumbers;
std::erase(myNumbers, number_in);
  

1. Вы можете выполнить итерацию, используя доступ к индексу,

2. Чтобы избежать сложности O (n ^ 2), вы можете использовать два индекса: i — текущий индекс тестирования, j — индекс для хранения следующего элемента и в конце цикла нового размера вектора.

код:

 void erase(std::vector<int>amp; 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>amp; v, int num) {
    vector<int>::iterator it = remove(v.begin(), v.end(), num);
    v.erase(it, v.end());
}
  

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

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

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

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

 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>amp; 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>amp; container,int number_in){
   container.erase(std::remove(container.begin(), container.end(), number_in),container.end());
}
  

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

 void ctest(vector<int>amp; 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: