Массивы и Векторы - Язык программирования C++ для спортивного программирования
Неделя 4Массивы и Векторы, Обход массива, Основы временной сложности
Массивы и Векторы
Одно имя для целого ряда чисел: vector<int> a(n), индексы от 0 до n − 1, чтение n чисел и их повторное использование, позиции, считая с 1, изменение элементов, разные способы пройти по вектору, два вектора рядом, push_back и size, for по элементам и массив фиксированного размера.
Теория
Урок 1 из 8
25 мин чтения
Вопросов: 5
На прошлой неделе каждое число читалось, использовалось и забывалось: цикл
хранил сумму или максимум, но не сами числа. Для суммы этого достаточно. А вот
для такой задачи — нет:
Прочитайте n чисел и выведите их в обратном порядке.
Первое прочитанное число нужно напечатать последним — после того как
прочитаны все остальные. Значит, программа должна сохранить каждое из них. Для
трёх чисел хватило бы трёх переменных; но при n до 100 000 никто не станет
заводить 100 000 переменных. Нам нужно одно имя для целого ряда чисел. В C++
это вектор (и его более старый родственник — массив, о нём в конце
урока).
Ряд пронумерованных ячеек
Эта строка создаёт вектор с именем a из 5 ячеек, в каждой из которых
лежит int. Ячейки пронумерованы, и нумерация начинается с 0: это a[0],
a[1], a[2], a[3] и a[4]. Число в квадратных скобках — это индекс
(какая ячейка), а то, что лежит в ячейке, — её значение. В новом векторе все
ячейки сначала равны 0.
Каждое a[i] ведёт себя точно как обычная переменная типа int: его можно
читать, печатать, присваивать, увеличивать через += или ++. Разница в том,
что индекс можно вычислять: a[i], a[i + 1], a[n - 1] — поэтому цикл
может пройти по ячейкам одну за другой.
vector<int> хранит int, vector<long long> — long long и так далее: у всех
ячеек одного вектора один и тот же тип. Ещё два способа создать вектор:
Код
Что получается
vector<int> a(n);
n ячеек, все равны 0
дальше
Практика: Массивы и Векторы
Сохраните числа, а потом используйте их по позиции, задом наперёд, по частям или дважды.
Обычно во вводе сначала идёт n, а потом сами n чисел. Создайте вектор, когда
n уже известно, а затем заполните его циклом — переменная цикла и будет
индексом:
Первое число попадает в a[0], второе — в a[1], …, последнее — в a[n - 1].
Теперь задача про обратный порядок решается легко: пройдём по тем же ячейкам
назад, от n - 1 до 0. Пройдите по шагам с n = 4:
Сохраняем все, а потом печатаем задом наперёд
C++
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 ios_base::sync_with_stdio(false);
6 cin.tie(NULL);
7
8 int n;
9 cin >> n;
10 vector<int> a(n);
11 for (int i = 0; i < n; i++) {
12 cin >> a[i];
13 }
14 for (int i = n - 1; i >= 0; i--) {
15 cout << a[i] << " ";
16 }
17 cout << "\n";
18 return 0;
19}
Читаем n
строка 9
Будет 4 числа. Программа должна напечатать их от последнего к первому, поэтому ей нужно сохранить каждое.
a4 ячеек
—
—
—
—
0
1
2
3
ввод
4
7
2
9
4
n4i—
нажми пуск
1 / 31
Каждое число прочитано один раз и после этого никуда не делось: его можно
использовать снова, в любом порядке и сколько угодно раз. В этом и весь смысл
вектора.
Индексы идут от 0 до n − 1
У вектора размера n индексы 0, 1, …, n - 1. Элемента a[n]нет:
Поэтому циклы по вектору пишут как for (int i = 0; i < n; i++), с <, а не с
<=. Цикл, который всё же доходит до a[n], читает память, принадлежащую
чему-то другому. C++ его не остановит и не предупредит: программа напечатает
странное число или упадёт, а проверяющая система сообщит Wrong answer или
Runtime error. Проверяйте первый и последний индекс каждого цикла, который
пишете.
В условиях задач элементы обычно нумеруются с 1: a₁, a₂, …, aₙ. В программе
они лежат в a[0] … a[n - 1], поэтому p-й элемент из условия — это
a[p - 1]. Здесь такой перевод нужен в каждом запросе:
На полке стоят n банок, даны их цены слева направо. Затем идут q запросов,
каждый — позиция p (считая с 1). Для каждого выведите цену банки, которая там
стоит.
Ввод
Вывод
Каждый ответ — это один взгляд на a[p - 1], и никакой цикл для поиска не
нужен, какой бы длинной ни была полка. Позиции считаются с 1, индексы — с 0, а
- 1 переводит одно в другое. (Есть и другой способ — сделать вектор на одну
ячейку больше и пользоваться a[1] … a[n]; он тоже работает, только никогда не
смешивайте два способа в одной программе.)
Изменяем элементы
Ячейку можно менять сколько угодно раз, и меняется только она:
Выбирайте тип по тому, что будет лежать в ячейках. Ячейке, которая начинается
около 10⁹ и сто тысяч раз получает += k, нужен vector<long long>. Как и
новому значению, составленному из двух старых: a[i] + b[i], где оба до 10⁹,
может достичь 2 · 10⁹ — больше, чем вмещает int (неделя 1), — так что считайте
его в long long.
Разные способы пройти по вектору
Цикл решает, какие ячейки посетить и в каком порядке. Все эти циклы обращаются
только к допустимым индексам:
Цикл
Что посещает
for (int i = 0; i < n; i++)
все ячейки, слева направо
for (int i = n - 1; i >= 0; i--)
все ячейки, справа налево
for (int i = 0; i < n; i += 2)
a[0], a[2], a[4], … — а вместе с a[i + 1] пары
for (int i = l - 1; i <= r - 1; i++)
часть от l-го до r-го элемента (считая с 1)
cout << a[n - 1 - i] внутри первого цикла
зеркальную ячейку: a[n - 1] при i, равном 0, и a[0] при i, равном n - 1
Раз числа остаются, программа может пройти по вектору несколько раз: один
раз — чтобы напечатать чётные числа, второй — чтобы напечатать нечётные; один
раз — чтобы посмотреть на последний элемент, а потом ещё раз, чтобы сравнить с
ним каждый элемент. Два прохода по n числам — это всего 2n шагов.
Два вектора одной длины выстраиваются ячейка к ячейке: a[i] и b[i] относятся
друг к другу. Прочитайте a одним циклом, b — вторым, а потом сравнивайте или
объединяйте их индекс за индексом:
Вектор, который растёт: push_back
Иногда n вам никто не сообщает — числа просто идут до 0. Тогда начните с
пустого вектора и добавляйте каждое число в конец, как только оно приходит:
push_back(x) добавляет одну новую ячейку в конец и кладёт в неё x.
a.size() — это число ячеек прямо сейчас, поэтому последний элемент — всегда
a[a.size() - 1]. Посмотрите, как растёт вектор, пока ввод идёт до 0:
push_back: вектор растёт по одной ячейке
C++
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 ios_base::sync_with_stdio(false);
6 cin.tie(NULL);
7
8 vector<int> a;
9 int x;
10 cin >> x;
11 while (x != 0) {
12 a.push_back(x);
13 cin >> x;
14 }
15 int n = a.size();
16 cout << n << " " << a[n - 1] << "\n";
17 return 0;
18}
Пустой вектор
строка 8
У vector<int> a; вообще нет ячеек: a.size() равно 0. Мы не знаем, сколько придёт чисел.
a0 ячеек
ввод
6
3
8
0
x—n—
нажми пуск
1 / 14
Размер не бывает отрицательным, поэтому C++ даёт a.size() тип, в котором
отрицательных чисел нет вовсе: у пустого вектора a.size() - 1 — это не −1,
а огромное число. Прежде чем из него вычитать,
сохраните его в int — int n = a.size();, — как в трассе.
Каждый элемент: for по элементам
Чтобы посетить все элементы по порядку и только читать их, есть более
короткий for:
Читайте его как «для каждого x из a». Индекса здесь нет: пользуйтесь им,
когда позиция не важна. x — это копия элемента, поэтому изменение x не
меняет вектор; чтобы менять элементы, нужен цикл с индексом.
Вот push_back и for по элементам вместе. cin >> x && x != 0 читает число и
останавливается на 0, как на неделе 3:
Числа даны до 0. Выведите сначала все чётные числа, а потом все нечётные,
каждую группу — в том порядке, в котором пришли числа.
Ввод
Вывод
Два вектора раскладывают числа по мере поступления; печатать ничего не нужно,
пока не встретится 0.
Теперь рассадите зрителей сами. Система бронирования кинотеатра хранит каждый ряд
как вектор: номера на креслах считаются с 1, а программа считает с 0.
Найдите своё местопопробуй!
Массивы: родственник фиксированного размера
Во многих решениях, которые вам попадутся, вместо векторов используются обычные
массивы C++:
Размер массива задаётся, когда программа пишется, поэтому его делают таким, как
наибольшееn, допустимое по условию, плюс несколько запасных ячеек, и
используют только первые n ячеек. Большие массивы объявляют внеmain:
большой массив внутри main может обрушить программу сразу при запуске. У массива
нет ни size(), ни push_back — n вы храните сами.
Индексы, циклы и правило «от 0 до n − 1» у них одинаковые. В этом курсе мы
пользуемся векторами: они знают свой размер, растут, когда нужно, и на них
опираются следующие недели (функции, сортировка).
Проверьте себя
А вы знали?
Почему счёт начинается с 0? В 1982 году информатик Эдсгер Дейкстра написал
заметку на одну страницу — Почему нумерация должна начинаться с нуля. Его
довод: с индексами 0 ≤ i < n в диапазоне ровно n элементов, пустой диапазон —
это 0 ≤ i < 0, и нигде не нужны + 1 или - 1. C, а за ним и C++, считают так
же: a[i] означает «ячейка, которая на i шагов дальше первой» — а первая
отстоит от самой себя на 0 шагов.
vector<int> a(5);
a[2] = 15; // кладём 15 в ячейку с индексом 2a[0] = a[2] + 3; // теперь a[0] равно 18cout << a[2]<< "\n"; // печатает 15
проверь себя1 балл
vector<int> a(8); создаёт вектор из 8 ячеек. Какой индекс у его последней ячейки?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Если программа читает a[n] из вектора размера n, она всегда останавливается с сообщением об ошибке, которое указывает на это место.
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
В условии элементы пронумерованы с 1: a₁, a₂, …, aₙ. Программа читает их в a[0] … a[n - 1]. Какое выражение — 5-й элемент из условия?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
В a лежат 1 2 3 4 5, n равно 5. Что напечатает этот код?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Что напечатает этот код?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
6
50 20 70 10 40 30
3
2
6
1
20
30
50
7 4 9 10 3 6 0
4 10 6 7 9 3
int n;cin >> n;vector<int> a(n);for(int i = 0; i < n; i++){ cin >> a[i];}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector<int> a(n); // n ячеек, от a[0] до a[n - 1] for(int i = 0; i < n; i++){ cin >> a[i];} int q; cin >> q; for(int k = 0; k < q; k++){ int p; cin >> p; // позиция, считая с 1 cout << a[p - 1]<< "\n"; // ... это индекс p - 1} return 0;}
vector<long long> a(n, x); // каждый элемент сначала равен xa[i - 1] = k; // i-й элемент становится равным ka[i - 1] += k; // или увеличивается на k
int wins = 0;for(int i = 0; i < n; i++){ if(a[i]> b[i]){ // раунд i: очки a против очков b wins++;}}
vector<int> a; // ячеек пока нет: a.size() равно 0a.push_back(6); // a — это {6}a.push_back(3); // a — это {6, 3}cout << a.size()<< "\n"; // печатает 2
for(int x : a){ // x принимает значение a[0], потом a[1], ... cout << x << " ";}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); vector<int> evens, odds; // оба сначала пустые int x; while(cin >> x && x != 0){ if(x % 2 == 0){ evens.push_back(x); // новая ячейка в конце evens} else{ odds.push_back(x);}} for(int e : evens){ // каждый элемент evens по порядку cout << e << " ";} for(int o : odds){ cout << o << " ";} cout << "\n"; return 0;}
const int MAXN = 100005;int a[MAXN]; // вне main: MAXN ячеек, все равны 0int main(){ int n; cin >> n; for(int i = 0; i < n; i++){ cin >> a[i];} // ... a[i] работает точно так же, как у вектора}
for(int i = n - 1; i > 0; i--){ cout << a[i]<< " ";}
vector<int> a ={4, 7};a.push_back(1);a.push_back(9);cout << a.size()<< " "<< a[2];
![a[2] = 15: индекс 2 говорит, какая ячейка, а значение 15 — что в ней лежит](/_next/image?url=%2Fapi%2Flessons%2Fcmvf65j02fi6lpn01tpfbfdjf%2Fimages%2F1792409270387-2sgsmz-index-vs-value.png&w=1920&q=75)
![Допустимые индексы — от 0 до n-1; a[5] лежит за пределами вектора из 5 ячеек](/_next/image?url=%2Fapi%2Flessons%2Fcmvf65j02fi6lpn01tpfbfdjf%2Fimages%2F1792409276376-e923wu-valid-indices.png&w=1920&q=75)