std :: vector iterator invalidation

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)). Вы можете выполнить эту задачу гораздо более эффективно, используя 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());