Skip to content
Topos Uranos
English

Records

Summary

Until now, every collection in the course held data of a single type: grades, heights, cells of a table. The entities of a problem, by contrast, have several attributes of different types: a student has a name and a grade; a book, a title, an author and a year. This lesson introduces the record, the compound type that programmers define themselves with struct to group those attributes under a single name. It begins with the reason for records, the fragility of parallel vectors; it continues with the definition of a struct, its fields with default member initializers, and the creation of records with braces and with designated initializers; then come records as parameters and as results of functions, and vectors of records, which are traversed with structured bindings and sorted and searched by a field, together with the question of stable sorting; and it closes with the art of modeling a problem with types that reflect its domain.

Learning objectives

  1. Define a struct with fields and default member initializers, and create records with brace initialization, including designated initializers.
  2. Write functions that take and return records, choosing the passing mode.
  3. Sort and search a vector of records by a field with std::ranges::sort, std::ranges::stable_sort and std::ranges::find with a projection, and distinguish a stable sort from one that is not.
  4. Model the data of a problem with records and justify the choice of fields and types.

Grouping data

Parallel vectors

Suppose a program must store, for each student in a group, their name, their grade and their age. With what has been seen up to the lesson Tables, the obvious solution is three vectors, one per attribute, with the convention that the index ii designates the same person in all three: names[i], grades[i] and ages[i]. These are called parallel vectors. A table will not do, because its cells must all be of the same type, and a name is not a number.

C++ program
#include <algorithm>#include <cstddef>#include <print>#include <string>#include <vector>​int main(){    const std::vector<std::string> names{"Ana", "Luis", "Eva"};    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("{}: grade {}, age {}", names[i], grades[i], ages[i]);    }}
Output
Ana: grade 4, age 19Luis: grade 6, age 22Eva: grade 7, age 20

The program meant to sort the students by grade, and it sorted only the grades. It compiles without warnings, and neither the memory error sanitizer, AddressSanitizer, nor the undefined behavior sanitizer, UndefinedBehaviorSanitizer, has anything to report; yet its output is false: Ana had a 6 and appears with a 4. The convention that bound the three vectors is not written anywhere the compiler can read, so nothing prevents breaking it. From this follows the fragility of parallel vectors: every operation that moves, adds or removes an element must be repeated, identically and in the same order, in all of them; and forgetting one is enough to corrupt the data silently.

ExampleRows that fall out of line and index cards that move whole

Three parallel vectors versus one vector of index cards, each holding the three data items of one person.

Proof

  1. Column 0 describes one person: names[0], grades[0] and ages[0] are Ana’s name, grade and age. The only link is the index.

  2. std::ranges::sort(grades) reorders a single row. The other two do not notice: column 0 now brings together Ana’s name, Luis’s grade and Ana’s age, which belong to nobody.

  3. The alternative: a single vector whose elements are index cards. Each card contains the three data items of one person, and the link between them is no longer a convention about indices but the card itself.

  4. Sorting by grade moves whole cards: Luis’s card goes to first place together with the name and the age written on it. No data item can be separated from the others, because the operation does not see them separately.

If this is so, what the problem calls for is a type whose values are cards: a value that contains a name, a grade and an age, and that is copied, passed to a function, stored in a vector and sorted as a whole. C++ does not supply it ready-made, because the cards of each problem are different; but it lets the programmer define it. That type is the record.