Looping statements

Review of last time

Conditional control structures let us switch between two (or more!) paths of statements, based on some boolean conditions. If the condition evaluates to true, then the program “flows” through one set of statements, otherwise, it flows through another. The basic conditional statement we looked at was if-else:

if(condition)
    true-body;

if(condition)
    true-body;
else
    false-body;

if(input.empty())
    cout << "You must type something!" << endl;
else {
    cout << "Input received, processing..." << endl;
    ...
}

As we saw, we can nest if-else statements inside each other, for example, to test whether two things are true:

if(a != 0.0) {
    if(1.0 / a > 15.0) {
        cout << "Value in range!" << endl;
    }
}

and we saw how this is equivalent to 

if(a != 0.0 && 1.0 / a > 15.0)
    cout << "Value in range!" << endl;

We also saw how we can rewrite

if(!data.empty())
    cout << "Processing data..." << endl;
else
    cout << "No data to process." << endl;

into

if(data.empty())
    cout << "No data to process." << endl;
else
    cout << "Processing data..." << endl;

And finally, note that something like

if(y < 10)
    x = y * 10;
else
    x = y / 10;

is the same as 

x = y < 10 ? y * 10 : y / 10;

(Which is “better”? That’s up to you, but the former is probably better if the assignments are complicated.)

Introduction to loops

Today is where stuff starts getting cool, and the kinds of programs we can write become more interesting. This is also the first time that we’re going to give a different kind of “flow” to the statements in our program. Up until now, all our programs have just executed their statements straight through, top to bottom. Today we’re going to add the ability to repeat portions of our program.

Let’s write a useful-ish program, one that lets the user press a key, and if that key generates any input at all, will print out the character codes for it. Keys like ‘a’, ‘!’, ‘4’ generate a single character of input. Keys like Enter and Backspace also generate a single character, although it’s “nonprintable” (all the nonprintable characters have codes less than 32). But some keys (like Ctrl and Alt) don’t generate any characters when pressed, only when used in combination with others, and finally, keys like Insert and the arrow keys, actually generate multiple characters of input. It’s these last keys that we’re really interested in. In order to do this, we need to repeatedly wait for the user’s input, not just once. And we also don’t know how many character codes we’ll get at once: it might be one (if the user entered ‘A’), or more, for special keys like F5 or home.

We can get a single character from the input with cin.get(c). What we want to do is repeated do this, until the user presses Ctrl-D (which signals “end of input”), printing codes for every character we read. The trick is that cin.get(c) actually gives back a bool-like result, indicating whether or not there is any more input (i.e., it will evaluate to false if the user presses Ctrl-D). What we want is to repeat this process: reading using get, and then writing the code, for as long as cin.get(c) continues to give us true results. We can do this with a loop. In particular, if we want to keep doing something as long as some condition is true, what we will use is a while loop:

#include <iostream>
#include<cstdlib>
using namespace std;

int main() {
    cout << "Press a key!" << endl;

    char c;
    while(cin.get(c)) 
        cout << (int)(c) << " ";

    return 0;
}

This program doesn’t work quite the way we expect, because get will actually wait for you to type an entire line, and press Enter, before returning with its results. So you have to press Enter after every key. This is also why every sequence of codes ends with “10”; 10 is the code for Enter. But we can try some fancy keys like Escape, Delete, or Home. (Backspace generates a code, but we don’t get it, because while you are typing your input line, you can backspace through it.)

This also illustrates another use of input-reading commands like cin.get or even cin >> c: you can use them as bool-valued expressions. They will evaluate to true if the input was successful, or false if something went wrong, typically, when there is nothing more to read. To terminate a loop like this, you can either press Ctrl-C which kills your program no matter what it’s doing, or you can press Ctrl-D which signals that no more input is forthcoming, and thus ends the loop allowing your program to quit normally.

(The version of this that I’m going to post later has some extra code that puts the input into ‘raw’ mode, so that we get every key the user presses. But this also means that Ctrl-C and Ctrl-D can’t be used to kill the program!)

So today we’re going to look a lot more at loops: how to use them, what they’re good for, what we can do with them.

Loop control structures

There are three (or four, depending on how you count) kinds of loops in C++. All of them have the same general purpose, of allowing you to repeat a statement (or block of statements) over and over, until some condition is met.

