В стандартной библиотеке C++ не очень много последовательных контейнеров с динамической длиной:
- std::list
- std::forward_list
- std::deque
- std::vector
Из них std::vector используется в большинстве случаев. А остальные — только если их особенности становятся действительно необходимыми и дают заметную разницу в улучшении производительности. Так, например, возможность вставки в произвольную позицию за константное число операций в std::list не дает преимущества в сравнении с std::vector (требует линейного времени), пока контейнеры недостаточно большие или размер элементов мал.
std::vector, будучи самым эффективным контейнером, является еще и самым небезопасным. Из-за инвалидации ссылок и итераторов.
Неосторожное использование std::vector вкупе с обилием засахаренных синтаксических конструкций очень легко приводит к неопределенному поведению.
Простенький пример с очередью задач:
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 инвалидируются — цикл продолжится по уничтоженным данным.- Если реаллокации не произойдет, цикл пройдет только по тому набору элементов, что были в векторе изначально. До добавленных в процессе дело не дойдет.
Корректный код:
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));
}
}
}В какой-то момент нам захотелось по-быстрому добавить логгирование, чтобы что-то проверить:
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 станет висячей.
Корректный код:
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