L04 - Массивы

О чём лекция

Сто чисел не заведёшь сотней переменных, а перебирать переменные в цикле нельзя. Массив решает это: элементы одного типа подряд в памяти, доступ по номеру. Главное в лекции — массив и указатель тесно связаны: массив почти везде превращается в указатель на нулевой элемент, а p[i] — это просто *(p + i). Здесь же находит применение Арифметика указателей из L03. В конце — динамические массивы, размер которых можно узнать во время работы программы.

Маршрут

Зачем → задача «100 чисел по возрастанию»
Что такое массив и как его заполнить → Массив
Почему массив ведёт себя как указатель → Указатель, Арифметика указателей
Размер массива и размер указателя → sizeof
Массивы массивов → многомерные массивы
Массив неизвестного заранее размера → Динамический массив, Динамическая память

1. Проблема

Задача 1. Вводятся 3 числа, вывести их в порядке возрастания:

int a, b, c;
std::cin >> a >> b >> c;
const int min = std::min(a, std::min(b, c));
const int max = std::max(a, std::max(b, c));
std::cout << min << ' ' << a + b + c - min - max << ' ' << max;

Среднее — сумма минус крайние.

Задача 2. То же для 5 чисел — int a, b, c, d, e; и дальше уже неясно, как продолжать.

Задача 3. То же для 100 чисел:

придумывать и записывать 100 разных переменных — нерациональная трата времени;
циклы сильно упростили бы работу, но перебирать переменные в цикле невозможно.

2. Массив

Массив (array) — последовательность элементов одного типа, расположенных непрерывно в памяти, к которым есть доступ по индексу через некоторый уникальный идентификатор.

int array[10];

массив хранит 10 int;
к каждому элементу обращаются через имя array операцией [], нумерация с нуля:
```
array[0], array[2], array[9];
```
гарантируется, что элементы идут в памяти подряд, без разрывов:
```
&a[i] - &a[j] == i - j;
```

Важно: выражение в квадратных скобках при объявлении должно быть положительной константой, известной на этапе компиляции:

int n;
std::cin >> n;
int array[n];  // по Стандарту C++ так нельзя

Как быть, если размер узнаётся только во время работы, — раздел 9.

3. Решение задачи 3

int array[100];
for (int i = 0; i < 100; ++i) {
  std::cin >> array[i];
}
for (int i = 0; i < 100; ++i) {
  int min_idx = 0;  // индекс минимального
  for (int j = 1; j < 100; ++j) {
    if (array[j] < array[min_idx]) min_idx = j;
  }
  std::cout << array[min_idx] << ' ';
  array[min_idx] = 1'000'000;  // предполагаем, что значения меньше 1'000'000
}

Сто раз ищем минимум среди всех элементов, печатаем его и «вычёркиваем» — заменяем числом, заведомо большим любого входного. Следующий поиск минимума его уже не выберет.

Не из лекции

Это родственник сортировки выбором из АиСД, см. Квадратичные сортировки: на каждом шаге ищется минимум, итого $100 \cdot 99$ сравнений, $Θ (N^{2})$ . Отличие — элементы не переставляются, а затираются, поэтому массив после работы испорчен.

Решение держится на предположении из комментария. Если во входе встретится число $\geq 1000000$ , «вычеркнутые» элементы начнут выбираться повторно.

4. Операции над массивами

int array[10];
 
array[1];                     // операция доступа по индексу
sizeof(array);                // 40: суммарный размер в байтах
sizeof(array) / sizeof(int);  // 10: количество элементов
&array;                       // адрес массива ( int(*)[10] )

int(*)[10] читается как «указатель на массив из 10 int» — это не то же самое, что int*, см. раздел 6.

5. Инициализация массивов

Неинициализированный массив:

int a[10];

Заполнение нулями:

int a[10]{};
int b[20]{};

Ошибка в лонгриде: int a[10]();

В материалах для заполнения нулями приведено int a[10](); int b[20]();. Это не компилируется: declaration of 'a' as array of functions (GCC 16.2). Круглые скобки после имени читаются как «функция без параметров», и получается массив функций — а такие массивы запрещены (правило 1 в разделе 8). Выше исправлено на {}. Круглые скобки работают только с new: new int[10]() — динамический массив из нулей.

Заполнение значениями:

int a[5]{1, 2, 3};  // 1 2 3 0 0 (остальное заполняется нулями)
int b[]{1, 2, 3};   // 1 2 3 (размер вычисляется автоматически)

Ошибка в лонгриде: int b[1]{1, 2, 3}

В материалах вторая строка — int b[1]{1, 2, 3}; // размер вычисляется автоматически. Так не компилируется: too many initializers for 'int [1]'. Чтобы размер вычислился, скобки оставляют пустыми: int b[]{1, 2, 3}.

Копирование запрещено:

int b[5] = a;  // CE

6. Связь массивов и указателей

В большинстве ситуаций массив автоматически преобразуется в указатель на свой нулевой элемент:

int array[10];
 
std::cout << array;      // выводится адрес нулевого элемента
std::cout << array + 5;  // адрес пятого элемента