Note that the loop structure are not statements themselves, they are control structures; they modify how other statements work. Thus, in the above program, there are three statements and one control structure. Having said that, a control structure can be used (like a block) anywhere where a normal statement is expected.

Anatomy of a loop structure

All of the loop structures have two things in common:

When you look at a loop, the two most important things are what is being repeated and what will make this stop.

Loop types

The four types of loop are

We’ll look at the first two of these today.

While loop

The while loop is what we saw above. It looks like this:

while(condition)
    body

The body can be a single statement (ending with a ;), or it can be a block (because a block can replace a single statement anywhere). The body will be repeated over and over, until the condition evaluates to false. If the condition is false from the start, then the body won’t be run at all.

A while loop actually expands into something like this:

if(condition) {
    body
    if(condition) {
        body
        if(condition) {
            body
            ...
        }
    }
}

That is, the condition is checked only before each complete run of the body. In particular, if the condition happens to become false in the middle of the body, the body won’t stop there; it will run until the end and only then check the condition. E.g.,

i = 0;
while(i < 10) {
    cout << "One ";
    i = 12;
    cout << "Two ";
}

This will print One Two, because the condition is true the first time through; the second time we check it, it is false, and thus the body is only run once.

(This is true of all the loops, in one way or another; there is a specific point at which the condition is checked, generally at the beginning or end of the body. It’s value elsewhere does not matter.)

The simplest while loop is probably something like this:

while(false)
    cout << "Hello!" << endl;

What will this do when we run it? (Demonstrate.)

The second simplest while loop is

while(true)
    cout << "Hello!" << endl;

What will this do?

Let’s look at some examples (practice stepping through each of these, and demonstrate each on the server).

While looking at a loop and figuring out what it does is a good skill to have, another useful exercise is to think of some repetitive task and then write the loop for it. For example:

Note that we can always combine different loops, provided we think about what we want to end the loop. E.g., suppose we have these two while loops:

int i = 1;
while(i <= 10) {
    cout << i;
    i = i + 1;
}

int j = 20;
while(j >= 0) {
    cout << j;
    j = j - 1;
}

Here we have a loop that counts up from 1 to 10, and another that counts down from 20 to 0. We can combine these into a single loop that counts in both directions: we just have to decide when the loop should end: should it end when i == 10? If so, that will happen before j reaches 0, so the count-down part of the loop won’t finish. On the other hand, if we let j count all the way down, then i will end up negative.

int i = 1, j = 20;
while(i <= 10) {
    cout << i;
    i = i + 1;
    cout << j;
    j = j + 1;
}

Another option is to split this into two loops: one that runs over the common part where both i and j are counting together, and then second which finishes up j:

int i = 1, j = 20
while(i <= 10) {
    cout << i;
    i = i + 1;
    cout << j;
    j = j - 1;
}
// Still some j left to do
while(j >= 0) {
    cout << j;
    j = j - 1;
}

Note that a common mistake when writing while loops is to forget that the while part is not a statement, and write:

while(whatever);
    cout << "Things";

This loop won’t do anything. The “body” of the loop is actually the empty statement created by the semicolon after the while. In fact, the loop we have written is actually

while(whatever) { 

}
cout << "Things";

Remember: the while part doesn’t have a semicolon after it, because it’s not a statement by itself.

While loops are good when there’s some natural true/false condition that would cause us to stop. Let’s look at some example while loops:


// This will take all the words the user types (separated by spaces) and
// count them.
string input;
int word_count = 0;
while(cin >> input)
    word_count++;

(If we used getline, it would count the number of lines.)

Drawing a line

Let’s say we want to draw a “line” out of text, like so:

---------------------

where we ask the user for how many dashes to print.

First we need to prompt the user for the number:

int dashes;
cout << "How many dashes to print? ";
cin >> dashes;

Now what? We showed above a while loop that would count from 1 to 4, but this can be used to count from 1 to anything, and we can do whatever we want inside the loop; it doesn’t have to just print out the number.

int i = 1;
while(i <= dashes) {
    cout << "-";
    ++i;
}
cout << endl;

An easier way to do this: just use the repeated-character string trick:

cout << string(dashes, '-') << endl;

Using a while-loop with find. We can combine a loop with find to find all the occurences of a string:

