You Can Program In C++ (2006) [eng]
.pdf
58 |
CHAPTER 3 |
Looping
C++ has three major constructs to deal with repetition. It also has a way to roll your own; however, good programmers normally avoid that option.
Language Note: Some languages, particularly the functional languages, use recursion as their main tool for repetition. It is possible to use this mechanism in C++, but the resulting code will generally be inferior to that written using C++’s native looping mechanisms. C++ compilers are not tuned to produce good object code when recursion is used as a looping mechanism. The use of recursion for looping will also make your code harder for C++ programmers to understand, because you will be writing code in a way that is strange to them.
The do-while Loop
We have already been using this in a highly specialized form so that we can repeat some action until an internal condition results in breaking out. The general form of the do-while loop is:
do{ action-one action-two etc.
} while(Boolean-expression)
In pseudocode, the do-while loop has this effect:
A: action-one action-two
etc.
if Boolean-expression evaluates as true then go to A
This always executes the actions section at least once. Then the program checks to see whether it should go back and repeat the section. We keep repeating the actions until one of two things happens: either the Boolean expression in the while clause evaluates as false, or one of the internal actions forces a breakout. The first option is the usual one, though we have not used that form so far in this book. For example, the following code fragment displays the numbers from 0 to 9 together with their squares:
int i(0); do{
std::cout << i << " " << i*i << '\n'; } while(++i < 10);
T R Y T H I S
Write a short program that incorporates the above code snippet. Compile, link, and execute it to check that the output is as predicted. Now change the ++i to i++, and compile and execute the result. Did the different results surprise you? Do you understand the difference? Note that we sometimes need to be careful about whether we use preor post-increment.
LOOPING AND MAKING DECISIONS |
59 |
The while Loop
A straight while loop tests at the start and is probably commoner than do-while. The major difference is that do-while loops always run at least once, whereas while loops test immediately and the actions section is only executed if the test evaluates as true. The form of a while loop in C++ is:
while(Boolean-expression){ action-one
action-two etc.
}
In pseudocode, the while loop has this effect (compare this with the pseudocode for the do-while loop):
go to B
A:action-one action-two etc.
B:if Boolean-expression evaluates as true then go to A
I could have used straightforward while(true) loops everywhere that I have so far used dowhile(true) in this book. Indeed, it is probably better to use this form for loops that rely on internal breakouts because it warns a reader of the code to watch for an internal break statement or return statement. The reason that I chose otherwise is partly so that I could write this here. There is not a lot between the choices but giving the marginally better one second may help you to remember that C++ often gives you a choice.
We can write the snippet of code above as:
int i(0); while(i++ < 10){
std::cout << i << " " << i*i << '\n';
}
However, the results are not exactly the same.
WARNING!
Resist the temptation to write:
int i(0); while(i < 10) {
std::cout << i++ << " " << i*i << '\n';
}
There is a potential for something very nasty happening if you write code that both increments a variable and uses that variable a second time all within the same statement. Notice that I wrote ‘potential’. Such statements have what is called ‘undefined behavior’ (which I will address directly in Chapter 6). This means that the C++ Standard makes no requirements on such code. It can do what you expected; or it can do something different, even something disastrous. I once had a program that reprogrammed the BIOS of an expensive graphics card because of undefined behavior. What makes it hard to learn about undefined behavior is that the program is allowed to do what you expected; it just isn’t required to.
60 |
CHAPTER 3 |
I will point out other potential for undefined behavior as I go. However, you should note that this is not unique to C++: all programming languages have cases of undefined behavior; C++ is more up-front about it than some.
Experienced C++ programmers use a simple guideline: ‘‘Do not use increment and decrement operators in expressions with other variables.’’ This is just a guideline, so there are places where expert programmers will ignore it. However, you need a good reason for doing so. The absolute rule is: ‘‘Never use a second instance of a variable that is being incremented or decremented within the same full expression.’’ For now, you can think of a full expression as something such as the control expression in a decision or loop, or any expression that ends with a semicolon.
T R Y T H I S
Modify the previous program by replacing the do-while with a while. Check the results and decide how to modify the program so that you get the same results as before.
The for Loop
The third and most commonly used loop construct in C++ is the for loop. It is easy to use once you get the feel of it, but it can be a little strange at first. The form of the for loop is:
for(initialization-expression; Boolean-control-expression; termination-expression) action
In pseudocode, the for loop has this effect:
initialization-expression go to B
A: action termination-expression
B: if Boolean-control-expression evaluates as true then go to A
Let me take each of those parts separately.
Initialization
The initialization part is executed exactly once. It states what must be done before entry to the loop for the first time. It can be empty (i.e. do nothing); it can set a number of variables to initial values before the loop starts; it can also be used to define one or more variables of a single type. The commonest option in C++ is the last one, defining a single variable that will control the loop.
Control expression
The control expression is always executed immediately before each execution of the action statement to determine whether it should be executed again (or the first time, whether it should be executed even once). The loop ends immediately this expression evaluates as false. This part can also be empty, but if it is, the loop will have to use an internal breakout – just as we have been using for do-while(true) loops. In other words, leaving out a control expression is equivalent to writing true at that point.
Termination
The termination part is an optional action that will be executed at the end of every pass through the loop and immediately before the next test of the control expression. Note that this happens at the end of a pass so is not executed before the first pass.
61
Action
The action, or controlled statement, can be a simple statement but is more often a compound statement (a block of statements contained within braces). It provides the actions that will be executed during each pass through the loop. This statement can be a null one (empty), in which case the only actions taken will be those provided by the control and termination expressions. For example, the following is valid (though not generally advocated as good code):
for(int i(0); i < 10; std::cout << ++i << '\n');
Putting it together
Here is the equivalent to the earlier snippets but using a for loop instead of a while loop:
for(int i(0); i != 10; ++i) std::cout << i << " "
<< i*i << '\n';
Defining the control variable of a for loop in the initialization clause is the normal idiom in C++. The control expression for a counted case such as this one is usually expressed using the != (not-equals) operator. This may be strange if you have come from a language such as C that uses a different idiom (such as the less-than operator), but comparing for inequality works in C++ even when the control variable is a user-defined type that does not support a strict ordering (we will eventually make extensive use of types called iterators that exhibit this property). The C++ idiom works just as well when we are using an integer variable as we are here.
It is also normal to use pre-increment in C++ when we are dealing with freestanding increment expressions. For integer objects it makes no difference whether we use preor post-increment, but later on we will be using other types of iterator (objects that are
used to control repetition and identify members of collections), and for those pre-increment is often more efficient. Therefore, we adopt a style that works well in all cases. We call such automatic choices ‘idioms’. Knowing the idioms of a language makes it easier both to write your own code and to read other programmers’ code.
62 |
CHAPTER 3 |
Language Note: One of the problems with idioms is that newcomers often try to recycle the idioms of their previous language. Sometimes these work well; sometimes they seem to work but there are hidden traps; and sometimes they either work badly in C++ (e.g. using recursion for looping) or do not work at all (e.g. using the Python form of for loop, which is a very powerful one, but not one that C++ currently provides). Most C idioms will work in C++, but every one of them needs to be re-examined in the context of C++, because not all of them are the preferred option in C++.
break, continue, and goto
There are several ways of varying from the normal flow of code in a construct. I am leaving the details of return until Chapter 5, when I deal with functions. You will also have noted that throwing an exception exits from the normal flow. I am also leaving details of that for a later chapter.
I have already made extensive use of break without going into much detail as to what it does. break causes an immediate exit from any of the above loop constructs (for, while, and do-while) as well as forcing an exit from a switch statement (and an if statement, but you should generally avoid its use there). The statement immediately after the construct in question will be the next one executed after a break statement.
It is good practice to avoid using break for exiting loops, though we have seen one of the exceptions to this in its use for exiting an otherwise infinite loop. It is often possible to change the source code so that break is unnecessary. The resulting code is often simpler even if it was not so obvious in the first place. If you find yourself writing more complicated code in order to avoid an early exit from a loop, you are probably heading in the wrong direction. Often programmers are still using a mental model that involves early exit while trying to abide by a coding guideline that prohibits the use of break. Try to design your code so that an early exit from a loop is unnecessary. Then you will reduce your use of break for all the right reasons, and your code will likely become simpler and more elegant.
Sometimes we find that we need to abandon the current pass of a loop and go immediately to the next one. C++ provides a special mechanism for that: the keyword continue. Here is a small code snippet to demonstrate its use (however, this is only a demonstration of use and not an illustration of good coding practice):
std::cout << "The following digits are not divisible by 5:\n"; for(int i(1); i != 10; ++i) {
if(i == 5) continue; std::cout << i << '\n';
}
In this case it would have been easy to eliminate the continue by replacing the above code with:
std::cout << "The following |
digits are not divisible by 5:\n"; |
for(int i(1); i != 10; ++i) |
{ |
if(i != 5) std::cout << i |
<< '\n'; |
} |
|
However, I might argue that the first form is clearer because it makes the exceptional case explicit whereas the second one buries it. In this simple case, I do not think there is much in it, but the decision whether or not to use continue should be based on which alternative makes the resulting code clearer.
I am going to say much about goto. I have never found it useful in over a decade of programming in C++. I have no great philosophical objection to goto; I just find that any code that uses it can be rewritten in a simpler form without it. Its continued presence in C++ is one of those holdovers from the past when long
LOOPING AND MAKING DECISIONS |
63 |
functions were common. These days we tend to write many shorter functions and rely on good compilers to reduce the number of actual function calls. goto is not generally useful in modern C++ programming. You need to know it exists because you might come across it in someone else’s code, but you do not need to use it.
Language Note: One of the problems for programmers used to languages such as BASIC is that they are accustomed to using goto. Some of the idioms they are used to use goto and they just import those into C++. The biggest problem with the use of goto is that it usually results in code that lacks clarity. Such code is hard to maintain and is prone to bugs.
In theory you can roll your own loops by using goto and if (witness the use of these in the pseudocode above). In practice, no C++ programmer would do that.
W A L K T H R O U G H
The Number-Sorting Program
Here are the important lines of that program again, to save you having to turn back and forth between the source code (page 52) and my commentary. I have highlighted the lines that I am going to write about.
7 int main( ) {
8try{
9std::vector<int> numbers;
10do {
11std::cout << "Next whole number (-999 to stop): ";
12int next;
13std::cin >> next;
14if(next == -999) break;
15numbers.push_back(next);
16} while(true);
17if(numbers.size( ) == 0){
18std::cout << "There were no numbers input.\n";
19return 0; // exit program
20}
21std::sort(numbers.begin( ), numbers.end( ));
22std::cout << "Here are the " << numbers.size( )
23<< " numbers you typed in ascending numerical order:\n";
24for(int i(0); i != numbers.size( ); ++i){
25std::cout << numbers[i] << ", ";
26}
27std::cout << '\n';
28}
29catch(...){
30std::cerr << "***An exception was thrown.***\n";
31}
32}
64 |
CHAPTER 3 |
Line 9 defines numbers as the name of an object that encapsulates a contiguous sequence of ints. The use of std::vector specifies that it will be a contiguous sequence. The <int> specifies that it is a sequence of ints. Because I have provided no extra information in the definition, numbers will start out as an empty sequence. C++ std::vector sequences have a growth strategy that allows them to expand as needed in a way that provides optimum general performance. They are the C++ programmer’s first-choice container for sequences of objects of the same type.
Line 12 defines the variable next directly before its point of first use. Strictly speaking, as we have defined next within a block of source code, the code recreates it every time the block repeats. However, any respectable compiler will avoid adding extra code. I have not initialized next because I am going to obtain a value from the std::cin in the next line. This is one of the special cases where we may reasonably leave out the initialization of a variable of a fundamental type. Nonetheless, many programmers insist on initialization even in this instance, because they worry about someone later on separating the point of definition from the point where the variable is first written to, thereby leaving the gate open for someone else to add code that uses the variable before it has been written to.
If you thought carefully about line 13 in the context of the comment I made about assumptions, you will have noted that the code assumes that the user always types in a valid integer. Even such trivial errors as trying to input a number with a decimal point will send the program into an infinite loop. We are not yet ready to deal with that issue other than by sending a message to std::cerr and then giving up by throwing an exception.
T R Y T H I S
If you have not already done so, go back and amend the program so that it tests std::cin immediately after its use and throws an exception if it has failed.
W A L K T H R O U G H
Continued
Line 14 tests for end of input. If the user has entered the specified value, the program skips forward to start executing from line 17. Otherwise, it executes line 15. This line uses the mechanism provided by std::vector for adding a new object to the end of the sequence it is holding. If there is not enough space for the new object, push back( ) will trigger the internal behavior that provides a larger amount of space and, if necessary, copies the existing values into that space so that the objects in the sequence remain contiguous. In other words, std::vector automatically maintains its contents as a contiguous sequence.
Lines 17 –20 deal with the possibility that no numbers were provided. They make use of the mechanism provided by std::vector that reports the current number of objects in the sequence. numbers.size( ) always evaluates to the number of objects in the sequence that we are calling numbers. Line 19, return 0 is the mechanism for leaving main (i.e. the program) early. We could have avoided the need for an early exit by putting the remainder of the normal processing in a block controlled by else.
LOOPING AND MAKING DECISIONS |
65 |
T R Y T H I S
Modify the program to eliminate the return 0 and make the rest of normal processing a block controlled by else. When you have done this, consider the two versions and decide which seems clearer to you. I prefer the early return, but some coding guidelines prohibit use of early returns. Try to come up with an alternative design that avoids making the normal processing the else part of an if-else.
W A L K T H R O U G H
Continued
Line 21 uses one of the more powerful features of modern C++, the concept of applying ‘algorithms’ to sequences. The #include <algorithm> line provides access to the somewhat misnamed ‘algorithm’ part of the Library. std::sort is one of roughly 80 algorithms provided by the Library. The default version of it requires two arguments. The first argument specifies where the sequence starts, and the second one specifies how to determine that the sequence has finished. By default std::sort( ) sorts a sequence into the natural ascending order for the type of objects in the sequence – it uses the < (less-than) operator for the type of objects stored in the sequence.
numbers.begin( ) uses the mechanism of std::vector that supplies the value (called an iterator) that identifies the start of the sequence. numbers.end( ) supplies the iterator that signifies that the sequence has ended (we will discuss the details of iterators another time, but for now just know that they generally identify the location of objects). Note that end( ) does not identify the last object: it is a special iterator that determines whether the sequence has ended (in other words, unlike most iterators, this one does not identify the location of an object). This representation of the end of a sequence may seem strange at first, but it has many advantages, and as you get used to it you will find it strange that you ever expected the end of a sequence to be the last element rather than after the last one.
Now if you look at line 21 again you will see that it results in the rearranging of the sequence called numbers into ascending order.
Lines 24 –26 output the sorted sequence in numbers as a comma-separated list. The control expression of the for loop keeps going until it has counted all the elements of numbers. Notice that along with many other languages, C++ starts counting at zero, with the consequence that you have finished when the count reaches the number of the elements in the container (given by numbers.size( )).
Line 25 uses the feature of std::vector that allows access to elements by using a subscript or index. That means that we can treat std::vector objects as if they are arrays, but arrays with a lot of added functionality. How surprising you find this depends on your prior programming experience.
On Magic Numbers
Programmers often refer to numerical literals as ‘magic numbers’. Sometimes the significance of a literal number is obvious from the context in which it is used, as is the case for the factor used for converting hours
66 |
CHAPTER 3 |
to minutes in the following code snippet:
int hours; std::cin >> hours;
int minutes(hours * 60);
I see nothing wrong with using the literal 60 in this context. But there are cases where even though the context makes the use clear we might still prefer to use a named value. For example:
double radius; std::cin >> radius;
double circumference(2 * radius * 3.14159625);
You probably recognize the literal as an approximation for the mathematical constant π , but are you sure I typed the figures correctly? (I did not.) In addition, if π turns up in a program it will probably do so more than once.
Readability and correctness are just two reasons for replacing the literal with a name. In C++, we do that by defining a const-qualified name for the literal. The above code now becomes:
double const pi(3.14159265); // corrected double radius;
std::cin >> radius;
double circumference(2 * pi * radius);
That final statement becomes instantly recognizable by anyone with even the smallest amount of domain knowledge. The use of a named constant means that we only have to type the value in once – carefully – and after that, we write readable code. Should I mistype the value of π or want to provide more significant figures I have a single point at which to make the change.
Where magic numbers become a matter for more concern is where the values are essentially arbitrary. In the number-sorting program, the choice of −999 to flag end of input is entirely arbitrary. It signifies termination of input because I decided that that is what it would mean. A stranger looking at the code can legitimately ask what is special about −999. The answer is that it is a magic number whose property is neither more nor less than what I choose it to be. We should always replace such numeric literals with named values. In C++, we do that by providing an appropriate name for a const-qualified object of a suitable type. In the number-sorting program, I might provide:
int const end_input(-999);
Now I replace line 11 with
std::cout << "Next whole number (" << end_input << " to stop): ";
and line 14 with:
if(next == end_input) break;
I hope you think the result is clearer and easier to maintain. You can easily change the termination value to something else by changing the definition of end input. In addition, the source code should need less commentary because the named values communicate my intention.
From now onwards, look at literals with a degree of suspicion, and ask yourself if their use is sensible in context, or do they have smell of ‘magic’? You will get back the cost of a little extra typing many times over in reduced maintenance time.
The names fgw::red1 etc. for the bits in the color-coding in the default palette of colors used by fgw::playpen objects are an example of removing magic numbers. In this case the names stop being useful (actually, they become positively misleading) when we move away from the default palette. Named values do not solve all our problems. We have to choose names carefully.
LOOPING AND MAKING DECISIONS |
67 |
EXERCISES
1.Write a program that asks the user how many words they are going to input, and then collects those words into a std::vector<std::string>. When the input has completed, sort the words alphabetically and print them out in a column.
2.Write a program that collects words from the keyboard until ‘END’ is typed in. It should then sort the words and output them in a column. Try to avoid the magic use of ‘END’ by using a suitably named constant object.
3.Write a program that displays a column of 20 black pixels in the Playpen window. Check carefully that it is a column of 20, not 19 or 21. I suggest that you do not use the default Playpen scale but set the scale to something larger. You might like to think about a way that will allow you to count the pixels as they are plotted.
4.Write a program that prompts the user for two whole numbers and then displays a cross in the Playpen window whose height is the first number and whose width is the second. Modify this program so that the user can select a color other than black. For example, you might ask the user for the amount of red (0 to 7), the amount of green (0 to 7) and the amount of blue (0 to 7). You know enough C++ and enough about the default Playpen palette to achieve this, but it will be hard if you are not already a fluent programmer in some other language.
5.Write a program that covers the Playpen with 256 colored tiles, one of each of the 256 colors in the default palette. If you use a scale of 32, 16 rows of 16 logical pixels will exactly cover the Playpen. The only hint I will give you is to consider using nested for loops. You may have to experiment quite a bit. (Don’t forget that you can change the origin if that helps you.)
6.Write a program that draws the diagonals of the Playpen.
7.The median of a collection of values is the one in the middle when they are arranged in numerical order. If there are two middle ones (because there are an even number of values in the collection) the median is the arithmetic mean of the middle pair. Write a program that collects numbers from input and then outputs their median.
8.An examination is graded on the basis that the top 20% of the candidates get ‘A’, the next 20% get ‘B’, and so on to the bottom 20%, who get ‘E’. Write a program that collects the marks for 20 candidates and then outputs the grade boundaries. Note that you do not need to know the maximum possible mark. For a perfect solution you will need to resolve issues concerning multiple candidates on a grade boundary.
S T R E T C H I N G E X E R C I S E S
These exercises give experienced programmers a greater challenge. If you found the above exercises tough, leave these ones for now. You can always come back to them later. As always, answers should be limited to using only C++ that I have introduced so far.
9.The triangular numbers are those resulting from the sum of the first n whole numbers. So the first four are: 1; 3 (= 1 + 2); 6 (= 1 + 2 + 3) and 10 (= 1 + 2 + 3 + 4). Write a program that displays triangular numbers of pixels as triangles in the Playpen. It should start by displaying a single pixel in a color of your choice and