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

Записи

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

До сих пор каждая коллекция курса хранила данные одного-единственного типа: оценки, значения роста, ячейки таблицы. Сущности задачи, напротив, обладают несколькими признаками разных типов: у студента есть имя и оценка; у книги есть название, автор и год. Этот урок вводит запись, составной тип, который сам программист определяет с помощью struct, чтобы собрать эти признаки под одним именем. Урок начинается с того, зачем нужна запись, то есть с хрупкости параллельных векторов; продолжается определением struct, его полями с начальными значениями и созданием записей фигурными скобками и назначенными инициализаторами; затем рассматривает записи как параметры и как результаты функций; векторы записей, которые обходятся со структурными привязками, сортируются и просматриваются при поиске по одному полю, вместе с вопросом об устойчивой сортировке; и завершается искусством моделировать задачу типами, отражающими её предметную область.

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

  1. Определять struct с полями и начальными значениями и создавать записи инициализацией фигурными скобками, в том числе с назначенными инициализаторами.
  2. Писать функции, которые принимают и возвращают записи, выбирая способ передачи.
  3. Сортировать вектор записей и искать в нём по одному полю с помощью std::ranges::sort, std::ranges::stable_sort и std::ranges::find с проекцией и отличать устойчивую сортировку от неустойчивой.
  4. Моделировать записями данные задачи и обосновывать выбор полей и типов.

Группировка данных

Параллельные векторы

Пусть программа должна хранить для каждого студента группы его имя, оценку и возраст. С тем, что изучено до урока Таблицы, решение под рукой состоит из трёх векторов, по одному на признак, с соглашением, что индекс ii обозначает одного и того же человека во всех трёх: names[i], grades[i] и ages[i]. Они называются параллельными векторами. Таблица не подходит, потому что все её ячейки должны быть одного типа, а имя не является числом.

Программа на C++
#include <algorithm>#include <cstddef>#include <print>#include <string>#include <vector>​int main(){    const std::vector<std::string> names{"Анна", "Луис", "Ева"};    std::vector<int> grades{6, 4, 7};    const std::vector<int> ages{19, 22, 20};    std::ranges::sort(grades);    for (std::size_t i{0}; i < names.size(); ++i) {        std::println("{}: оценка {}, возраст {}", names[i], grades[i], ages[i]);    }}
Вывод
Анна: оценка 4, возраст 19Луис: оценка 6, возраст 22Ева: оценка 7, возраст 20

Программа хотела упорядочить студентов по оценке, а упорядочила только оценки. Она компилируется без предупреждений, и ни санитайзер ошибок памяти AddressSanitizer, ни санитайзер неопределённого поведения UndefinedBehaviorSanitizer ничего не сообщают; тем не менее её вывод ложен: у Анны было 6, а в выводе у неё 4. Соглашение, связывавшее три вектора, нигде не записано так, чтобы компилятор мог его прочесть, и потому ничто не мешает его нарушить. Отсюда следует хрупкость параллельных векторов: всякую операцию, которая перемещает, добавляет или удаляет элемент, нужно повторить, одинаково и в том же порядке, во всех векторах; и достаточно забыть один, чтобы данные незаметно испортились.

ПримерСтроки, которые расходятся, и карточки, которые перемещаются целиком

Три параллельных вектора против одного вектора карточек, каждая из которых содержит три сведения об одном человеке.

Доказательство

  1. Столбец 0 описывает одного человека: names[0], grades[0] и ages[0] суть имя, оценка и возраст Анны. Связь между ними обеспечивает только индекс.

  2. std::ranges::sort(grades) переупорядочивает только одну строку. Две другие об этом не знают: столбец 0 теперь соединяет имя Анны, оценку Луиса и возраст Анны, которые не принадлежат никому.

  3. Альтернатива: один вектор, элементы которого суть карточки. Каждая карточка содержит три сведения об одном человеке, и связь между ними есть уже не соглашение об индексах, а сама карточка.

  4. Сортировка по оценке перемещает карточки целиком: карточка Луиса переходит на первое место вместе с его именем и возрастом. Никакое сведение не может отделиться от остальных, потому что операция не видит их по отдельности.

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