Skip to content
Topos Uranos
English

Synthesis and challenges: compound data

Summary

This lesson closes the sixth unit of the course, devoted to compound data. It reconstructs the chain of concepts that runs from the indexed sequence to the record, by way of the sequence that grows, the cost of an algorithm, searching and sorting, and tables; it separates what of all this holds in any language from what is specific to C++; it gathers the undefined behavior of the unit, with what the library stops, what the sanitizer stops and what nobody flags; it repeats in its exit assessment the skills of the entry assessment; and it ends with six challenges that combine the whole unit.

Learning objectives

  1. Represent collections and entities with the appropriate type (array, vector, table or record), and justify the choice by the shape of the data.
  2. Process collections with correct algorithms, written by hand and justified with an invariant, or taken from the library while respecting their preconditions.
  3. Estimate the cost of an algorithm by counting its dominant operations, and check the estimate with a measurement.
  4. Recognize the undefined behavior of the unit (out-of-bounds access, the invalidated reference, the overflowing midpoint, the violated library precondition) and rewrite the program without it.
  5. Separate, in what was learned in the unit, what holds in any language from what is specific to C++.

What the unit achieved

The unit set out to teach how to represent collections of data and how to process them with the basic algorithms, estimating how much they cost. It has done so relying only on what the introduction declared it took for granted: loops with an invariant, functions and their passing modes, integer arithmetic. The scores program, which with five variables silently ignored the surplus data, is now written with a vector; and the question about ties, which with all the pairs took minutes for a million items, is answered by sorting and comparing neighbors.

Arrays

The lesson Arrays presented std::array, the fixed-size sequence, whose indices count from zero because they are offsets. It established that the index ii is valid if and only if 0≤i<n0 \leq i < n, that each access with [] requires proving it with the loop invariant, and that out-of-bounds access is undefined behavior, which .at() turns into a defined stop; it introduced std::size_t and taught how to read C arrays.

Vectors

The lesson Vectors presented the sequence that grows with push_back and settled when a series must be stored: if some decision about an item depends on later items. It established the canonical traversals (accumulate, filter, transform) with their invariants and their shorthands in the library (std::ranges::count, std::ranges::max, std::ranges::fold_left), the rule for passing a vector, and the difference between size and capacity, from which follow the constant average cost of push_back and the invalidation of references when the vector moves.

The cost of an algorithm

The lesson The cost of an algorithm added the second question: count the dominant operation in the worst case, classify by order of growth, predict the effect of doubling nn, and measure with std::chrono::steady_clock, with optimization, without sanitizers, repeating and taking the median.

Searching and sorting

The lesson Searching and sorting justified binary search with its invariant and its measure; it wrote selection sort and insertion sort, counting their comparisons; it presented the ranges algorithms with the precondition of order, which nobody checks; and it computed when it pays to sort before searching.

Tables

The lesson Tables traversed tables by rows and by columns, computed the transpose and the product of matrices, with its cubic cost, counted neighbors without leaving the edges, and stored a table in a flat vector with the index i⋅columns+ji \cdot \mathit{columns} + j.

Records

The lesson Records replaced parallel vectors with the struct, with a default value in each field; it taught how to pass and return records, how to sort and search them by a field with a projection, how to sort by several keys with std::ranges::stable_sort, and how to model a problem with records that contain records and vectors.