Перейти к содержимому
Topos Uranos
Русский

Массивы

Краткое содержание

До сих пор каждое значение в курсе жило в собственной переменной, под собственным именем; но многие данные одного типа, например температуры за неделю, нельзя обойти циклом, если у каждого из них своё имя. Этот урок вводит первую структуру данных курса, индексированную последовательность: элементы одного типа, расположенные в соседних ячейках памяти и пронумерованные с нуля. В современном C++ она записывается с помощью std::array, размер которого фиксируется при компиляции. Изучаются его объявление, тип индексов std::size_t и два способа обхода: по индексу и циклом for по диапазону. Устанавливается правило, которое управляет всем разделом: индекс допустим, если он лежит в пределах от 0 до размера минус один, и при каждом обращении в цикле эта допустимость обосновывается инвариантом. Показывается, что происходит при нарушении правила, а это неопределённое поведение, и [] сравнивается с доступом с проверкой .at(). Наконец, представлены массивы в стиле C, чтобы читать чужой код.

Цели обучения

  1. Объявлять, инициализировать и обходить std::array по индексам и циклом for по диапазону.
  2. Обосновывать с помощью инварианта цикла, что индекс при каждом обращении находится в допустимых пределах.
  3. Различать доступ через [], который стандарт не проверяет, и доступ через .at(), который проверяется всегда, и объяснять, когда уместен каждый из них.
  4. Читать код с массивами в стиле C и объяснять их недостатки по сравнению с std::array.

Индексированная последовательность

Много данных, одно имя

Чтобы вычислить среднее значение температур за неделю средствами, изученными до сих пор, понадобились бы семь переменных, monday, tuesday и так вплоть до sunday, и сумма из семи слагаемых. Для температур за год их было бы 365, и никакой цикл не смог бы их обойти, потому что в теле цикла имя переменной всегда одно и то же. Недостаёт имени для всей совокупности и номера для каждого элемента, чтобы номер мог быть переменной, которую цикл продвигает вперёд.

Индексированная последовательность есть именно это: совокупность из nn элементов одного типа, хранящихся друг за другом в соседних ячейках памяти и обозначаемых своей позицией, которая называется индексом. Математике этот объект знаком: конечная последовательность (a0,a1,…,an−1)(a_0, a_1, \dots, a_{n-1}), в которой aia_i обозначает элемент на месте ii, или вектор, как в курсе «Алгебра и геометрия I». В C++ пишут a[i], и индексом может быть любое целочисленное выражение: 2, i, i + 1.

Почему с нуля

В C++, как и в большинстве современных языков, первый элемент имеет индекс 0, а последний индекс n−1n - 1. Причина не в капризной условности, а в способе, которым находят элемент: если последовательность начинается с некоторого адреса памяти и каждый элемент занимает ss байт, то элемент с индексом ii находится по начальному адресу плюс i⋅si \cdot s. Следовательно, индекс есть смещение: количество элементов, которые нужно пропустить, начиная с первого. Первый элемент отстоит от самого себя на ноль шагов.

Отсюда следует определение, которое управляет всем этим разделом: в последовательности из nn элементов индекс ii допустим тогда и только тогда, когда 0≤i<n0 \leq i < n. Правое неравенство строгое, и именно оно служит источником самой частой ошибки с последовательностями, ошибки на единицу: написать i≤ni \leq n там, где следовало написать i<ni < n, или начать с 1 там, где следовало начать с 0. Индекс, равный nn, обозначает не последний элемент, а ячейку, которая идёт за последовательностью и ей не принадлежит.