Mediumитераторы
Что такое iterator invalidation и когда оно происходит?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
Iterator invalidation — потеря валидности итератора после операции, меняющей контейнер. Использование инвалидированного итератора — UB.
std::vector<int> v{1, 2, 3, 4};
// Правильное удаление по условию — перечитываем it после erase
for (auto it = v.begin(); it != v.end(); ) {
if (*it % 2 == 0) it = v.erase(it);
else ++it;
}
// С C++20 короче: std::erase_if(v, [](int x){ return x % 2 == 0; });- vector —
push_back/reserveпри росте capacity инвалидируют ВСЕ итераторы;erase— от точки до конца; - deque — большинство операций инвалидируют все;
- list/forward_list/map/set —
eraseинвалидирует только удалённый, остальные живы; - unordered_* — rehash инвалидирует все.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.