Сигнал задачи
Когда применять
Нужны плотное хранение, быстрый доступ по индексу и рост в конце.
Что держать в голове
- Уметь выбирать контейнер по требуемым операциям.
- Уметь объяснять амортизированную стоимость роста динамического массива.
- Уметь оценивать ожидаемую стоимость поиска и обновления по ключу.
Сложность
- Доступ по индексу O(1); добавление в конец амортизированно O(1), но отдельное расширение требует O(n); вставка и удаление внутри O(n).
- Хранятся size элементов и запас capacity; неиспользованная ёмкость ускоряет рост ценой дополнительной памяти.
Границы и ошибки
- Python list концептуально ведёт себя как динамический массив, а не связный список; его точное внутреннее хранение зависит от реализации, а C++ std::list не даёт O(1) доступа по индексу.
- После перераспределения std::vector прежние указатели, ссылки и итераторы на его элементы могут стать недействительными.
- Амортизированное O(1) для push_back или append не означает O(1) в худшем случае для каждого отдельного вызова.