Массивы в C++#

Материал о последовательностях, динамической памяти и алгоритмах. Затем решите 12 авторских задач: Intern, Middle, Senior — по четыре задачи на уровень.

Последовательность и выбор контейнера#

Массив — упорядоченный ряд значений одного типа. Индексация начинается с нуля: при n элементах индексы от 0 до n-1. Для значений фиксированного размера есть std::array<T, N> (<array>); для размера, известного во время работы, обычно используют std::vector<T> (<vector>). Встроенный T a[N] тоже фиксированного размера. Стандартный C++ не поддерживает массивы переменной длины.

std::vector<int> temperatures{18, 20, 17};
std::cout << temperatures[1]; // 20

Вектор хранит элементы непрерывно и знает число элементов. size() — число созданных элементов, capacity() — вместимость уже выделенной памяти. Не обращайтесь к элементу по индексу size() или выше. operator[] не проверяет границу; at(i) проверяет и бросает исключение. Пустой вектор нельзя индексировать.

Жизненный цикл памяти#

std::vector<int> a;
a.reserve(1000); // место зарезервировано, size() всё ещё 0
for (int i = 0; i < 1000; ++i) a.push_back(i);

reserve резервирует capacity, но не создаёт элементов. Для изменения количества элементов предназначен resize. Если размер заранее известен, создайте std::vector<int> a(n). При исчерпании capacity push_back может выделить новый участок памяти и переместить элементы. Добавление в конец амортизированно O(1), но конкретное перераспределение стоит O(n). После него ссылки, указатели и итераторы на элементы могут стать недействительными. insert и erase в середине обычно O(n), так как хвост сдвигается.

clear() удаляет элементы, но не гарантирует освобождения буфера. shrink_to_fit() — необязательный запрос реализации. Обычно не нужны ручные new[] и delete[]: std::vector автоматически освобождает память по RAII и помогает избежать утечек и двойного освобождения.

Python и Rust#

Python list растёт при append, индексируется с нуля, но хранит ссылки на объекты; это не то же расположение данных, что компактный std::vector<int>. Для крупных числовых данных применяют, например, NumPy. Rust Vec<T> похож на вектор C++ по идее владеющего расширяемого буфера и автоматически освобождает память. Rust проверяет правила владения/заимствования; v.get(i) возвращает безопасный результат Option, а неверный v[i] паникует. В C++ выход a[i] за границы — неопределённое поведение, а время жизни ссылок контролирует программист.

Сложность, память и ошибки#

Доступ по индексу — O(1), проход/поиск — O(n), добавление в конец — амортизированно O(1), вставка в начало — O(n). Копирование вектора из n элементов требует O(n) времени и памяти; большой массив, который функция только читает, обычно передают как const std::vector<T>&. Отличайте память входа от дополнительной памяти алгоритма: O(1) дополнительной памяти означает фиксированное число временных переменных, а не отсутствие самого входного массива.

Частые ошибки: индексация за границей; путаница reserve и resize; использование ссылки после перераспределения; копирование массива без необходимости; O(n²) из-за многократного удаления первого элемента; переполнение суммы (при необходимости используйте long long). size_t беззнаковый, поэтому осторожно смешивайте его с отрицательными индексами типа int.