Skip to content

← Values, Types, Initialisation step 2 of 4

Medium Primitives

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

  1. 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.

  2. std::size_t for the counter, when you do need the index.

  3. 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.