string s = ...;
string p = ...; // Pattern to find
int l = s.find(p); // First occurrence
while(l < s.length()) {
    // l is a occurence location
    l = s.find(p, l+1); // Find next
}

The Do-While loop

A do-while loop is similar to a while loop, in that it runs the body until the condition becomes false. However, unlike a while loop, a do-while loop always runs its body at least once. The way it’s written emphasizes this:

do 
    body
while(condition);

As the layout suggests, the condition is tested at the end of each run through the body (while the while loop tests it at the beginning). So if condition is false from the start, we still have to pass through the body in order to get to the point where it is tested.

The do-while loop is one of the two exceptions, things that shouldn’t have semicolons after them, but do. If you need a memory device, you can remember it this way

A do-while loop always does something (i.e., always runs the loop body at least one). So it always does something, and thus ends with a semicolon like a statement.

Generally, we use a do-while loop when we want to make sure that something happens at least once. A common scenario is where we need to set some things up, and then we do something that might cause the loop to stop. For example, 

int age;
do {
    cout << "Enter your age: ";
    cin >> age;
    cout << (age < 21 ? "No one under 21 allowed" : "OK") << endl;
} while(age < 21);

To rewrite this as a while loop, we would have to do

cout << "Enter your age: ";
int age;
cin >> age;
while(age < 21) {
    cout << "No one under 21 allowed" << endl;
    cout << "Enter your age: ";
    cin >> age;
}
cout << "OK" << endl;

We had to read in the age twice in our code, once outside the loop to “prime the pump” and then again inside the loop, if the user’s input is incorrect. Using a do-while loop simplifies this. On the other hand, do-while isn’t terrifically useful for reading input from the user, because the thing we do to read input needs to happen at the beginning of the loop, but in a do-while the condition is at the end.

A good clue that you want a do-while loop is if you find yourself initializing some variable to a special value, just so it will pass the condition of a while loop:

int x = 1;
while(x != 0) {
    cout << "Enter a non-negative number: ";
    cin >> x; 
    // etc.
}

Here’, we only set x to one to avoid triggering the condition; what we really want to do is read in x from the user before we do anything:

int x;
do {
    cout << "Enter a non-negative number: ";
    cin >> x;
    // etc.
} while(x != 0);

Let’s look at some do-while loops:


// Prints out 0,1,2,...,8,9
int i = 0;
do {
    cout << i << endl;
    ++i;
} while(i < 10);

// Prints out 10,9,8,...,3,2,1
int i = 10;
do {
    cout << i << endl;
} while(--i > 0);

// Prints out 9,8,...,3,2,1,0
int i = 10;
do {
    cout << --i << endl;
} while(i > 0);

// This is a better version of the "keep running" while loop above
char running;
do {
    ...
    cout << "Continue (y/n)? ";
    cin >> running
} while(running = 'Y' || running = 'y');

// Will continually prompt the user for numbers until they enter 0.
// The condition could be simplified to just `number` since any != 0 is true
int sum = 0, number = 0;
do {
    cout << "Enter a number: "
    cin >> number;
    sum += number;
} while(number != 0);

More complex loop examples

Above we saw how to draw a line. Suppose we want to draw a “triangle”, something like this:

     *
    * *
   *   *
  *     *
 *       *
***********

where the height (number of rows) in the triangle is user input (and thus we can’t just print the same triangle every time!). That is, we want to solve this problem:

Write a program which prompts the user for a number of rows and then prints a triangle of that size.

When faced with a problem like this, it’s sometimes helpful to ask what is the smallest possible input: what is the smallest triangle we could reasonably draw? Although it doesn’t look like a triangle, a one-row drawing might look like this:

*

Next up we have 2

 *
***

and 3

  *
 * *
*****

and so forth.

The first part of the problem is to read the size of the triangle from the user. Fortunately, this is something we know how to do:

int rows;
cout << "Enter number of rows: ";
cin >> rows;

(Maybe we should make sure that the user enters a number that is at least 1, since that’s the smallest triangle we can draw?)

Drawing a triangle means drawing all the rows, and we don’t know, when we’re writing the program, how many rows there will be. Whenever you have a problem that requires you to do something over and over, but you don’t know how many times, you should try a loop.

Something like this:

int row = 1;
while(row < rows) {
    // ...draw this row
    row++;
}

Sometimes its good to leave parts of your program unwritten like this, so that you can test out the other parts. If we want to, we can even add some printing to help us test it:

