Проверка валидности итератора после модификации контейнера

Условие

Необходимо проанализировать, насколько безопасно использовать полученный итератор после того, как в контейнер добавляются новые элементы, и указать, для каких STL‑контейнеров такое использование не приводит к его инвалидизации.

template<typename T>
void impl(T& data) {
    data.push_back(0);
    auto iterator = data.begin();
    for (size_t i = 1u; i < 1000u; ++i) {
        data.push_back(i);
    }
    std::cout << "First: " << *iterator << std::endl;
}
int main(int argc, char** argv) {
    std::list<int> data_1;
    impl(data_1); // безопасно

    std::vector<int> data_2;
    impl(data_2); // итератор инвалидируется при push_back
    return EXIT_SUCCESS;
}

Ответ

Для list добавление в конец сохраняет итератор на первый элемент. Для vector он сохраняется только пока не произошло перераспределение; после реаллокации разыменование недопустимо.

У исходно пустого vector обычное заполнение до 1000 элементов вызывает рост буфера. Чтобы использовать тот же приём безопасно, до получения итератора зарезервируйте достаточную ёмкость или получите begin уже после вставок.

Не все контейнеры со стабильными ссылками имеют стабильные итераторы: например, push_back у deque инвалидирует итераторы, хотя ссылки на существующие элементы сохраняет. Контракт проверяют отдельно для конкретной операции и контейнера.