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

Question

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

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

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

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

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

Answer 1

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

Нет; все итераторы в и после итераторов, переданных в erase, становятся недействительными.

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

---

Обратите внимание, что этот конкретный метод удаления нечетных элементов довольно неэффективен: каждый раз, когда вы удаляете элемент, все элементы после него должны быть перемещены на одну позицию влево в векторе (это O (n ^{). 2} )). Вы можете выполнить эту задачу гораздо эффективнее, используя 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());

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