Верно и обратное: к указателю можно применять [], то есть обращаться с ним как с массивом:

int* p = array;
std::cout << p[2];  // второй элемент массива
p += 5;
std::cout << p[2];  // седьмой элемент массива

Номера элементов здесь — индексы с нуля: «пятый» — array[5], шестой по счёту. После p += 5 указатель смотрит на array[5], и p[2] — это array[7].

Как это работает:

p[2];  // равносильно *(p + 2)
2[p];  // да, настолько равносильно *(2 + p)

Индексирование — это сдвиг указателя плюс разыменование. Сложение коммутативно, поэтому 2[p] тоже компилируется. Вот зачем нужна Арифметика указателей: внутри массива сдвиг на n — переход к элементу на n дальше.

Массив — не указатель

Важно понимать, что массив ≠ указатель на первый элемент:

int array[10];
int* p = array;
 
std::cout << sizeof(array) << ' ' << sizeof(p);  // 40 8
 
&array;  // имеет тип int(*)[10]
&p;      // имеет тип int**

sizeof и & — те контексты, где массив в указатель не превращается. Но в большинстве ситуаций массив действительно ведёт себя как указатель.

Сравнение массивов

Сравнивать массивы через >, <, == и т. п. бессмысленно: на деле сравниваются указатели на первые элементы.

int a[]{1, 2, 3};
int b[]{1, 2, 3};
 
a == a;  // всегда true
a == b;  // всегда false

Не из лекции

Сравнение массивов в C++20 объявлено устаревшим, а в C++26 запрещено. GCC 16.2 с -std=c++20 предупреждает: comparison between two arrays is deprecated in C++20, с -std=c++26 — уже ошибка.

7. Многомерные массивы

Массивы могут иметь несколько размерностей:

int a[10];  // одномерный массив
a[1];       // обращение к элементу
 
int b[5][20];  // двумерный массив
b[3][11];      // обращение к элементу
 
int c[7][9][3];  // трёхмерный массив
c[3][8][0];      // обращение к элементу

Инициализация

int a[2][3]{1, 2, 3, 4};  // заполнение по строкам
// 1 2 3
// 4 0 0
 
int b[][2]{1, 2, 3, 4};  // первая размерность может быть выведена
// 1 2
// 3 4
 
int c[3][2]{{1, 2}, {3, 4}, {5, 6}};
// 1 2
// 3 4
// 5 6

Ошибка в лонгриде: int b[1][2]{1, 2, 3, 4}

В материалах вторая строка — int b[1][2]{…}; // первая размерность может быть выведена. Так первая размерность задана, и равна 1: too many initializers for 'int [1][2]' (GCC 16.2). Чтобы её вывели, скобки оставляют пустыми: int b[][2]. Выводится только первая размерность, остальные обязательны.

Многомерные массивы и указатели

Как и одномерные, многомерные массивы приводятся к указателю на первый элемент. Первый элемент многомерного массива — массив меньшей размерности:

int a[1][2][3];
a[0];  // тип int[2][3]
 
int b[2][3];
b[1][1] <=> *(b[1] + 1) <=> *(*(b + 1) + 1) <=> *(&b[0][0] + 3 + 1);

Цепочка разворачивает b[1][1] по правилу p[i] ≡ *(p + i):

b + 1 сдвигается на одну строку — на sizeof(int[3]) = 12 байт;
*(b + 1) — это строка b[1], массив int[3], который тут же превращается в int*;
+ 1 сдвигает уже на один int.

Последняя форма считает от самого первого int: строки лежат подряд, b[1] начинается через 3 элемента, нужный — ещё через 1.

Не из лекции

Последняя форма работает на практике, но формально стандарт разрешает арифметику указателей только в пределах одного массива, а &b[0][0] указывает в строку b[0] из трёх элементов. Шаг за её пределы строгий анализатор вправе считать неопределённым поведением. Для понимания раскладки в памяти пример полезен, в коде лучше писать b[1][1].

8. Правила работы с массивами

1. Нельзя создавать массивы ссылок и массивы функций, но можно — массивы указателей и массивы указателей на функции:

int& a[10];     // Compilation error
int b[20](int);  // Compilation error
 
// error: declaration of 'a' as array of references
// error: declaration of 'b' as array of functions
 
int* c[30];          // Ok (массив указателей)
int (*d[40])(int);   // Ok (массив указателей на функции)

2. Нельзя создать массив с неизвестным числом элементов, но можно его объявить:

int a[];         // Compilation error (определение)
int b[] = {1, 2, 3};  // Ok: int[3]
extern int c[];  // Ok (объявление)
 
// error: storage size of 'a' isn't known

Разница между объявлением и определением — из L02, см. Объявление и определение.

3. При сравнении массивов сравниваются адреса нулевых элементов, а не значения. Результат сравнения на равенство для разных массивов всегда false:

int a[3]{1, 2, 3};
int b[3]{1, 2, 3};
std::cout << (a == b) << ' ' << (a == a);  // 0 1

4. Массивы нельзя присваивать друг другу (исключение — строки при инициализации):

int a[3];
int b[3]{1, 2, 3};
a = b;  // Compilation error

Не из лекции

