4.1 Динамические массивы¶

Что такое динамический массив?¶

Динамический массив — это массив, размер которого можно изменять во время выполнения программы. В C++ основной такой структурой является vector.

В отличие от обычного массива:

int a[5]; // размер фиксирован

вектор можно расширять и уменьшать по мере необходимости. Такая логика используется в нём:

flowchart TB
    A[vector: размер 0] --> B[push_back 1]
    B --> C[Память выделена<br/>емкость = 1]

    C --> D[push_back 2]
    D --> E[Места нет]
    E --> F[Выделяется новый массив<br/>большего размера]
    F --> G[Элементы переносятся]
    G --> H[Старый массив удаляется]
    H --> I[Новый элемент добавляется]

    I --> J[push_back 3]
    J --> K{Хватает емкости?}
    K -- Да --> L[Просто добавляем элемент]
    K -- Нет --> F

Базовое использование vector¶

Создадим пустой вектор и добавим элементы:

vector<int> v;

v.push_back(10);   // [10]
v.push_back(4);    // [10, 4]
v.push_back(7);    // [10, 4, 7]

Доступ к элементам осуществляется так же, как в обычном массиве:

cout << v[0] << "\n"; // 10
cout << v[1] << "\n"; // 4
cout << v[2] << "\n"; // 7

Перебор элементов¶

Способ 1 — по индексам¶

for (int i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
}

Способ 2 — range-based for (короче и удобнее)¶

for (auto x : v) {
    cout << x << " ";
}

Работа с концом вектора¶

vector<int> v;

v.push_back(8);
v.push_back(3);

cout << v.back() << "\n"; // 3

v.pop_back();             // удаляем последний элемент

cout << v.back() << "\n"; // 8

• back() — возвращает последний элемент
• pop_back() — удаляет последний элемент

Обе операции работают за O(1).

Инициализация вектора¶

Через список значений¶

vector<int> v = {5, 1, 9, 3};

Через размер¶

vector<int> v(10);        // 10 элементов со значением 0
vector<int> v(10, 7);     // 10 элементов со значением 7

Как устроен vector внутри?¶

Внутри vector использует обычный массив.

Когда место заканчивается:

1. Выделяется новый массив большего размера.
2. Все элементы копируются туда.
3. Старый массив удаляется.

Из-за этого:

• push_back() иногда работает медленно,
• но в среднем работает за O(1) (это называется амортизированной сложностью).

Когда использовать vector?¶

Используйте vector, если:

• размер массива заранее неизвестен;
• нужно часто добавлять элементы в конец;
• требуется удобный интерфейс STL;
• важна высокая производительность.

В большинстве задач олимпиадного программирования vector — стандартный выбор вместо обычных массивов.

Строки как динамические массивы¶

Тип string — это по сути vector<char> с дополнительными возможностями.

string s = "robot";

s += "ics";     // robotics

cout << s[2];   // 'b'

Полезные функции:

string t = "programming";

cout << t.substr(3, 4) << "\n"; // gram
cout << t.find("ram") << "\n";  // 3

• substr(pos, len) — подстрока
• find(str) — поиск подстроки

Сложность операций¶

Важные замечания для соревнований¶

• Почти всегда используйте vector вместо массивов фиксированного размера.
• Если известен примерный размер, можно вызвать:

v.reserve(1000000);

чтобы избежать лишних перераспределений памяти.

• Не используйте erase в середине вектора в цикле — это операция O(n).

Итог¶

Динамический массив (vector) — базовая структура данных в C++ для соревнований.

Он:

• удобный,
• быстрый,
• гибкий,
• поддерживает STL,
• идеально подходит для большинства задач.

Дальше мы рассмотрим структуры множеств (set) и отображений (map), которые позволяют работать с динамическими коллекциями ещё эффективнее.