Loops: while, do-while and for

Start with the problem

Adding the numbers from 1 to 3 by hand is easy: write sum = sum + 1;, then sum = sum + 2;, then sum = sum + 3;. Adding the numbers from 1 to 1,000 that way is absurd, and the count may not even be known until the program runs. What you want to say is: do this step again and again, as long as a condition holds.

A loop does exactly that. The three kinds in C++ differ in where they test the condition and how much setup they put in one place, but underneath they are the same machine mechanism.

How the idea works

The while loop. It tests first, then runs the body, then tests again:

int i = 1;
while (i <= 3) {
    sum = sum + i;
    ++i;
}

If the condition is false on the first test, the body never runs. The body must change something the condition reads, or the loop never ends.

The do-while loop. It runs the body first and tests afterwards, so the body always runs at least once. Note the semicolon at the end:

do {
    showMenu();
    choice = readChoice();
} while (choice != 'q');

The for loop. The header gathers the setup, the test and the update in one line. The three parts run in an order different from the order in which they are written:

1. The initialization runs once, before anything else.
2. The condition is tested before every iteration, including the first.
3. The step runs after every body, before the next test.

The trace above follows all three through for (int i = 1; i <= 3; ++i). The initialization appears in step 2, the test and the backward jump in steps 3, 5 and 7, and the final failed test in step 9. A variable declared in the initialization, like i here, exists only inside the loop, and step 10 shows it going out of scope.

break and continue. The statement break leaves the innermost loop at once. The statement continue skips the rest of the current iteration: in a for loop it still runs the step before the next test, while in a while loop it jumps straight to the test.

What the CPU does. There is no special repeat instruction. The compiler places the body in memory, and ends it with a conditional jump that goes back to an earlier address. Many compilers also move the test to the bottom of the loop, so that each iteration needs only one jump instead of two. The same instructions run again, and what changes from pass to pass is the data: i and sum hold new values, as the cells of the trace show.

Why it is correct

A loop is a conditional branch whose target lies earlier in the code. It ends when the condition becomes false, so something in the body or the step has to move the program toward that point. In the trace, i climbs from 1 to 4, and every pass brings the test closer to failing. The for header makes this easy to check: you can see in one line where the variable starts, how it changes and when the loop stops.

The number of iterations follows from the header. For for (int i = a; i < b; ++i) it is b - a, because the range is half-open: it includes a and excludes b. The loop in the trace uses <=, so its range is closed and includes 3, which gives 3 iterations. Choosing between < and <= is where many off-by-one errors begin, and the next lesson is about them.

What it costs

Overhead per iteration. The increment, comparison and jump back usually cost one or two cycles, and the branch is easy for the CPU to predict, because it is taken almost every time. The one misprediction when the loop finally exits is cheap compared with a long loop.

Total work. The running time is roughly the number of iterations times the cost of one body. Summing 1 to n takes n additions, so doubling n doubles the time: this is your first contact with how cost grows with input size. A million iterations of a simple body typically take about a millisecond. At -O2, compilers sometimes turn such a sum into a closed formula or process several numbers per instruction, so a simple loop may run faster than its source suggests.

Nesting multiplies. A loop inside a loop runs the inner body once per combination: 1,000 outer iterations of 1,000 inner iterations make a million body executions.

Pitfalls and variations

The loop that never ends. Forgetting the step, as in a while loop without ++i, repeats forever. In a terminal, Ctrl-C stops the program.

The stray semicolon. for (int i = 0; i < 3; ++i); ends the loop with an empty body, as in lesson 1, and the block below it runs once.

Continue in a while loop. If the update comes after the continue, it is skipped and the loop may never end, as the last check showed.

Unsigned counters. A loop such as for (unsigned i = 5; i >= 0; --i) never ends, since an unsigned number cannot go below 0, as lesson 4 explained.

Floating-point counters. for (double x = 0; x != 1.0; x += 0.1) never hits 1.0 exactly, because 0.1 has no exact binary form. Count with an integer and compute the double from it.

Break leaves only one loop. Inside nested loops, break exits the innermost one only.

Variations. The range-based for (int x : values) visits every element of a container, and you will use it once arrays and vectors arrive. A loop such as while (std::cin >> x) from lesson 5 uses the read itself as the condition. A loop written for (;;) or while (true) runs until a break, return or exit ends it, as the retry loop in lesson 5 did.

Where it is used

Loops are everywhere: processing input until it ends, the main loop of a game that draws frames while the program is running, servers that wait for the next connection, and every numerical and data-processing routine. Every algorithm you will study, from searching to sorting, is built from loops and decisions like the ones you now know.

The next lesson, "Off-by-One Errors and Loop Invariants", shows how to get the boundaries of a loop right the first time.