Español
Português
中文 (中国)
العربية
हिन्दी
Русский
Français
Deutsch
Ελληνικά
Italiano
日本語
한국어
LatineSummary
This lesson opens the sixth unit of the course, devoted to compound data. It explains what the unit is for: to teach how to represent collections of data (sequences of fixed and of variable size, tables and records) and how to process them with the basic algorithms, written by hand and taken from the library, estimating how much they cost; it presents its six lessons and the thread that joins them; it recalls what the unit takes for granted, above all loops with an invariant and passing by const reference; it formulates the problem the unit solves, that of a program that must store data whose quantity it does not know and that, written with separate variables, silently ignores the ones left over; it anticipates cost as the second measure of an algorithm, alongside its correctness; and it shows where it leads, in the following units and in the course Programming in C++ II.
Learning objectives
- Describe the sequence of contents of the unit and explain what each lesson contributes to the next.
- Recall loops, their invariants and parameter passing (by value, by reference and by const reference), and review them if needed.
- Anticipate, with an example, the cost of an algorithm as a second measure of its quality, alongside its correctness.
- Recognize what one is expected to be able to do at the end of the unit, and distinguish it from what will be learned in the following units.
Entry assessment
Before working through the unit, it is worth measuring the starting point. This assessment is a self-assessment: it is not graded, and its only purpose is to guide your study. The first four questions check what the unit takes for granted: the invariant of the loop that looks for a maximum, the passing mode of a large parameter, the number of iterations of two nested loops and unsigned arithmetic. The next six touch, in the order of the lessons, on the central ideas of the unit: the valid indices of a sequence, the creation of a vector, the number of times a size can be divided in half, searching in sorted data, the double index of a table and the danger of storing the data of a single entity in separate collections. No one is obliged to get them right yet, and in some of them “I don’t know yet” is an honest answer: each answer, right or not, explains the point and names the lesson that deals with it. The same skills are measured again at the end, in the synthesis lesson.
Before starting the unit, measure your starting point. It is a short self-assessment: it is not graded and its result is stored only in your browser.
Question 1From earlier unitsThe fragment
int largest{0}; int t{}; while (std::cin >> t) { if (t > largest) { largest = t; } }must leave inlargestthe highest of the temperatures read. With what input does it fail?The first iteration compares the item with 0 and keeps it if it is positive: with a single positive item the result is correct. It is worth following the trace before answering.With>an item equal to the maximum does not replace it, but the maximum is the same number: the repetition does not alter the result.It reveals that the initialization was not checked against the invariant: a correct loop requires the invariant to hold before the first iteration.The desired invariant, “largestis the maximum of what has been read so far”, does not hold at the start, because before reading anything there is no maximum, and the initial 0 beats every negative item. It is corrected by initializing with the first item, after checking that it exists. The lesson Vectors does the same on a stored sequence, and the library expresses it withstd::ranges::max, whose precondition is that the sequence not be empty.Review: Designing correct loops
Question 2From earlier unitsA function computes how many vowels a text of a million characters has, stored in a
std::string, and does not modify it. How should its parameter be declared?Passing by value copies the million characters on each call: it is correct, but it pays a cost that contributes nothing.It does not copy, but it allows the text to be modified needlessly and does not accept a literal or a temporary: it confuses “not copying” with “allowing modification”.The passing mode is part of the interface: passing by value promises the function a copy of its own, and the program must make it.The const reference reads the text without copying it and without permission to modify it, and it also accepts a temporary. In unit 6 this choice becomes the rule: a function that reads a vector of a million items receives it asconst std::vector<int>&, and the unnecessary copy becomes the most frequent cost error.Review: Parameters and scope
Question 3From earlier unitsHow many times is
++countexecuted infor (int i{0}; i < 6; ++i) { for (int j{0}; j < i; ++j) { ++count; } }?Correct answer:
The inner loop makes 0 iterations with , one with , and so on up to 5 with : in total , which is . The lesson The cost of an algorithm generalizes the count: two loops that go through all the pairs of items make iterations, and that number decides whether an algorithm is usable for a million items.Review: Loops
Question 4From earlier unitsWhat does
std::println("{}", 0u - 1);write on a system with a 32-bitunsigned int?It believes that an unsigned type admits negative values.It believes that the subtraction stops at the smallest value of the type; unsigned arithmetic wraps around, it does not saturate.It confuses a possible warning with an error: the expression is valid and its value is defined.Unsigned arithmetic is modular: subtracting 1 from 0 wraps around to the largest value of the type, . Unit 6 measures sizes withstd::size_t, which is also unsigned, sov.size() - 1with an empty vector does not give , but an enormous number; the lesson Arrays warns about that subtraction, and the lesson Vectors shows the loop that, because of it, goes out of bounds.Question 5In a sequence of elements numbered as in C++, which indices designate an element?
It numbers from one, as in everyday language; in C++,a[n]is already outside the sequence.It is the most frequent off-by-one error: it counts indices for elements.It is an honest answer: lesson 6.1 explains it, with the reason why counting starts from zero.The C++ index counts from zero, because it is the offset from the first element: the first isa[0]and the lasta[n - 1]. Accessing with[]an index outside that interval is undefined behavior, and the lesson Arrays teaches how to prove, with the loop invariant, that each access is valid.Review: Arrays
Question 6What does
vcontain afterstd::vector<int> v(3, 7);?It reads the parentheses as if they were braces.It swaps the roles of the two numbers.It is an honest answer: lesson 6.2 presents the vector and its forms of creation.With parentheses, the first number is the count and the second the value of each element; with braces,std::vector<int> v{3, 7};is the list of the elements, the 3 and the 7. The vector is the first type in the course in which braces and parentheses say different things, and the lesson Vectors shows it with a program.Review: Vectors
Question 7How many iterations does
for (int m{1024}; m > 1; m /= 2) { ... }make?Correct answer:
The values ofmat the start of each iteration are 1024, 512, 256, 128, 64, 32, 16, 8, 4 and 2: ten iterations, because , and ten is . An algorithm that reduces its problem by half at each step takes on the order of steps, and the lesson The cost of an algorithm calls it logarithmic: with a billion items, about thirty are enough.Review: The cost of an algorithm
Question 8A phone book has a million names in alphabetical order. To find one, it is opened in the middle, the half where the name cannot be is discarded, and the process is repeated with the other half. At most, how many times must it be opened?
It is the count of the search that examines the names one by one: without taking advantage of the order, on average half of the phone book is gone through.It is the square root of a million: it confuses dividing the stretch in half with dividing it into blocks.It uses the decimal logarithm: each opening discards half, not nine tenths.Each opening halves the stretch where the name can be, and exceeds a million: after twenty halvings a single name remains. It is the binary search of the lesson Searching and sorting, which works only if the data are sorted and which is justified with an invariant.Review: Searching and sorting
Question 9With
std::vector<std::vector<int>> t{{1, 2, 3}, {4, 5, 6}};, what are the values oft[1][0]andt.size()?It reads the first index as the column and counts the columns instead of the rows.It believes thatsize()counts all the cells of the table.It is an honest answer: lesson 6.5 presents tables as vectors of vectors.Question 10A program stores the names of a group in one vector and their grades in another, so that the grade
grades[i]is that ofnames[i]. If it sorts only the vector of grades, what happens?For the compiler the two vectors are independent: the relation exists only in the mind of whoever wrote the program.The algorithm receives a single vector and knows nothing of the existence of the other.Every access is valid and every result is defined: the defect is one of logic, and that is why neither of the two sanitizers of the course reports it (the one for memory errors, AddressSanitizer, and the one for undefined behavior, UndefinedBehaviorSanitizer).
Loading the content…
Completed
Sign in to save your progress