# std::vector и инвалидация ссылок

В стандартной библиотеке C++ не очень много последовательных контейнеров с динамической длиной:
- std::list
- std::forward_list
- std::deque
- std::vector

Из них `std::vector` используется в большинстве случаев. А остальные — только если их особенности становятся действительно необходимыми и дают заметную разницу в улучшении производительности. Так, например, возможность вставки в произвольную позицию за константное число операций в `std::list` [не дает преимущества](https://baptiste-wicht.com/posts/2012/11/cpp-benchmark-vector-vs-list.html) в сравнении с `std::vector` (требует линейного времени), пока контейнеры недостаточно большие или размер элементов мал.

`std::vector`, будучи самым эффективным контейнером, является еще и самым небезопасным. Из-за инвалидации ссылок и итераторов.

Неосторожное использование `std::vector` вкупе с обилием засахаренных синтаксических конструкций очень легко приводит к неопределенному поведению.

Простенький пример с очередью задач:
```C++
std::optional<Action> evaluate(const Action&);

void run_actions(std::vector<Action> actions) {
    for (auto&& act: actions) { // UB
        if (auto new_act = evaluate(act)) {
            actions.push_back(std::move(*new_act)); // UB
        }
    }
}
```
Красиво, коротко, с неопределенным поведением и неправильно.

- `push_back` может вызвать реаллокацию вектора. Итераторы begin/end инвалидируются — цикл продолжится по уничтоженным данным.
- Если реаллокации не произойдет, цикл пройдет только по тому набору элементов, что были в векторе изначально. До добавленных в процессе дело не дойдет.

Корректный код:
```C++
void run_actions(std::vector<Action> actions) {
    for (size_t idx = 0; idx < actions.size(); ++idx) {
        const auto& act = actions[idx];
        if (auto new_act = evaluate(act)) {
            actions.push_back(std::move(*new_act));
        }
    }
}
```

В какой-то момент нам захотелось по-быстрому добавить логгирование, чтобы что-то проверить:
```C++
void run_actions(std::vector<Action> actions) {
    for (size_t idx = 0; idx < actions.size(); ++idx) {
        const auto& act = actions[idx];
        if (auto new_act = evaluate(act)) {
            actions.push_back(std::move(*new_act));
        }
        std::cerr << act.Id() << "\n"; // UB!
    }
}
```
И у нас опять неопределенное поведение — `push_back` может вызвать реаллокацию вектора
и тогда ссылка `act` станет висячей.

Корректный код:
```C++
void run_actions(std::vector<Action> actions) {
    for (size_t idx = 0; idx < actions.size(); ++idx) {
        if (auto new_act = evaluate(actions[idx])) {
            actions.push_back(std::move(*new_act));
        }
        std::cerr << actions[idx].Id() << "\n";
    }
}
```

Этот простой паттерн с инвалидацией ссылок в векторе может очень легко спрятаться под слоем абстракций. Например — цикл обработки является публичным методом класса `TaskQueue`, а обработка одной задачи — его приватный метод. В таком случае изменение в одном методе, совершенно корректное в рамках него, приведет к UB из-за неявного влияния на другой метод.

Кое-как защититься от подобной неприятности можно с помощью статических анализаторов, работающих с потоком исполнения программы. Также проблема почти точно ловится санитайзерами или утилитами проверки памяти (например, valgrind). Если, конечно, у вас достаточно хорошие тесты.

В языке Rust проблема отлавливается на этапе компиляции с помощью borrow checker'а.

Если вы можете позволить себе просадку производительности, лучше использовать специализированные контейнеры (или адапторы контейнеров) для специфичных задач.
Так `std::queue` по умолчанию использует `std::deque` и не инвалидирует ссылки при добавлении новых элементов. А также ее нельзя неосторожно использовать в range-based-for — у нее нет итераторов begin/end

## Полезные ссылки
1. https://baptiste-wicht.com/posts/2012/11/cpp-benchmark-vector-vs-list.html
2. https://stackoverflow.com/questions/6438086/iterator-invalidation-rules