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

Составные данные: итоги и задачи повышенной трудности

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

Этот урок завершает шестой раздел курса, посвящённый составным данным. Он восстанавливает цепочку понятий, ведущую от индексированной последовательности к записи через растущую последовательность, сложность алгоритма, поиск и сортировку и таблицы; отделяет то, что из этого верно для любого языка, от того, что свойственно C++; собирает неопределённое поведение раздела вместе с тем, что останавливает библиотека, что останавливает санитайзер и о чём не сообщает никто; повторяет в итоговой проверке навыки входной; и заканчивается шестью задачами повышенной трудности, объединяющими весь раздел.

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

  1. Представлять коллекции и сущности подходящим типом (массивом, вектором, таблицей или записью) и обосновывать выбор формой данных.
  2. Обрабатывать коллекции правильными алгоритмами, написанными вручную и обоснованными инвариантом или взятыми из библиотеки с соблюдением их предусловий.
  3. Оценивать сложность алгоритма, подсчитывая его доминирующие операции, и проверять оценку измерением.
  4. Распознавать неопределённое поведение раздела (доступ за границами, недействительную ссылку, переполненную середину, нарушенное предусловие библиотеки) и переписывать программу без него.
  5. Отделять в изученном в разделе то, что верно для любого языка, от того, что свойственно C++.

Чего достиг раздел

Раздел ставил целью научить представлять коллекции данных и обрабатывать их базовыми алгоритмами, оценивая их стоимость. Цель достигнута с опорой только на то, что введение объявило известным: циклы с инвариантом, функции и способы передачи параметров, арифметику целых чисел. Программа о баллах, которая с пятью переменными молча отбрасывала лишние данные, теперь пишется с вектором; а вопрос о совпадениях, который при переборе всех пар требовал минут для миллиона данных, решается сортировкой и сравнением соседей.

Массивы

Урок Массивы представил std::array, последовательность фиксированного размера, индексы которой отсчитываются от нуля, потому что они являются смещениями. Он установил, что индекс ii допустим тогда и только тогда, когда 0≤i<n0 \leq i < n, что каждый доступ через [] требует доказать это инвариантом цикла и что доступ за границами есть неопределённое поведение, которое .at() превращает в определённую остановку; ввёл std::size_t и научил читать массивы в стиле C.

Векторы

Урок Векторы представил последовательность, растущую с помощью push_back, и установил, когда ряд нужно хранить: если какое-либо решение о значении зависит от последующих значений. Он ввёл канонические обходы (накопление, фильтрацию, преобразование) с их инвариантами и сокращениями в библиотеке (std::ranges::count, std::ranges::max, std::ranges::fold_left), правило передачи вектора и различие между размером и ёмкостью, из которого следуют постоянная в среднем стоимость push_back и то, что ссылки становятся недействительными, когда вектор переезжает.

Сложность алгоритма

Урок Сложность алгоритма добавил второй вопрос: подсчитывать доминирующую операцию в худшем случае, классифицировать по порядку роста, предсказывать эффект удвоения nn и измерять с помощью std::chrono::steady_clock, с оптимизацией, без санитайзеров, повторяя и беря медиану.

Поиск и сортировка

Урок Поиск и сортировка обосновал двоичный поиск инвариантом и мерой; написал сортировку выбором и сортировку вставками, подсчитав их сравнения; представил алгоритмы библиотеки диапазонов с предусловием упорядоченности, которое никто не проверяет; и вычислил, когда выгодно отсортировать данные перед поиском.

Таблицы

Урок Таблицы обходил таблицы по строкам и по столбцам, вычислил транспонированную матрицу и произведение матриц с его кубической сложностью, подсчитал соседние клетки, не выходя за края, и сохранил таблицу в плоском векторе с индексом i⋅columns+ji \cdot \mathit{columns} + j.

Записи

Урок Записи заменил параллельные векторы на struct с начальным значением в каждом поле; научил передавать и возвращать записи, сортировать их и искать по полю с помощью проекции, сортировать по нескольким критериям с помощью std::ranges::stable_sort и моделировать задачу записями, которые содержат записи и векторы.