«Строки при инициализации» — это char s[] = "abc";: массив char заполняется из строкового литерала. Формально это инициализация, а не присваивание; s = "xyz"; потом тоже не скомпилируется.

5. Лайфхак: если массив — поле структуры или класса, присваивание чудесным образом начинает работать:

struct S {
  int array[3];
};
 
S c{1, 2, 3};
S d{4, 5, 6};
c = d;  // Ok (c.array == {4, 5, 6})

Структуры в курсе ещё не разбирались.

9. Динамические массивы

Создаются оператором new[], который возвращает указатель на нулевой элемент массива:

int* array = new int[10];

Результат — указатель на элемент (не на массив!), поэтому в контекстах из раздела 6 он ведёт себя как указатель, а не как массив:

sizeof(new int[10]) == sizeof(int*);  // 8
sizeof(*array) == sizeof(int);        // true

Количество элементов через sizeof уже не узнать — его нужно хранить отдельно.

Не из лекции

Первая строка ничего не выделяет: sizeof не вычисляет свой операнд, так что утечки тут нет.

Размер стекового массива, в отличие от динамического, обязан быть константой времени компиляции:

int n = 10;
// Работаем с n ...
int a[n]{1, 2, 3};         // стандартом запрещено, но компиляторы позволяют
int* b = new int[n]{1, 2, 3};  // Ok

Warning: ISO C++ forbids variable length array 'a'

Не из лекции

Предупреждение GCC выдаёт с флагом -pedantic (или -Wvla); без него массив переменной длины (variable length array, VLA) молча собирается. Это расширение компилятора, а не C++.

Во второй строке размер должен вместить инициализатор. При n < 3 new int[n]{1, 2, 3} бросает исключение std::bad_array_new_length (проверено на GCC 16.2 при n == 2).

И не забывайте убирать за собой. Важно: память, выделенную через new[], освобождают через delete[]:

int* array = new int[10];
// ...
delete[] array;

Не из лекции

delete без скобок для массива — неопределённое поведение. GCC 16.2 предупреждает уже при компиляции (-Wmismatched-new-delete), а -fsanitize=address падает с alloc-dealloc-mismatch (operator new [] vs operator delete).

Подробнее — Динамический массив.

10. Многомерные динамические массивы

Многомерный динамический массив можно моделировать массивом массивов:

// выделение памяти
int** array = new int*[n];
for (int i = 0; i < n; ++i) {
  array[i] = new int[m];
}
 
// заполнение
for (int i = 0; i < n; ++i) {
  for (int j = 0; j < m; ++j) {
    std::cin >> array[i][j];
  }
}
 
// очищение
for (int i = 0; i < n; ++i) {
  delete[] array[i];
}
delete[] array;

Сначала массив из n указателей, потом каждому — своя строка из m чисел. array[i][j] работает так же, как у обычного двумерного массива: array[i] — указатель на строку, [j] — элемент в ней. Освобождать в обратном порядке: сначала строки, потом массив указателей. Если удалить array первым, указатели на строки потеряются — утечка.

Грабли

Размер стекового массива — константа времени компиляции. int a[n] с n из std::cin — расширение GCC, а не C++.
int a[10](); — не массив нулей, а ошибка «массив функций». Нули — int a[10]{};.
Чтобы размер вывелся, скобки пустые: int b[]{1, 2, 3}, int b[][2]{…}.
Нумерация с нуля: array[9] — последний из десяти, array[10] — выход за границы, Неопределённое поведение.
sizeof(array) / sizeof(int) работает только для настоящего массива. Для указателя, в том числе полученного из new[], это 8 / 4.
a == b сравнивает адреса, а не содержимое.
Массив нельзя присвоить и скопировать через =.
new[] — в паре с delete[], не с delete.
Двумерный динамический массив освобождают построчно, потом сам массив указателей.

После этой лекции должно получаться

объяснить, почему 100 чисел не обработать сотней переменных;
записать массив из 5 элементов с инициализацией 1 2 3 0 0;
объяснить, почему p[2] и 2[p] — одно и то же;
сказать, чему равны sizeof(array) и sizeof(p) для int array[10], int* p = array — и почему они разные;
развернуть b[1][1] в выражение через * и +;
объяснить, почему a == b для двух одинаковых массивов даёт false;
создать динамический массив размера n, введённого с клавиатуры, и правильно его освободить;
выделить и освободить двумерный динамический массив n × m.

Конспекты МФТИ

Проводник

L04 - Массивы

Маршрут

1. Проблема

2. Массив

3. Решение задачи 3

4. Операции над массивами

5. Инициализация массивов

6. Связь массивов и указателей

Массив — не указатель

Сравнение массивов

7. Многомерные массивы

Инициализация

Многомерные массивы и указатели

8. Правила работы с массивами

9. Динамические массивы

10. Многомерные динамические массивы

Грабли

После этой лекции должно получаться

Оглавление

Вид графа

Обратные ссылки

Недавно обновлённое

АиСД L05 - Быстрая сортировка и сортировка подсчётом

АиСД L06 - Динамическое программирование

L05 - Функции и ссылки

Быстрая сортировка

Динамическое программирование