We can't find the internet
Attempting to reconnect
Something went wrong!
Attempting to reconnect
← Values, Types, Initialisation step 2 of 4
The comparison that is always true
for (int i = 0; i < xs.size(); ++i)
Every C++ programmer has written this. It is in every textbook printed before about 2015. It is also wrong, and the way it is wrong is worth understanding properly rather than memorising.
What actually happens
xs.size() returns std::size_t, which is unsigned. i is int, which
is signed. C++ cannot compare them directly, so it applies the usual
arithmetic conversions, and the rule that fires is:
If the unsigned type is at least as wide as the signed type, the signed operand is converted to unsigned.
On a 64-bit machine std::size_t is 64 bits and int is 32, so i becomes
std::size_t. For a positive i that is harmless.
For a negative one it is not:
int i = -1;
i < xs.size() // -1 becomes 18446744073709551615
// the comparison is TRUE, always
Negative numbers convert by wrapping, so -1 becomes the largest value
std::size_t can hold. A loop that was meant to stop runs off the end of the
container, and reading past the end is undefined behaviour.
Why this is worth a whole problem
Because the failure is invisible in the common case. i is only negative if
you count downwards, or subtract, or the container is empty and you wrote
i <= xs.size() - 1 — and that last one is the trap that catches people:
for (int i = 0; i <= xs.size() - 1; ++i) // xs is empty
xs.size() is 0. 0 - 1 in unsigned arithmetic is not -1; it is
18446744073709551615. The loop that should not run at all runs eighteen
quintillion times.
The three ways out
-
A range-for, when you do not need the index:
for (const int& x : xs)No counter, no comparison, no bug. This is the default.
-
std::size_tfor the counter, when you do need the index. -
std::ssize(xs)(C++20) when you need signed arithmetic on the length, which returns a signed size and lets you subtract safely.
Your task
std::vector<int> last_n(const std::vector<int>& xs, int n);
Return the last n elements of xs, in order. If n is greater than the
size, return everything. If n is zero or negative, return nothing.
The starter computes a start index by subtraction, in the wrong type. It is
right whenever n is small and xs is long, which is every case you would
test by hand.
Stuck?
C++ reference solution
Sign in to attempt this problem and reveal the reference solution.