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

102

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

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

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

Naveen
источник

Ответы:

168

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

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

Мотти
источник
2
std::remove()сдвигает элементы таким образом, что удаляемые элементы перезаписываются. Алгоритм не изменяет размер контейнера, и если nэлементы удаляются, то не определено, какие nэлементы будут последними .
Wilhelmtell
20
Идиома стирание-удаление описана в пункте 32 книги Скотта Мейерса «Эффективный STL: 50 конкретных способов улучшить использование стандартной библиотеки шаблонов».
Алессандро Якопсон 01
1
@Benjin обновление не требуется, оно вызовет деструкторы объектов, если они существуют.
Motti
54
Подобные «идиомы» STL заставляют меня использовать Python для небольших проектов.
Johannes Overmann
1
@LouisDionne , что относится к перегрузке одной итератора, я использую перегрузку два итератора
Motti
53

Вызов стирания аннулирует итераторы, вы можете использовать:

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

В С ++ 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 станд :: экспериментальный :: Стирание и станд :: экспериментальный :: erase_if также доступны, в C ++ 20 это (наконец) переименовали в станд :: Стирание и станд :: erase_if :

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

или:

std::vector<int> myNumbers;
std::erase(myNumbers, number_in);
Далле
источник
2
Зачем использовать собственный функтор, если можно использовать equal_to? :-P sgi.com/tech/stl/equal_to.html
Крис Джестер-Янг,
3
Кстати, вызов eraseс помощью remove- канонический способ сделать это.
Конрад Рудольф
1
я думаю, что он делает именно это. но он должен использовать remove_if, если использует собственный функтор iirc. или просто используйте remove без функтора
Йоханнес Шауб - litb
3
+1 Подробный код просто помог мне в соревновании по программированию, а «просто использовать идиому удалить-стереть» - нет.
13
  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());
}
Sergtk
источник
4

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

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

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

Laserallan
источник
-1

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

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

it = mV.begin(); 
mV.erase(it); 
Амит Вуич
источник
1
Вопрос был не в этом. Ваш ответ 11 лет спустя кажется неуместным, Амит!
Asteroids With Wings,