Std::vector аннулирование итератора

Ранее было несколько вопросов по этому вопросу; я понимаю, что вызов std::vector::erase приведет к недействительности итераторов, находящихся в позиции после стираемого элемента. Однако после стирания элемента итератор в этом положении все еще действителен (при условии, конечно, что после стирания он не указывает на end())?

Мое понимание того, как будет реализован вектор, похоже, предполагает, что итератор определенно полезен, но я не совсем уверен, может ли это привести к поведению undefined.

В качестве примера того, что я говорю, следующий код удаляет все нечетные целые числа из вектора. Этот код вызывает поведение undefined?

typedef std::vector<int> vectype;
vectype vec;

for (int i = 0; i < 100; ++i) vec.push_back(i);

vectype::iterator it = vec.begin();
while (it != vec.end()) {
    if (*it % 2 == 1) vec.erase(it);
    else ++it;
}

Код работает нормально на моей машине, но это не убеждает меня в том, что оно действительно.

Ответ 1

после стирания элемента, итератор в этой позиции все еще действителен

Нет; все итераторы в или после того, как итератор (ы), переданный в erase, недействительны.

Однако erase возвращает новый итератор, который указывает на элемент сразу после стираемых элементов (или до конца, если такого элемента нет). Вы можете использовать этот итератор для возобновления итерации.

Обратите внимание, что этот конкретный метод удаления нечетных элементов довольно неэффективен: каждый раз, когда вы удаляете элемент, все элементы после его перемещения должны перемещаться влево в векторе (это O (n ²)). Вы можете выполнить эту задачу гораздо более эффективно, используя erase-remove idiom (O (n)). Вы можете создать предикат is_odd:

bool is_odd(int x) { return (x % 2) == 1; }

Затем это можно передать в remove_if:

vec.erase(std::remove_if(vec.begin(), vec.end(), is_odd), vec.end());

Ответ 2

Или:

class CIsOdd
{
public:
    bool operator()(const int& x) { return (x % 2) == 1; }
};

vec.erase(std::remove_if(vec.begin(), vec.end(), CIsOdd()), vec.end());