int row = 1;
while(row <= rows) {
    // ...draw this row
    cout << "Drawing row " << row << endl;

    row++;
}

Now we need to focus on the problem of drawing the n-th row, out of a total rows. One thing to notice is that rows only determines where we stop: the first row is always 1 *, the second is always two, etc. The size and shape of each row depends only on how far down it is, not on how close it is to the bottom — except for the last row. The last row is special (it’s nothing but *‘s), so maybe we should ignore it for now.

Every other row looks something like this:

         *                   *        
----x---- ----y----_----y---- ----x----

That is, we print x spaces (for some x), then a *, then \(2y + 1\) spaces, then another star, then a final x spaces.

How do I print a certain number of spaces? Use another loop:

int s = 0; 
while(s < x) {
    cout << " ";
    s = s + 1;
}

Printing an entire row looks like this:

int s = 0; 
while(s < x) {
    cout << " ";
    s = s + 1;
}
cout << "*";
s = 0; 
while(s < 2 * y + 1) {
    cout << " ";
    s = s + 1;
}
cout << "*";
s = 0; 
while(s < x) {
    cout << " ";
    s = s + 1;
}
cout << endl;

That seems kind of messy. Is there a cleaner way we can do this? Well, first of all, there’s not really any point of printing the spaces at the end of the line, becuase they are invisible! We can print the newline after the second *.

Maybe, instead of printing everything, can we construct a string that contains what we want, and then print it at the end? Why don’t we construct the string consisting of x spaces once, and then reuse it:

string spaces_x, spaces_y; // Starts out empty
int s = 0;
while(s < x)
    spaces_x.push_back(" "); // Add another space
s = 0;
while(s < y)
    spaces_y.push_back(" ");

// Now use spaces:
cout << spaces_x << "*" << spaces_y << " " << spaces_x << "*" << endl;

But if we think back to strings, we can build a string that contains some number of copies of a single character:

string(x, ' ')

will give us the string consisting of x spaces. So now we have just

cout << string(x,' ') << "*" << string(2 * y + 1,' ') << "*" << endl;

One thing to notice: as we go down in rows, x gets smaller while y needs to get bigger.

Printing all the rows

Putting this back into our code:

int row = 1;
while(row < rows) {
    // Compute row size
    int x = ...;
    int y = ...;

    cout << string(x,' ') << "*" << string(2 * x + 1,' ') << "*" << endl;

    row++;
}

Two changes: I’ve removed the debugging code, and I’ve changed the loop condition to skip the last row.

Let’s print the last row: it’s nothing but *s, but how wide is it, relative to the total number of rows? How does the width change as we go from one row to the next? It increases by 2 each time, but it starts at 1. So the total width should be rows * 2 - 1. (Note that if rows == 1 this will correctly give the width of the first/last row as 1.)

int row = 1;
while(row < rows) {
    // Compute row size
    int x = ...;
    int y = ...;

    cout << string(x,' ') << "*" << string(2 * x + 1,' ') << "*" << endl;

    row++;
}
cout << string(rows * 2 - 1, '*') << endl; // Last row

Now we just need to figure out how to calculate x and y. There are a couple ways we can do this:

We saw that the last row has a width of rows * 2 - 1. This means that in the first row, x should be rows - 1. From there it’s a short hop and skip to 

int row = 1;
int x = rows - 1;
int y = 0;
while(row < rows) {
    cout << string(x,' ') << "*" << string(2 * x + 1,' ') << "*" << endl;

    row++;
    x--;
    y++;
}
cout << string(rows * 2 - 1, '*') << endl; // Last row

Let’s try this out and see what happens.

Printing a multiplication table.

Let’s try to print out a 10x10 multiplication table, something like this:

   0  1  2  3  4  5  6  7  8  9  10
0  
1
2
3
4
5
6
7
8
9
10

The main problem here is getting the numbers to line up, but fortunately there’s a trick we can use with cout: setting the field width to the number of characters in the largest number in the table (100) will make all the numbers we print take up that much space. You can set the field width using:

cout.width(3);

And then we just have

cout.width(2);
for(int x = 0; x <= 10; ++x) {
    for(int y = 0; y <= 10; ++y)
        cout << x*y;
    cout << endl;

That doesn’t print the row/column headers. We can add them if we wish.