All of Programming [ PART I ]

Video 12.5: Stepping through a call to realloc. Note that even though we wrote p = realloc(p, 14 * sizeof(*p)); in the video (which is a simple example of the mechanics), doing so in real code can result in a memory leak if realloc fails. If realloc fails, it returns NULL but does not free the memory that was passed in to it (so that the program has not lost that data— in case it can recover from the situation and continue on). Beyond malloc, free, and realloc, there are a few more standard functions available for memory allocation, such as calloc (which zeroes out the region in memory for you—by contrast, malloc does nothing to initialize the memory). The man pages for all of these functions are, as always, great reference. 12.4 getline You have already seen fgets, which lets you read a string into a buffer you have preallocated, specifying the maximum size for the string to read (i.e., how much space is in the buffer). However, how could you write code that would read a string of any length? Before this chapter, we have not had the tools to think about such a function—it clearly requires dynamic allocation, as we would need that function to allocate memory that lasts after the function returns. Now, we can learn about getline. Figure 12.8: The signature of getline.

The function getline is available in the C Standard IO Library (#include <stdio.h>). Its signature (shown in Figure 12.8) looks a bit intimidating, but it is worth understanding. getline reads a single line from the file specified in its third argument, stream. It does this by reading characters from the file repeatedly until it sees the character ’\\n’, which indicates the end of a line. As it reads each character, it copies the characters into a buffer in memory. After reading the newline character, getline places a ’\\0’ character, which indicates the end of the string. So far, this behavior sounds much like fgets; however, the difference is in the fact that getline allocates space for the string as needed. The difference arises from the fact that getline uses malloc and realloc to allocate/enlarge the buffer. The linep parameter points at a pointer. If *linep is NULL, getline mallocs a new buffer. If *linep is not NULL, getline uses that buffer (which is *linecapp bytes long) to start with. If the initial buffer is not long enough, getline reallocs the buffer as needed. Whenever getline mallocs or reallocs the buffer, it updates *linecapp to reflect the number of bytes allocated. It also updates *linep to point at the new buffer. When the getline function returns, *linep is a pointer to the string read from the file. The getline function returns on an error (including end of file), and the number of bytes read (not counting the null terminator byte) on success. Note that the return type is ssize_t, which stands for “signed size_t”—that is, the signed integer type, which is the same number of bytes as size_t (so it can return ). Video 12.6: Using getline to read lines from a file and print them out. The getline function can be used in two ways. First, the user can provide getline with a pointer to a malloced buffer (*linep) whose size is pointed to by linecapp. If the

line being read is larger than *linecapp, getline will perform a realloc for the user and modify the values of *linep (to point to the newly realloced region) and *linecapp (to be the size of the newly reallocated buffer) accordingly. Second, the user can provide getline no buffer, indicated by linep containing a pointer to NULL (linep cannot be NULL, but if *linep is NULL). In this case, getline will perform a malloc for the user and modify the values of *linep (to point to the newly malloced region) and *linecapp (to be the size of the newly allocated buffer) accordingly. These two ways can be used together—i.e., one can write a loop where no buffer is provided the first time, and the same buffer is reused on subsequent iterations. Video 12.6 shows an example of using getline to read lines from a file and print them out. Video 12.7: An example that combines getline and realloc. We conclude this chapter with Video 12.7, which shows a slightly larger example that combines getline and realloc to read all the lines from a file into an array. The example then sorts them (using qsort, which you saw in Section 10.3), prints out the results, and frees the memory appropriately.

12.5 Practice Exercises Selected questions have links to answers in the back of the book. • Question 12.1 : What does the malloc function do? • Question 12.2 : What does the sizeof operator do? Why is it important? • Question 12.3 : What is a memory leak? • Question 12.4 : What does the free function do? What is OK to do with a block of memory after you free it? • Question 12.5 : Suppose you call realloc, and your program segfaults inside the C library code for realloc. What kind of problem would you suspect in your code? How would you go about fixing it? • Question 12.6 : Read the man page for strdup. What does this function do? What does it mean that its argument is a const char *? How do you need to deallocate the memory it allocates for you? • Question 12.7 : Write char * myStrdup(const char * str). This function should behave exactly like strdup (whose man page you read in the previous question). You should not make use of the strdup function in writing this function. • Question 12.8 : Consider the following code (which has memory leaks): 1 #include <stdio.h> 2 #include <stdlib.h> 3 4 int f(int n) { 5 int * p = malloc(2 * sizeof(*p)); 6 p[0] = n; 7 p[1] = n+2; 8 int ans = p[0] * p[1]; 9 return ans; 10 } 11 int main(void) {

12 int * p = malloc(4 * sizeof(*p)); 13 int * q = p; 14 int ** r = &q; 15 p[0] = f(1); 16 *r = NULL; 17 q = malloc(2 * sizeof(*q)); 18 p = q; 19 q = NULL; 20 return EXIT_SUCCESS; 21 } Execute this code by hand, and identify the lines on which memory is leaked (that is, the line on which the last reference to a block is lost). Next, modify the code by inserting appropriate calls to free (do not make any other changes to the code) so that the code no longer leaks memory. Use Valgrind to make sure you have properly eliminated all memory leaks without introducing any other bugs. • Question 12.9 : Video 12.7 walked through a program that read lines from stdin, sorted them, and printed the results. Write a similar program (or modify the code in the video) so that the program takes one or more command line arguments (each of which specifies a file name), reads all of the lines in all of the specified files, sorts the data, and prints the results. Note that this program should read all lines from all files, then sort all of them together (so lines from different files may be interleaved in the output), then print the results. Test your program, and be sure that it Valgrinds cleanly and does not leak memory. • Question 12.10 : Consider the following code, which has errors in it: 1 #include <stdio.h> 2 #include <stdlib.h> 3 4 struct my_struct_tag { 5 int nNums; 6 int * nums; 7 };

8 typedef struct my_struct_tag my_struc 9 10 void f(my_struct * ptr) { 11 for (int i = 0; i <= ptr->nNums; i+ 12 printf(\"%d\\n\", ptr->nums[i]); 13 } 14 free(ptr); 15 } 16 int main(void) { 17 my_struct * s = malloc(sizeof(s)); 18 s->nNums = 5; 19 s->nums = malloc(5 * sizeof(*s->num 20 for (int i = 0; i < s->nNums; i++) 21 s->nums[i] = i + 4; 22 } 23 f(s); 24 free(s); 25 return EXIT_SUCCESS; 26 } Identify and fix four major errors in the code. Check your work with Valgrind. After you have made the code work with no Valgrind errors, is there a way it can be further improved by using a more correct type in some place? • Question 12.11 : For this problem, you will write a program that reads two matrices from files (whose names are specified as command line arguments), multiplies the two matricies (if you don’t know or don’t remember how to multiply matricies, find that domain knowledge on the internet). If the two matricies cannot be multiplied, your program should print an error and exit. Otherwise, it should print the result then free any memory it allocated. When your program reads the input matricies, it should read a file where the first line contains an unsigned integer (specifying the width), the next line contains an unsigned integer (specifying the height), then each other line contains a double (which is a value in the matrix). The matrix values will be ordered such that you read across the zeroth row (starting from column

0, and ending at the max column), then across the first row, and so on. If there are any errors reading the file (e.g., not enough values, values that are not doubles, etc.), your program should print an error and exit. Hint: you should use malloc to allocate your matrices. Hint 2: we provide the struct for a matrix, as well as the functions (though you are encouraged to abstract things out into more functions as you see fit) you should write to accomplish this task: 1 struct matrix_tag { 2 double ** values; 3 size_t rows; 4 size_t columns; 5 }; 6 typedef struct matrix_tag matrix_t; 7 8 matrix_t * multiply(matrix_t * left, 9 //write this 10 } 11 matrix_t * readMatrix(const char * fi 12 //write this 13 } 14 void printMatrix(matrix_t * matrix) { 15 //write this 16 } 17 void freeMatrix(matrix_t * matrix) { 18 //write this 19 } 20 int main(int argc, char ** argv) { 21 //write this 22 } 11 Interacting with the User and System13 Programming in the Large Generated on Thu Jun 27 15:08:37 2019 by L T XML

I Introduction to Programming in C12 Dynamic AllocationII C++

Chapter 13 Programming in the Large So far, we have focused exclusively on programming in the small—designing the algorithm for a small-sized task (i.e., one or a few functions), implementing it, testing it, and debugging it. However, most “real” programs have significant differences from the tiny ones we have developed so far. One key difference is that they tend to be much larger than those we have written (e.g., the Linux kernel has about 16 million lines of code in about 30 thousand source files). Another difference is that they have more than one person working on them, sometimes teams of hundreds to thousands. A third key difference is that real software has a long life span during which it must be maintained. Now that you have an understanding of the basics of programming in the small, we are ready to begin learning about programming in the large—the aspects of designing and implementing programs that arise from having significantly-sized programs with long life spans. A key aspect of programming in the large is the higher-level design of the program. Instead of just writing one (or a few) functions to perform a function-sized task, the programmer must now design the code into multiple appropriately sized modules with clearly defined interfaces between them. Of course, programming in the small still comes into play, as the design will ultimately boil down to many function-sized tasks, which must be implemented. A good analogy to think about programming in the small and in the large is writing (as in, English text). “Writing in the small” would be the task of crafting a sentence or paragraph. Here, you are concerned with issues like grammar (syntax) and word choice. You have one particular point you want to make and must make it clearly. This is about the size of programming tasks you have accomplished so far. Continuing our analogy, “writing in the large” would come into play for larger documents —whether they are dozen-page papers or many-hundred page books—which may also be written by multiperson teams. Now, we must be concerned with splitting the task into logical pieces (chapters and sections) and forming an outline. We must concern ourselves with the “interface” (in the case of writing: logical flow of ideas) between pieces at all granularities— chapter-to-chapter, section-to-section, and paragraph-to-paragraph. At some point, our “writing in the large” will produce a design that dictates many “writing in the small” tasks—we then apply our skill in that area to “implement” each of these paragraphs. This analogy is particularly apt because the “in the large” and “in the small” skills are distinct but go hand-in-hand in both cases. In both cases, you need both skills to write a complete document/program. You also need to keep the “in the small” in mind as you do the “in the large”—thinking about what makes for an appropriately sized paragraph/function that you can implement. We are going to spend the rest of the chapter introducing programming in the large. Our coverage here will be sufficient for you to begin writing modest-sized programs, which we will start to work toward through the rest of this book. However, we will note that if you plan to work on very large software projects and/or want to become an expert in programming in the large, there is an entire subfield of computer science, called Software Engineering, dedicated to this topic. In such a case, you should take classes in that area once you have mastered the basics of programming. 13.1 Abstraction

One of the key techniques for designing any large system is abstraction. As we previously discussed, abstraction is the separation of interface from implementation. The interface of something is what it does, while the implementation is how it does it. Recall our example of abstraction from Section 3.1.2: driving a car versus knowing how it works under the hood. The car provides a simple interface (turning the steering wheel turns the car, pushing the accelerator makes the car go faster, pushing the brake slows it down, etc.); however the implementation (how everything works under the hood) is quite complex. Of course, you do not actually have to know how the car works to drive it—the implementation is hidden from you. You only need to know the interface. A similar principle applies in designing programs—you should be able to use a function if you know what it does, without having to know how it does it. In fact, in your programming so far, you have routinely used a wide variety of C library functions without knowing their implementation details (even ones that you may have written an equivalent for as a practice exercise may be implemented in a much more optimized manner in the real C library). 13.1.1 The Seven-Item Limit One of the reasons abstraction is crucial to large systems is that it breaks them down into pieces we can think about at one time. Psychologists have found1 that the human brain is generally limited to thinking about approximately seven things at any given time. However, the “things” in this limitation are in terms of pieces of information with semantic meaning to the person thinking about them. For example, it is difficult to remember the sequence of letters zyqmpwntyorprs but easy to remember the word unsurmountable, even though they both have the same number of letters. The word unsurmountable is one logical piece of information and thus requires you to remember only one thing, while the gibberish zyqmpwntyorprs requires you to remember each individual letter, as it is not a meaningful word. Meanwhile, even though dzqf is also gibberish, you can easily remember it because it has few letters. Note that being able to think about a function is important in a variety of contexts. If a function’s complexity exceeds your cognitive capacity, it becomes very difficult to write— there are just too many things going on to keep straight in your head as you try to generalize, and patterns become difficult to find. However, this complexity is also a problem when you want to understand what code that is already written does. If you write the code, and it does not work, understanding it is crucial to effective debugging. You may also need to understand code to modify it. Remember that real software has a long life span—you might need to go back to code you (or someone else) wrote years ago to change it in support of a new feature. Abstracting code out into functions (or other larger modules) provides a way to wrap the entire behavior up into one logically meaningful thing—the resulting function has a well- defined task, and you can think about it in terms of what it does (its interface) rather than thinking about the details of how it does it. Having the function as one logical unit you can think about means that it only counts for one in the limit of the seven things you can think about at once. To see this principle in action in a programming context, consider the following code (do not invest too much effort in trying to puzzle out what it does): 1 roster_t * readInput(const char * fname) { 2 FILE * f = fopen(fname, \"r\"); 3 size_t sz = 0; 4 char * ln = NULL; 5 char * endp = NULL; 6 if (f == NULL) { 7 return NULL; //Could not open file->indicate failure 8}

9 roster_t * answer = malloc(sizeof(*answer)); 10 answer->numStudents = readAnInteger(f); 11 if (getline(&ln, &sz, f) == -1) { 12 fprintf(stderr,\"Could not read a line (expecing a number)\\n\"); 13 exit(EXIT_FAILURE); 14 } 15 answer->numStudents = strtol(ln, &endp, 10); 16 //skip whitespace 17 while (isspace(*endp)) { 18 endp++; 19 } 20 if (*endp != ’\\0’) { 21 fprintf(stderr, \"Input line was not a number\\n\"); 22 exit(EXIT_FAILURE); 23 } 24 answer->students = malloc(answer->numStudents * sizeof(*answer->student 25 if (answer->students == NULL) { 26 free(answer); 27 return NULL; 28 } 29 for (int i =0; i < answer->numStudents; i++) { 30 student_t * s= malloc(sizeof(*s)); 31 s->name = NULL; 32 getline(&s->name, &sz, f); 33 char * p = strchr(s->name, ’\\n’); 34 if (p != NULL) { 35 *p = ’\\0’; 36 } 37 if (getline(&ln, &sz, f) == -1) { 38 fprintf(stderr,\"Could not read a line (expecing a number)\\n\"); 39 exit(EXIT_FAILURE); 40 } 41 s->numClasses = strtol(ln, &endp, 10); 42 //skip whitespace 43 while (isspace(*endp)) { 44 endp++; 45 } 46 if (*endp != ’\\0’) { 47 fprintf(stderr, \"Input line was not a number\\n\"); 48 exit(EXIT_FAILURE); 49 } 50 s->classes = malloc(s->numClasses * sizeof(*s->classes)); 51 for (int i = 0; i < s->numClasses; i++) { 52 s->classes[i] = NULL; 53 getline(&s->classes[i], &sz, f); 54 p = strchr(s->classes[i], ’\\n’); 55 if (p != NULL) { 56 *p = ’\\0’; 57 } 58 } 59 answer->students[i] = s; 60 } 61 int result = fclose(f); 62 assert(result == 0); 63 free(ln); 64 return answer; 65 } This giant function is a huge mess! Not only is it ridiculously difficult to understand what it does, but it also duplicates code—performing the same task in multiple places. Duplication of code is generally bad for many reasons. The most straightforward reason not to duplicate code is that you duplicate the effort to write it. Perhaps more importantly, it is more difficult to maintain—if you need to change something, you have to remember (or your development teammate needs to figure out) to change it in two places. Finally, if you have an error in your code you have to fix it in multiple places. This giant mess of code really should be about four functions. In fact, this comes from combining four functions from the moderately-sized example we work in Section 13.4. Keep

this mess in mind as you read that section, and contrast the difficulty in understanding this piece of code with understanding the corresponding four functions in that example. 13.1.2 Hierarchical Abstraction Abstraction works hierarchically—we can combine the smallest “building blocks” of our system into larger logical units. We can then combine those larger “blocks” into larger units and repeat this process until we have a large, complex system. Of course, ideally, at any granularity where we inspect the system (e.g., read the code), we have something small enough to fit into our cognitive capabilities—something we can analyze and understand. Returning to our example of letters and words, words get combined into sentences, sentences get combined into paragraphs, paragraphs get combined into sections, and so forth. You can see the same effects of thinking about things in logical units at any of these granularities: think about the sentence “I am learning about why abstraction is important in programming,” and the gibberish phrase: “A in tricycle grail air discontinue my flammable to imprecision.” As with the letters/words example, you can think about the first more easily, as it has a logical meaning, even though they both have the same number of words (and letters in each word). Designing software with hierarchical abstraction can primarily happen in two ways: bottom-up, or top-down. In a bottom-up design, you start with the smallest building blocks first, and build successively larger components from them. This approach lends itself well to incremental testing (build a piece, test it, build a piece, test it, etc.). However, the downside is that you have to be sure you are building the right blocks, and they will all fit together in the end. The other design philosophy is top-down. In top-down, you start by designing the highest-level algorithm and determine what other functions you need in support of it. You then proceed to design these functions until you reach small enough functions that you do not need to abstract out any more pieces. This design approach should sound rather familiar, as it is exactly what we have described to you when discussing how to translate your generalized steps into code. The advantage here is that you know exactly what pieces you need at every step (they are required by the higher-level algorithms that you have already designed) and how they fit together. The downside to top-down design can arise in testing. If you try to write the whole thing then test it, you are asking for trouble (as we discussed in Chapter 6). However, if you implement your algorithm in a top-down fashion, you may have high-level algorithms that rely on lower-level pieces that do not exist. This problem can be overcome in a couple of ways. First, you can still test what you have every time you build a complete piece. That is, when you finish a “small block,” you can test it. Then once you have built (and tested) all the “small blocks” for a medium-sized piece, you can test it. Effectively, you are building and testing your code in a bottom-up fashion, even though you have done the design in a top- down fashion (and may have some partially implemented/untested higher-level algorithms). The second way you can address this problem is to write “test stubs”—simple implementations of the smaller pieces that do not actually work in general but exhibit the right behaviors for the test cases you will use to test your higher-level algorithms. Such test stubs may be as simple as hard-coded responses (e.g., if (input == 3) {return 42;}). You can then test your higher-level functions assuming the lower-level pieces work correctly, before proceeding to implement those pieces. 13.2 Readability

As we mentioned before, writing code that can be read and understood—both by yourself and by others—is a crucial skill as you develop code in larger projects with a longer life span. Many aspects of a code’s design and implementation contribute to its readability—or lack thereof. Many novice programmers get completely focused on getting their code to work and ignore its readability. While correct code is critical, it is harder to make unreadable code work correctly. Additionally, you are likely to develop bad habits—which become harder to break the longer you have them. You do not want to end up like this guy http://xkcd.com/1513/. 13.2.1 Function Size As we just discussed, smaller functions are easier to read and understand (as well as easier to write) than larger functions. A general rule of thumb is that your function should fit comfortably into one screen—that is, you should be able to read the entire thing all at once without scrolling. Of course, exactly what constitutes “one screen” somewhat depends on your terminal window size and how you format your code, so remember that this is a guideline.2 If you end up with a function that makes logical sense and is over by three lines, do not sweat it too much. Likewise, if you have a function that performs eight different logical tasks, you should not say “well that is fine, I managed to cram it all on one screen.” 13.2.2 Naming The names you use for identifiers can contribute significantly to (or detract significantly from) the readability of your code. Name your variables, functions, and types to indicate what they mean and/or do. If you can tell what something does from reading its name, you do not have to work (as hard) to figure it out. Of course, at the same time, you should not name your variables in overly long ways that become cumbersome to type. A good rule of thumb here is that the length of a variable’s name should be proportional to the size of its scope, and the complexity of its use. It is reasonable to name the counter variable of a for loop i because it has a relatively small scope (one loop) and a simple use (it just counts: you can tell that from reading the for loop where it is declared). Functions and types should therefore generally have relatively descriptive names. They (usually) exist at quite large scopes (all of the functions we have seen so far have had a scope of the entire program) and perform complex tasks. Some people like naming conventions. We have seen a few naming conventions so far. One is placing a _t suffix on the type name (e.g., color_t). Another is writing the names of constants in all capitals. Some programmers like the “Hungarian notation” scheme, where variable names are prefixed with a sequence of letters indicating their types (e.g., chInput starts with a “ch” indicating its type is char, and while iLength starts with an “i” indicating its type is int). Another set of conventions arise in how you “glue together” multiple words, as spaces are not allowed in variable names. The two major ways are to use underscores (_) wherever you would want spaces (e.g., num_letters_skipped). The other is to capitalize the first letter of words other than the first (e.g., numLettersSkipped)—this approach is called “inner caps” (also called “camel case”). Either of these methods is fine, though many programmers have a strong preference for one over the other. We note that “inner caps” can also be applied to names that start with a capital letter on the first word by convention—such as class names, which we will see when we discuss C++ in Chapter 14. 13.2.3 Formatting

The formatting of code can also have a large impact on its readability. Programmers largely agree on some basic rules. One common rule is that code should be indented to reflect the block structure—i.e., in C, code inside more curly braces should be indented more than code inside fewer curly braces. Another is that one should generally place a newline at the end of a statement, so that consecutive statements appear on different lines. 1 int sumNums (int n) { 1 int sumNums (int n) 2 int total = 0; 2{ 3 for (int i = 0; i < n; i++) { 3 int total = 0; 4 total = total + n; 4 for (int i = 0; i < n; i++) { 5} 5 total = total + n; 6 return total; 6} 7} 7 return total; 8} (a) Java style. (b) One True Brace Style (1TBS). Figure 13.1: Four commonly used conventions for curly brace placement. However, programmers typically have much dissension about the specific details of code formatting. Probably the most contentious topic is the placement of curly braces. Figure 13.1 shows four different brace-placement conventions: Java Style, 1TBS, Allman Style, and GNU Style. We note that there are other variations on many of these, typically involving whether the else “cuddles” the close curly brace of the corresponding if (that is, the else is on the same line as the closing brace), and/or whether curly braces are used around single-line blocks. There are of course, other styles not shown here as well. We strongly prefer the so-called “Java” style (so named because Sun’s style guidelines used it, and thus much of the code for Java uses it) for a couple reasons. First, placing the open brace on the same line as the if/else/for/… that it belongs to helps to avoid errors where a programmer accidentally adds a line of code to the body, but mistakenly places it before the braces. To see this problem, consider the following code: 1 if (hasPrivileges(user)) 2 logActivity(user,action); //accidentally added in wrong place 3{ 4 someSecureActivity(action); 5} Here someone has added code—a call to a function to log some activity—intending to write it in the body of the if but has separated the curly braces from the if. In this case, the logActivity call is the entirety of the body of the if, and the remaining code is legal, but is not conditionally protected by the if. That is, the code behaves as if it were: 1 if (hasPrivileges(user)) { 2 logActivity(user,action); 3} 4 someSecureActivity(action); Such mistakes can contribute to serious errors in the software. In this hypothetical example, the mistake would almost certainly prove to be a security vulnerability, allowing any user to perform the privileged action (and to make matters worse, not logging the activity if the user does not have privileges to perform that action). We prefer Java style over 1TBS primarily from a consistency perspective (the curly brace is always in the same place relative to the rest of the code). Perhaps most importantly,

we recommend a brace style in which you always use curly braces, even when they can be omitted around single-line blocks. Omitting them can make introducing errors easier. Ultimately, what brace style you use is going to either be dictated by the style guidelines wherever you work or left up to your personal choice. 13.2.4 Commenting and Documentation Well-documented code is significantly easier to read than poorly-document code. Good documentation provides insights into the algorithm being used, explains why things that may seem surprising are correct, and generally allows the reader to understand how and why the code works the way it does. Of course, the key here is in writing good documentation—not just writing a lot of documentation. Most documentation is written as comments in the code. We have seen comments before and already learned that they indicate text that is for humans and thus is ignored by the compiler. In C and C++, comments can either be written with // to comment to the end of the line or /* */ to comment everything enclosed by the slash-star and star-slash. Understanding how to write good documentation can be quite tricky for novice (and even moderately experienced) programmers. Skill in this area generally increases as you read other people’s code (or your own code that you have not seen in a long time) and find comments particularly useful or lacking—things you wish the comments explained. Here are some good rules of thumb to help write better documentation: Document Large-Scale Design As you design larger programs, you will have multiple pieces that fit together. Describe how they fit together. What are the interfaces between modules? What are the invariants of the whole system? Describe Each Component For each component (function, object—when we get to C++, or file) of your system, write a comment at the start describing it. Start by describing the interface for anyone who just needs to use the component and does not need to know about its implementation details. For functions, describe what each parameter means as well as any restrictions on their values. Describe what the function returns. If it has any side effects, explain them. Continue by describing implementation details for anyone who needs to modify it. If it uses a commonly known algorithm, say so. If it uses an algorithm you designed yourself, explain how the algorithm works. Do Not Comment The Obvious A common mistake is to believe that just writing a lot of comments makes for good documentation. However, comments that describe the obvious are counter-productive—they clutter up the code while providing no useful information. Consider the following example: 1 int sumNums(int n) { 2 int total = 0; //declare total, set to 0 3 for (int i = 0; i < n; i++) { //for loop 4 total = total + n; //add n to the total 5} 6 return total; //return the total 7} Here, the programmer has written four comments, but none of them contribute anything useful to understanding the code. Anyone who understands the basics of how C works (i.e. what we covered in Chapter 2) can get the same information instantly just by looking at the code.

Explain The Unexpected If your code contains something unusual, such as a statement that is correct but could appear to be erroneous, you should document why that statement is correct. When someone unfamiliar with the code reads it, this documentation will save them from wondering whether or not the unusual aspect of the code is an error—they can simply read the explanation, rather than trying to figure out if it is broken. In general, if you think someone would ask “Why does it do that?” or “Is that right?” you should preemptively answer that question with a comment. Consider the following example of code with useful documentation in it: 1 /* This function takes two parameters: 2 * array (which is an array of ints) 3* n (the number of items in ’array’) 4 * and sorts the integers found in ’array’ into ascending order. 5 * The sorting algorithm used here is the widely-known \"quick sort.\" 6 * For details, see 7 * - \"All of Programming\" (Hilton + Bracy), Chapter 26, or 8 * - \"Introduction to Algorithms\" (CLRS), Chapter 7. 9 */ 10 void sort(int * array, size_t n) { 11 if (n <= 1) { 12 return; //arrays of size 1 or smaller are trivially sorted 13 } 14 //i starts at -1: it is incremented before it is used to index the array 15 int i = -1; 16 //j starts at n - 1 even though it is decremented before it 17 //is used to index the array, since array[n - 1] is our pivot. 18 int j = n - 1; 19 //we just use array[n - 1] here for simplicity. In a real implementation, 20 //we might want more sophisticated pivot selection (see CLR) 21 int pivot = array[n - 1]; 22 while (1) { 23 do { //scan from left for value >= pivot 24 i = i + 1; 25 } while (array[i] < pivot); 26 do { //scan from right for value < pivot 27 j = j - 1; 28 } while (j >= 0 && array[j] >= pivot); 29 if (i >= j) { //if i and j have crossed, data is partitioned. 30 break; 31 } 32 //swap array[i] with array[j] 33 int temp = array[i]; 34 array[i] = array[j]; 35 array[j] = temp; 36 } 37 //swap array[i] with the pivot (array[n - 1]) 38 array[n - 1] = array[i]; 39 array[i] = pivot; 40 //recursively sort the partitioned halves: [0, i) and [i + 1, n) 41 sort(array, i); 42 sort(&array[i + 1], n - i - 1); 43 } The code begins with a description of the function from a high level. It describes the interface to the function; if you only need to use the function, you can tell how to do so from just reading the comment. It also describes the algorithm used in this function. In this particular case, since the algorithm is well known, it provides a brief description, and a couple of references in case the reader is unfamiliar with it. Note that this function is a bit long (it does not quite fit into my terminal), so ideally we should abstract part of it out into its own separate function. Lines 14–36 are a great candidate for pulling out into their own function, as they perform a specific logical task (called “partitioning” the data—which you will learn about in Section 26.2.3).

Inside the code, the comments describe why or how things happen, as well as the rationale behind things that seem unusual. For example, the comment describing the initialization of i explains why it is initialized to , which may be confusing (or even seem like a mistake) to the unfamiliar reader. 13.3 Working in Teams Another consideration in larger programming tasks is working in teams. Depending on the size of the programming task, teams may range from two or three members to hundreds. Working with teams magnifies the importance of the considerations we have discussed so far. However, it also introduces its own challenges and benefits. One issue that becomes much more important when programming in a team is the use of a good revision control system (e.g., Git, Subversion, or Mercurial). These systems facilitate multiple people editing the same code base at once, as well as giving the ability to find out who made which changes in the code and track older versions. We discuss git in Section D.4. Another significant issue in programming with larger teams is integration—putting the pieces together. Programmers may write and test their own modules, determining that they work in isolation, only to discover that they do not work together with the other programmers’ modules when they attempt to integrate. Problems can arise from misunderstood (or imprecisely defined) interfaces and differing expectations. Many programmers underestimate the time required for integration, which can actually be quite significant. Of course, programming in teams has benefits too—primarily that the team can accomplish more in the same time than any individual can. Of course, the simplest way this works is by the fact that multiple people are programming at the same time. However, there are other benefits to working in teams, arising from the old principle of “two heads are better than one.” One nice way to work in partnerships is pair programming. In pair programming, two programmers share a computer with one “driving” and the other “navigating.” The driver controls the keyboard and actually writes the code. Meanwhile, the navigator watches the code being written and thinks about what is happening. The navigator is responsible for checking for problems with code—whether they are just local mistakes or failure to respect global invariants. The programmers may trade roles whenever they feel it is appropriate. 13.4 A Modestly Sized Example To see all of these concepts in action, we are going to consider a modestly sized programming example in detail (we note that this is still a rather small program in the grand scheme of things). Write a program roster that reads in a file with the following format: Number of students Student Name Number of classes Classname 1 Classname 2 ... Classname N Student Name Number of classes Classname 1

Classname 2 ... Classname N That is, the first line contains a single integer that is the number of students described in the file. After that, there are student descriptions, which each start with a line containing the student’s name. The next line is the number of classes that the student is in. After that, there are the specified number of lines, each of which contains the name of one class. Your program should read this file in and then output the class roster for each class. Specifically, for each class, it should create a file called classname.roster.txt (where classname is the name of the class) and print each of the students who are in that course (one per line) into that file. For example, if your input file were 4 Orpheus 3 Mus304 Lit322 Bio419 Hercules 2 Gym399 Lit322 Perseus 3 Lit322 Phys511 Bio419 Bellerophon 2 Gym399 Bio419 Then your program would create the following five output files: Note that if the file does not obey this format, your program should print a meaningful error message to stderr, and exit with a failure status.

This problem is far too large to write as a single function. Doing this task well involves breaking it down into about a dozen functions. We can intuitively see the need to break things down just by observing that there are several discrete tasks we will need to perform: reading our input (which itself has smaller subtasks, such as reading a number with error checking, and reading the information for one student), “rearranging” the information to the format we need, writing the output (which itself has smaller subtasks, such as computing the filename for a class and writing out the information for a class) and freeing the memory we allocated when we read the input. As always, we should begin with Step 1 and work through the programming process we have learned all throughout this book. Of course, for a task this big, we should recognize that we are seeking to break the task down into many functions, so we should be content with relatively complex steps—which then dictate what functions we need. Video 13.1 shows the initial steps for attacking this problem. Video 13.1: Initial steps for this example. From what we have done so far in Video 13.1, we can make a couple important steps towards solving this problem. The first is that we can define several of the types involved in the problem. The video worked through how we see our student_t and roster_t types. We can similarly work through what we need to represent our list of all the classes for a classes_t type. We would then come up with the following declarations: 1 // Each student has a name and an array of classes 2 struct student_tag { 3 char * name; 4 char ** classes; 5 int numClasses; 6 }; 7 typedef struct student_tag student_t; 8 9 //A roster is an array of student records (with the size) 10 struct roster_tag { 11 student_t ** students; 12 int numStudents; 13 }; 14 typedef struct roster_tag roster_t; 15 16 //An array of class names (with the size) 17 struct classes_tag { 18 char ** classNames; 19 int numClasses; 20 }; 21 typedef struct classes_tag classes_t; Having these type declarations in mind (as well as the pictures we drew of them in Video 13.1) will be helpful as we work through the subproblems that we are about to create. These types will be the input and/or output types of many of these other algorithms. Knowing exactly what they look like allows us to draw precise pictures in Step 1 for each of those problems, coming up with the right algorithms. The other important step we took in the video was coming up with the general algorithm for main: Read the input from the file named by argv[1] (call this r) Make a list of all of the (unique) class names (call this result c) Write one output file per class (from c and r) We will want to make a few alterations to this algorithm. First, we will notice that we did not write down anything about returning our answer—however, main always returns an int. In this case, we should return EXIT_SUCCESS. As we think carefully about what our other

functions (that we are about to write) will do, we may realize that they will need to malloc some memory—so we should free that memory when we are done with it. If we do not realize this fact yet, we may need to come back later and add the freeing. Furthermore, if we test carefully (with corner cases) in Step 4, we might realize we need to add some error checking. Ultimately, this results in a nice generalized algorithm for main: Check that the argc == 2 (fail if not) Read the input from the file named by argv[1] (call this the_roster) Check that r != NULL (fail if not) Create the list of all of the class names (call this result unique_class_list) Write all the class roster files from unique_class_list and the_roster Free memory held by unique_class_list Free memory held by the_roster return EXIT_SUCCESS As long as we abstract each of the complex steps out into its own function, this results in a nice, short, easy-to-understand main function: 1 int main(int argc, char ** argv) { 2 if (argc != 2) { 3 fprintf(stderr, \"Usage: roster inputname\\n\"); 4 return EXIT_FAILURE; 5} 6 roster_t * the_roster = readInput(argv[1]); 7 if (the_roster == NULL) { 8 fprintf(stderr, \"Could not read the roster information\\n\"); 9 return EXIT_FAILURE; 10 } 11 classes_t * unique_class_list = getClassList(the_roster); 12 writeAllFiles(unique_class_list, the_roster); 13 freeClasses(unique_class_list); 14 freeRoster(the_roster); 15 return EXIT_SUCCESS; 16 } Having written main, we now have five new programming tasks: readInput, getClassList, writeAllFiles, freeClasses, and freeRoster. We will leave working through the details (Steps 1–4) of readInput to the reader, but one probably comes up with code that looks like this: 1 roster_t * readInput(const char * fname) { 2 FILE * f = fopen(fname, \"r\"); 3 if (f == NULL) { 4 return NULL; //Could not open file->indicate failure 5} 6 roster_t * answer = malloc(sizeof(*answer)); 7 answer->numStudents = readAnInteger(f); 8 answer->students = malloc(answer->numStudents * 9 sizeof(*answer->students)); 10 if (answer->students == NULL) { 11 free(answer); 12 return NULL; 13 } 14 for (int i = 0; i < answer->numStudents; i++) { 15 answer->students[i] = readAStudent(f); 16 } 17 //we could check if we have reached EOF here-- 18 //depends on what we consider \"correct\" for the format 19 //Directions don’t specify if this is an error. 20 int result = fclose(f); 21 assert(result == 0); 22 return answer; 23 }

Note that again, we have formed two new programming tasks to do—writing readAnInteger and readAStudent. While this may seem counterproductive—we have gone from one programming task (solving this entire problem), to five programming tasks (as listed above), to six programming tasks (the remaining four from above plus the new two)—we have actually made significant progress. Each of our remaining tasks is far smaller and simpler than the ones that motivated their creation. Furthermore, by writing functions for each logical task, we will reduce code duplication. We will find that the same task comes up in multiple contexts and be able to just call a function we already wrote. For example, we will find that readAnInteger is useful in readAStudent, which might look like (again, we leave Steps 1–4 to the reader): 1 void stripNewline(char * str) { 2 char * p = strchr(str, ’\\n’); 3 if (p != NULL) { 4 *p = ’\\0’; 5} 6} 7 student_t * readAStudent(FILE * f) { 8 student_t * s = malloc(sizeof(*s)); 9 size_t sz = 0; 10 s->name = NULL; 11 getline(&s->name, &sz, f); 12 stripNewline(s->name); 13 s->numClasses = readAnInteger(f); 14 s->classes = malloc(s->numClasses * sizeof(*s->classes)); 15 for (int i = 0; i < s->numClasses; i++) { 16 s->classes[i] = NULL; 17 getline(&s->classes[i], &sz, f); 18 stripNewline(s->classes[i]); 19 } 20 return s; 21 } At this point, we have only introduced one new (rather simple) additional function, stripNewline (which just removes the \\n from the end of the string), which we also show above. When we write the readAnInteger function (which we will not show here, but you should be able to write it), we will not need any other functions at all—the only complex steps in readAnInteger can be implemented by calling functions in the C library. At that point, we will have completed everything we needed for readInput. Contrast these four functions with what we wrote in Section 13.1.1. Even though these four functions perform the same behavior as the giant function we saw earlier, they are much more readable, debuggable, and maintainable. As you write each of these functions, you would want to test them. Testing each portion of the code in isolation gives us many benefits, as we discussed in Section 6.1. You can debug any problems you have here now, and be confident that each works before you proceed (which involves making functions that rely on these smaller functions). Testing the smaller functions is relatively straightforward (you will want to write test harnesses for them, with main functions that are separate from the rest of your program). However, readInput is a bit larger and more complex—you will need a way to see if it got the right output easily to test it. To perform this testing, we could write another function that we do not really need for our main task (void printClassRoster(roster_t * r)), which prints out the class roster. We then change main (or write a separate main in another file) to temporarily look like this: 1 int main(int argc, char ** argv) { 2 if (argc != 2) { 3 fprintf(stderr, \"Usage: roster inputname\\n\"); 4 return EXIT_FAILURE;

5} 6 roster * the_roster = readInput(argv[1]); 7 if (r == NULL) { 8 fprintf(stderr,\"Could not read the roster information\\n\"); 9 return EXIT_FAILURE; 10 } 11 printRoster(the_roster); //print what we read. 12 //skip the rest: it isnt written yet anyways 13 /* classes * unique_class_list = getClassList (the_roster); */ 14 /* writeAllFiles (unique_class_list, the_roster); */ 15 /* freeClasses(unique_class_list); */ 16 /* freeRoster(the_roster); */ 17 return EXIT_SUCCESS; 18 } We would then proceed with getClassList in much the same fashion—working Steps 1– 5 and abstracting complex steps out into their own functions. In this case, we will likely want to abstract out a function to check if an array of strings contains a particular string (this function will also prove useful when we go to write our output files) and may or may not want to abstract out the function to add a string to the list of classes (which requires reallocing the array). We might end up with a function like this: 1 classes_t * getClassList(roster_t * the_roster) { 2 classes_t * ans = malloc(sizeof(*ans)); 3 assert(ans != NULL); 4 ans->numClasses = 0; 5 ans->classNames = NULL; 6 for (int i = 0; i < the_roster->numStudents; i++) { 7 student_t * current_student = the_roster->students[i]; 8 for (int j = 0; j < current_student->numClasses; j++) { 9 if (!contains(ans->classNames, 10 current_student->classes[j], 11 ans->numClasses)) { 12 addClassToList(ans, current_student->classes[j]); 13 } 14 } 15 } 16 return ans; 17 } The two pieces we abstracted out are contains: 1 int contains(char ** array, const char * str, int n) { 2 for (int i = 0; i < n; i++) { 3 if (!strcmp(array[i], str)) { 4 return 1; 5} 6} 7 return 0; 8} and addClassToList: 1 void addClassToList(classes_t * class_list, char * name) { 2 class_list->numClasses++; 3 class_list->classNames = realloc(class_list->classNames, 4 class_list->numClasses * 5 sizeof(*class_list->classNames)); 6 class_list->classNames[class_list->numClasses - 1] = name; 7} After writing these functions, we should again test everything together we have so far by writing a function to print the list of classes and putting a call to it in main. Our last programming task is to write our output files. We might end up with something like this:

1 void writeOneFile(const char * cName, roster_t * r) { 2 char * fname = makeRosterFileName(cName); 3 FILE * output_file = fopen(fname, \"w\"); 4 if (output_file == NULL) { 5 perror(\"fopen\"); 6 fprintf(stderr,\"Trying to open %s\\n\", fname); 7 abort(); 8} 9 free(fname); 10 for (int i = 0; i < r->numStudents; i++) { 11 student_t * s = r->students[i]; 12 if (contains(s->classes, cName, s->numClasses)) { 13 fprintf(output_file, \"%s\\n\", s->name); 14 } 15 } 16 int result = fclose(output_file); 17 assert(result == 0); 18 } 19 void writeAllFiles(classes_t * unique_class_list, roster_t * the_roster) 20 for (int i = 0; i < unique_class_list->numClasses; i++) { 21 writeOneFile(unique_class_list->classNames[i], the_roster); 22 } 23 } This code abstracts out the task of writing one file into its own function, leaving the writeAllFiles to simply iterate over the class list, and let writeOneFile do the major work. The writeOneFile function abstracts out makeRosterFileName, as that was itself a somewhat complex step in translating the generalized algorithm into code. We can then write this function: 1 char * makeRosterFileName(const char * cName) { 2 const char * suffix = \".roster.txt\"; 3 unsigned len = strlen(cName) + strlen(suffix) + 1; 4 char * ans = malloc(len * sizeof(*ans)); 5 snprintf(ans, len, \"%s%s\", cName, suffix); 6 return ans; 7} At this point, we would have completed the programming task. We wrote 14 functions, but each function is a reasonable size (all have fewer than 25 lines) with a clearly defined purpose. Notice how this abstraction contributes to the readability of the code. You can look at a function, and it is small enough that you can think about what it does. You can then understand the higher-level functions in terms of the lower-level functions they call—knowing what they do, without having to worry about how they do it at that point. Such is the benefit of good abstraction. Additionally, our code is easy to change. For example, suppose we decide to change the format of the input file so that each student’s entry does not start with the number of classes that they have, but instead, their entry ends with a blank line. We would only need to change readAStudent, as that code is the only part that handles reading a student’s information. Everything else is isolated from the details of how to read a student by abstracting that task into the readAStudent function. The rest of the code (in particular, readInput) only needs to know that readAStudent will read one student entry and return a pointer to it. If we made more drastic changes to the input format, then the impact on our code changes would be limited to readInput and the functions it calls. Nothing else cares about the details of how the input is read. 13.5 Even Larger Programs As the size of our programming problems continues to grow, so does the need to break the task down into manageable pieces. Writing small pieces of code then testing them is the only

way to make solid progress. The opposite approach (which is a poor choice) is the big bang approach, in which the programmer tries to write all of the code, and only then starts testing and debugging. One important way to split larger problems into smaller problems is to start with a minimal set of features—implement, test, and debug those—then add new features one at a time. After you add each new feature, retest the entire system, and make sure that everything still works. This model of development requires more discipline (resisting the temptation to write everything all at once—and hope it will all just work) but pays off in terms of increased overall productivity and software quality. Discipline (especially under pressure) is one of the key features of good programmers—a good programmer will work (whether implementing, debugging, and testing) in a disciplined manner, especially under time pressure. Remember: “haste makes waste.” As an example of how we might apply this principle, consider writing a program to let someone play chess. The first thing we might do is just write the program so that it displays the board but not even any pieces. This may not sound like much, but it is the smallest piece we can make and thus something we can and should stop and test before we proceed. Once we have this part working, we might add displaying the pieces on the board and test again. A next step might be to allow the user to move pieces around but without worrying about the legality of the moves—just letting the user pick up any piece and put it down anywhere else. At this point, it is likely quite useful to add code to save and load a board position. Whether or not we intend to have this feature in the final game, it will prove incredibly useful for testing—letting us set up and use test cases in an efficient manner. As with all other functionality, we should test this out thoroughly—we would not want our later testing confused and complicated by poor infrastructure. After testing this functionality, our next step would be to add the rules of the game one by one. We can add the basic rules for each piece moving and after each one, test the code again. After all the basic moves, we can add castling and other complex rules (and test each as we add them). We can then add code to check for winning (and test) and drawing (and test). If we want our program to have other features (e.g., playing across a network), we can then add them one at a time (and for large features, break them down into smaller pieces) and test as we go. 13.6 Practice Exercises Selected questions have links to answers in the back of the book. • Question 13.1 : How many pieces of information can the human brain work with at a time? • Question 13.2 : What is abstraction? Why is it important? • Question 13.3 : Why is it important to write readable code? How does good documentation improve the readability of code? • Question 13.4 : What is a reasonable size for a function? • Question 13.5 : What is the “big bang” approach to developing a large piece of software? Why is it bad? How can you avoid it? • Question 13.6 : Do the examaple problem from Section 13.4 (without referencing the pieces of the solution provided in the text). You do not need to come up with the exact same answer, but you should be able to work through the programming process and break it down into reasonably sized functions. • Question 13.7 : Change your solution to the previous question to adapt to a new input format, where each student’s information is terminated by a blank line instead of having a count of how many classes the student is in.

• Question 13.8 : Write a program that takes two command line arguments, both of which name files. The first file contains a “story” with some words replaced by the underscore (’_’) character. The second contains a list of words that can be used to fill in the blanks to complete the story. The second file contains one word per line. Your program should read the first file, and print its contents, except every time it encounters an underscore, it should pick a random word from the second file, and print it instead. For example, the first input file might contain the following “story”: Once upon a _ there was a _. The _ lived in a very scary _. One day, the _ left his _ and went in search of a _. This _ is getting pretty ridiculous, so we are going to _ it right here. Have a nice _. and the second input file might contain the following word list: dragon sword forest house cave cake fire cellphone knight horse tree gold ship One possible output of the random story program might then be Once upon a dragon there was a horse. The gold lived in a very scary cave. One day, the sword left his sword and went in search of a ship. This house is getting pretty ridiculous, so we are going to sword it right here. Have a nice cellphone. Note: we will improve on our random story program in Question 20.8, after we have learned about some data structures. 12 Dynamic AllocationII C++ Generated on Thu Jun 27 15:08:37 2019 by L T XML

All of Programming13 Programming in the Large14 Transition to C++

Part II C++ 14 Transition to C++ 15 Object Creation and Destruction 16 Strings and IO Revisited 17 Templates 18 Inheritance 19 Error Handling and Exceptions 13 Programming in the Large14 Transition to C++ Generated on Thu Jun 27 15:08:37 2019 by L T XML

II C++II C++15 Object Creation and Destruction

Chapter 14 Transition to C++ Now that we have learned the basics of programming and are starting to concern ourselves with larger problems, we are going to switch from C to C++. C++ builds on C (it is mostly a superset of C) and introduces a variety of features that are useful for programming in the large. We make this transition before we delve into data structures and algorithms (in Part III), as one of the major advantages of C++ arises from its ability to better express generic data structures and algorithms—where one implementation can operate on different types of data (which we will see in Chapter 17). We note that we did not start with C++, as it is difficult to find a reasonable starting point without an understanding of C (we would need to leave important things unexplained). With our understanding of C, we can transition gradually into C++, though many of the examples as we transition will “look like a C programmer wrote them”—as they will do some things using C constructs that most C++ programmers eschew. Before we proceed, we would like to note that C++ is actually quite a complex language and thus a challenge to explain to novices. Often a concept in C++ will have an easily understood basic principle and general use but a variety of complex underlying technical details, especially for obscure corner cases. In writing about C++ for a novice programmer, this complexity often presents a difficult tradeoff between complete technical accuracy and something a novice (or even relatively experienced) reader can grasp. When faced with this tradeoff, we will

aim for understandability, avoiding delving into details that are unlikely to come up in most programs you will write in the near future (or possibly ever—we have been doing C++ for decades and never had use for some of the odder aspects of C++). To further complicate matters, there are three versions of the C++ standard (the formal rules of the language) in use in practice today (C++03, C++11, and C++14), as well as the most recent standard (C++17) with subtle technical differences. We will simplify the discussion by primarily explaining things in terms of C++03. However, we will briefly present some of the new features in C++11 in Section E.6 (the changes in C++14 are relatively minor)—these are mostly features aimed at experts and thus not important to get started in C++. At the same time, sometimes the standards are unclear and/or disagree with what is commonly done. In such cases, we may present the way things are typically done without delving into the subtle technical details. C++ also has its own terminology for many concepts, which differs from the terminology used in other similar languages. This terminology difference arises from C++’s heritage of being originally created as an improvement to C (which was initially compiled by translation into C). When such a situation arises, we will aim to present both sets of terminology. We will then use the terms interchangeably throughout the rest of the text. While this choice may offend C++ purists, we expect it to prove useful to anyone who goes on to program in other languages (e.g., Java). Remember: this book is about how to program and is not intended as a detailed dive into the dark corners of C++. If you want to learn all the nitty-gritty corner cases and subtleties of C++, you should find a book specifically

focused on the topic. If you truly want to become an expert in the exact details of the formal rules of the language, you might then proceed to read the language standard (which itself is longer than this entire book). 14.1 Object-Oriented Programming One core difference between C and C++ is that C++ supports object-oriented programming (OOP). In OOP, we think about our program in terms of objects, which have a state inside of them, and we ask the objects to perform actions. The actual implementation of how to perform that action is hidden from us (inside the object) and may vary from one type of object to another. As we will see in Chapter 18, we can make objects of different— but related—types (which may have different implementations of the same behavior) and store them in the same variables or arrays. Two of the primary concepts in OOP are classes and objects. Technically the only difference in C++ between a class and a struct is the default access control of its members (which we will discuss shortly). Objects are instances of classes—that is, when you “draw a box” for something of a class type, you have made an object. You may have multiple boxes for the same class (or struct) type—meaning you may have multiple objects of a given type. As you are familiar with from your experience with structs, each of these boxes has its own sub-boxes for the fields declared in the class (or struct). In C++, however, classes (and also structs) can have functions declared inside of them, which are key to the object-oriented nature. These functions are either called member functions or methods,1 and have special behavior related to being inside of the objects, which we

will discuss shortly. We will note that while methods can be declared inside of structs or classes in C++, many programmers adhere to the convention of using structs for types that only contains data, and classes for types that have methods. The syntax for declaring a class is quite similar to the syntax for declaring a struct. However, C++ does away with the requirement to use the struct keyword when using the struct tag to name the type. That is, if we declare a struct in C++, we can just use its tag as a type name. That is, we can just write the following code in C++ (but not in C): 1 struct myStruct { 2 int a; 3 int b; 4 }; 5 int main(void) { 6 myStruct x; //not legal in C, legal in C++. 7 return 0; 8} The same is true of classes—the following code is also legal: 1 class myClass { 2 int a; 3 int b; 4 }; 5 int main(void) { 6 myClass x; 7 return 0; 8} In fact, you would seldom see a C++ programmer write class myClass x; in this code.

Figure 14.1: Summary of the syntax for declaring a class. Figure 14.1 summarizes the syntax for declaring a class—the keyword class is followed by the name of the class. The members (fields and methods) of the class are contained inside of the curly braces, which are opened after the name of the class. Finally, the class declaration ends with a semicolon. 14.1.1 Access Control In C++, members (fields or methods) of a struct or a class can have their access restricted so that only code within the class can directly access them. There are three levels of access (also called visibility) that each member can have: public, private, or protected. If a member is public, it can be accessed by any piece of code. If a member is private, it can only be accessed by code within that class. We will discuss protected once we discuss inheritance in Chapter 18. In a struct, the default access is public, and in a class, the default access is private. At this point, a natural question for you to be asking is: why would we want to restrict access to the members of our class? Remember that abstraction is key to designing large systems. We want to present an interface any code can use but hide the implementation details— making these implementation details private lets us do so in a way that can be enforced by the compiler. To see an example of why we might want to do this, consider the following code, which declares a class for a bank account

(we would want to add a few more things to this, which we will see later): 1 class BankAccount { 2 private: 3 double balance; 4 public: 5 void deposit(double amount) { 6 balance += amount; 7} 8 double withdraw(double desiredAmount) { 9 if (desiredAmount <= balance) { 10 balance -= desiredAmount; 11 return desiredAmount; 12 } 13 else { 14 double actualAmount = balance; 15 balance = 0; 16 return actualAmount; 17 } 18 } 19 double getBalance() { 20 return balance; 21 } 22 void initAccount() { 23 balance = 0; //we will see a better way to 24 } 25 }; Here, we declare the balance field to be private— only code inside of the BankAccount class can access this field. We note that line 2 is not strictly needed—if we had omitted it, balance would still be private, as that is the default in a class. On line 4, we request public access control to all members that follow (until some other access control is requested). We then declare four methods: deposit, withdraw, getBalance, and initAccount (which initializes the balance to zero—we will see a better way in Chapter 15). The withdraw function takes a desired amount but returns at most the available balance. Note that by making the balance private, we can ensure other code cannot modify balance in inappropriate ways,2

e.g., withdrawing more money than is available. Furthermore, if we decided we wanted to log all changes to the account balance, we know we only need to modify the deposit and withdraw functions—no other code changes balance. Figure 14.2: Illustration of member visibility for classes and structs. Figure 14.2 illustrates the visibility of fields in a class and a struct. The regions shown in green contain public members of the class/struct, while regions shown in pink contain private members. The default access (before we explicitly write an access specifier) depends on how we declare the class/struct—and in fact, that is the only difference between declaring a class and declaring a struct in C++. For a class (on the left), the default access is private, while for a struct (on the right), it is public. In either case, once we explicitly write an access specifier, that level of visibility persists until we write another— fields c and d are public because they come after we have requested public visibility, and before we request private visibility. Once we write another access specifier, that level of visibility persists until we write another (or the class/struct ends).

14.1.2 Encapsulation: Methods Act on Objects We said earlier that C++ adds the ability to put methods inside of classes (or structs), which is a key aspect of the OOP paradigm. Looking at our BankAccount example, we see that there are four methods inside the BankAccount class, but why is this important? Classes encapsulate— combine into a single logical unit—the data and methods that act on them. That is, we can think of these methods as being inside each instance of the object. Calling them causes them to act on the data inside that particular instance of the object. For example, notice how these methods reference the balance field. When we call deposit on a particular bank account object, it will adjust the balance field inside that particular object. Notice that we talk about calling a method on a particular object. We can access these methods in the same way that we can access fields of a struct (which is the same as for fields of a class)—with either the dot (.) operator if we have the object directly, or with the arrow (->) operator if we have a pointer to it. For example, we might do 1 BankAccount myAccount; //declare a variable of type 2 myAccount.initAccount(); //call initAccount() on myAc 3 myAccount.deposit(42.50); //call deposit(42.50) on my Let us notice that in this example (as there is only one BankAccount), you could probably execute this code by hand and get the correct result, but you would be missing a key detail to actually do it correctly. Notice that the code inside the methods references the balance field. With only one BankAccount object, there is only one balance field, so you can just guess that it is the only one.

But what would happen if you had many instances of BankAccount (each of which would have its own balance field), and more complex code? How would you know which balance field (that is, which BankAccount box’s sub- box named balance) to reference? Last time we needed to resolve confusion about multiple boxes of the same name, we discussed the notion of scope—the range in which a variable can be seen. Here, our confusion is not a matter of scope—the name of the field is in scope for any of the methods inside the class3 —and that name refers to the field in the same object as the method. We could imagine each object as having its own copy of the code for each method in the class—and the code references the field in the object it is in. While the “code inside the object” approach works logically, it would be quite inefficient to implement—and to execute by hand (imagine copying all of the code for an object into it each time you make a new one!). Instead, C++ (and many other OO languages) adds an extra parameter to each method, called this, which is a pointer to the object the method is inside of. For a method inside a class of type T, you can think of the this pointer as if it were a parameter declared as T * const this (that is, a pointer to a T, the contents of which can be changed, but the pointer itself cannot be made to point at anything else). All references to fields in the object are implicitly this->field. Understanding of this is key to our correctly executing object-oriented code by hand. When you set up the frame for a method (called on an object), draw another box for the implicit argument, this. The value you should pass for this is a pointer to the object the method is being called on. If the method invocation looks

like ptr->method(args), then copy ptr. If the method invocation looks like object.method(args), then take the address of object (that is, pass an arrow pointing at object, as if you passed &object). As you execute the code inside of the method, if you encounter a reference to a member of the class, remember that it acts as if it has this-> before it. This rule applies to both fields and methods—that is, if you call a method inside an object, it is implicitly invoked on this. Video 14.1: Executing code with methods. Video 14.1 walks through an example of the execution of code with method calls on objects. 14.1.3 const Methods There are times when we want to specify that the implicit this argument is a const pointer. That is, that the compiler should consider it to be a const T * const this rather than just T * const this. As we do not explicitly declare this ourselves, C++ provides a special place to put the const: after the close parenthesis of the parameter list, but before the open curly brace of the function body. For example, we might write a Point class like this: 1 class Point { 2 private: 3 int x; 4 int y; 5 public: 6 void setX(int new_x) { 7 x = new_x; 8} 9 void setY(int new_y) { 10 y = new_y; 11 } 12 int getX() const { 13 return x;

14 } 15 int getY() const { 16 return y; 17 } 18 }; Here, the getX() and getY() methods are declared with const on the end, meaning that their implicit this argument is a const pointer—we cannot modify anything in the object it points at (which is the object the method was invoked upon). Declaring methods in a const-correct fashion (meaning, we put const on them exactly when it is correct to do so) is important, as we can invoke a const method upon a const object but cannot invoke a non- const method upon a const object. While that last sentence sounds technically complicated, it is easy to see with an example: 1 void someMethod(const Point * p) { 2 int x = p->getX(); //legal: getX() is const 3 p->setX(42); //illegal: setX is not const 4 //but *p is const! 5} Here, we have a method that takes a const Point * as a parameter. Calling a const method (such as getX()) on p is legal, as the const declaration ensures we will not modify the contents of the object (which is what the const on the declaration of p promises to anyone who calls someMethod). However, we cannot invoke a non-const method (such as setX) on p, as it may (and in this case, certainly does) modify the object. 14.1.4 Plain Old Data C++ makes a distinction between classes (or structs) that are plain old data (POD) classes and classes that are not. At a high level, all POD types have direct C analogs —they are just sequences of fields in memory that you

could copy around freely. POD types require no special setup or destruction. You could allocate them with malloc, copy them with memcpy, and deallocate them with free. Unfortunately, discussing exactly what makes a class non-POD is quite complex, relies on concepts we have not introduced yet, and varies between C++03 and C++11. The simplest rule is that if you can write it in C, it is a POD class. If you cannot write it in C, it is probably not POD, with one significant exception: if you declare functions (a.k.a. methods) inside of a class or struct, they do not make the type non-POD (unless they are virtual functions, which we will learn about later). This last exception may seem quite surprising, as adding functions “inside” of a class is a significant feature of OOP. However, even though the functions are conceptually “inside the object,” they are actually not contained in the object in memory. Instead, the code for these functions is just placed with the rest of the code in memory and just takes the extra this parameter to tell which object it is currently operating on. The fact that the function is not actually inside the object means that the objects as they are in memory still have a direct C analog. That is, if we had a C++ class declaration of: 1 class MyClass { 2 public: 3 int x; 4 int y; 5 int getSum() const { return x + y; } 6 }; We could think of it as the C code: 1 typedef struct { 2 int x; 3 int y; 4 } MyClass; 5

6 int getSum (const MyClass * const this) { 7 return this->x + this->y; 8} The class in the C++ code and the struct in the C code would have the same layout in memory. That is, both of them would have the same size (sizeof(MyClass) would be the same whether we did the C++ version or the C version), and the offset of each field relative to the start of the object would be the same. So far, the only C++ feature that we have seen that can make a type non-POD is access restrictions (declaring fields private). Whether declaring any fields private, or mixing multiple visibilities (some private fields and some public fields) in a class makes it non-POD depends on whether you are using C++03 or C++11. Additionally, any class that has members of a non-POD type is itself non-POD (although it may have pointers to non-POD types, since the pointers themselves are all that is held in the object in memory, and they are POD). As we delve more into C++, we will learn more features that make types non-POD. Knowing whether a type is POD or not is important for knowing what you can and cannot do to it. With any non-POD type, you cannot work on the “raw” memory directly in a safe way, whether it is allocating, copying, or deallocating that memory. Instead, you have to use the C++ operators that know how to work with non-POD types properly. 14.1.5 Static Members Often we want the fields and methods of a class to “belong to” a specific instance of the class. In our BankAccount example, we want every BankAccount object we create to have a different balance field—the balance

of one account is a completely different “box” from the balance of any other account. Whenever we create a new BankAccount object, it should have a box inside of it for the balance. Likewise, when we deposit to a BankAccount (via the deposit method), it should affect the balance in the BankAccount object we are invoking deposit on (and no other). However, there are times when we want all instances of a class to share the same “box” for a particular field or to have a method that acts on no particular instance of that class. In our BankAccount example, we might want each BankAccount to have an account number that is uniquely assigned when the account is created. While each BankAccount’s particular account number should be “one box per instance” as we have seen so far, we also need a “box” shared by all BankAccounts to track the next account number to assign to a newly opened account. We want the next account number to be a static field of the BankAccount class. In this context, the keyword static means that there is one “box” shared by all instances of the BankAccount class, not one box per instance. We can modify our BankAccount class as follows: 1 class BankAccount { 2 private: 3 static unsigned long nextAccountNumber; 4 unsigned long accoutNumber; 5 double balance; 6 public: 7 unsigned long getAccountNumber() const 8 return accoutNumber; 9} 10 void deposit(double amount) { 11 balance += amount; 12 } 13 double withdraw(double desiredAmount) { 14 if (desiredAmount <= balance) { 15 balance -= desiredAmount;

16 return desiredAmount; 17 } 18 else { 19 double actualAmount = balance; 20 balance = 0; 21 return actualAmount; 22 } 23 } 24 double getBalance() const { 25 return balance; 26 } 27 void initAccount() { 28 accoutNumber = nextAccountNumber; 29 nextAccountNumber++; 30 balance = 0; //we will see a better way to 31 } 32 }; 33 34 unsigned long BankAccount::nextAccountNum There are a few things to notice about the declaration of the nextAccountNumber. First, inside the class declaration, we declare static unsigned long nextAccountNumber. Declaring this field as static requests that there not be one box per instance of the class. Methods inside the class can still access this one “shared” box (as seen in initAccount). However, in C++, this declaration does not actually create the “box”. Instead, we need another line of code outside of the class definition: 1 unsigned long BankAccount::nextAccountNumber = 0 This line of code actually creates the box and must be placed at the global scope—outside of any functions or classes. It is just like any other variable declaration, except that the name of the variable being declared looks a bit odd. The name of the variable, BankAccount::nextAccountNumber, specifies the nextAccountNumber “inside of” the BankAccount class. The

:: is the scope resolution operator, which allows us to specify a name inside of another named scope, such as a class. We will note that this statement executes before main begins execution—that is, the box is created and initialized before we begin our normal execution of code at the start of main. You can also write static methods in a class. These methods cannot access non-static members of the class because unlike non-static methods, they do not have a this pointer passed to them—they operate on no particular object. We are not going to have much use for static members in anything we do in this book. However, it useful to have seen the concept (especially if you go on to program in Java) and know what the term means, as it may appear in compiler errors (especially “non-static”). 14.1.6 Classes Can Contain Other Types In C++ (and many other OO language, classes can contain other types inside of them. Such a declaration can either be a typedef of an existing type or even the declaration of an entire other class (in which case, the resulting class is called an inner class). Like fields and methods, the current access specifier affects the visibility of the type declaration. For example, we could add some types to our BankAccount class: 1 class BankAccount { 2 public: 3 typedef double money_t; 4 private: 5 class Transaction { 6 public:

7 money_t amount; 8 timeval when; 9 }; 10 money_t balance; 11 Transaction * transactions; 12 //other stuff elided... 13 }; Line 3 makes money_t a typedef for double inside of BankAccount. This type declaration is public, so it can be referenced freely outside of the class; however, since the name is inside of the class, the scope resolution operator, (::) must be used—the type name would be written BankAccount::money_t. Inside the class, it can be referenced simply as money_t (as done when declaring the balance field in this example. This example also declares an inner class, Transaction, which is private. Code outside of the BankAccount class cannot make use of this type at all. The Transaction class has its own fields (and could have methods, and anything else a class can have) with their own visibility. You may wonder what happens when you have a private inner class (such as the Transaction class here) with public members (as this class has). Having a private class prevents code outside of the class from naming the type (that is, it cannot make use of the type name BankAccount::Transaction). Such a restriction typically means that we design our code such that the private inner class never “escapes” the outer class—that is, we never return instances of the class (or pointers to them) to the code in the outside world, and have no public fields whose type is the inner class. If we do not let instances of this private class escape, then there is nothing complex to thinking about how the access restrictions work: code in the outer class can access members of the inner class according to their visibility modifiers, and code outside of

the outer class cannot even “see” the inner class at all. If we do allow the inner class to escape the outer class, then even though that code cannot name the type, it can still access public fields in the object. Unlike most things “inside” of a class, methods of an inner class do not have direct access to non-static members of the outer class. This restriction is not an issue of access restrictions, but rather that the methods inside the inner class have a this pointer that points at the object that is an instance of that inner class (e.g., it is a pointer to a Transaction), and does not have a pointer to the outer-class instance (e.g., BankAccount) that created them (in fact, there might not be one). If we want to let the inner class reference the outer class, we can do so easily by having a field in the inner class that is a pointer to the outer class type and initializing it to point at the appropriate outer-class instance. We can then access fields and invoke methods through that pointer. 14.1.7 The Basics of Good OO Design Object-oriented programming is a nice tool to help with programming in the large; however, as with most tools, it must be used properly to have benefits. While good OO design is quite a large topic (as we mention in Chapter 34, an aspiring professional programmer should take a software engineering course), we cover some key principles here to help guide you as you begin to build software using objects. Classes are nouns. Methods are verbs. When you make a class, its name should be a noun. When you make instances of that class, you are making “things,” which correspond naturally to nouns. By contrast, methods should have verb names—they do things. If

you find yourself naming a class with a verb, you are likely describing something that should be a method within a particular class (maybe an existing class or maybe a new one). Keep classes small and to their purpose. As a class should be named for a noun, its implementation should reflect that noun. If there are subpieces that can logically be split out into their own class, doing so is often a good idea—much like we often want to abstract out tasks into functions as we write other functions. Be as general as you can be, but no more. As we will see later, C++ provides a variety of ways to make your classes general. For example, we will see in Chapter 17 how we can make classes and methods that operate on any type of data, as long as the operations are the same regardless of type. When designing a class, if you have a choice between making the class more general (whether in terms of types, having more parameters versus hard coding, or other ways to generalize your code), or limiting yourself to what you need specifically at this moment, it is typically better to write the more general class. Such an approach saves you from reimplementing the class to accommodate other types or variations later. Of course, if making the class more general presents significant difficulties, you may be trying to make it too generalized, which can be even worse. Avoid “Manager” classes.

One common hallmark of poor OO design is classes with “Manager” in their name. For example, if one is writing a game, and writes a GameManager class, this class reflects a poor design choice. Here, the programmer has basically said “I have a bunch of stuff I need to do but cannot come up with a good OO design, so I will throw it all into a class that manages everything.” Here, the programmer could improve his design by separating out the functionality of this manager into logical units that map onto nouns—for example, we might have a Timer class (to handle events that happen after a certain amount of time), a Set class (from which we make a set of timers to represent all the active timers), a GameBoard class (to represent the board), and so on. Basically, unless you are writing a class to represent an employee who oversees other employees, you should never name a class with manager in its name.4 14.2 References In C, we can refer to a “box” either directly by using its name or by dereferencing pointers that point at its box. C++ provides another way to refer to a box: via a reference. A reference is similar to a pointer in that it provides access to a “box” through a level of indirection; however, there are many differences between references and pointers. A reference is intended to conceptually be “another name for a box.” Reference types are declared with an & in the same way that pointers are declared with a * (e.g., int & x = y; declares a reference x, which has type “int reference” and feferences y—it is conceptually another name for y’s box).

The first difference between references and pointers is that once a reference is initialized (to refer to some box), it cannot be changed to refer to a different box. By contrast, pointers can have what they point at changed any time (unless they are declared with appropriate const modifiers to prevent such modifications). A consequence of this rule is that any type that has a member whose type is a reference is not a POD type—because the reference requires “special” initialization (you cannot just assign to it later). The second difference is that references are automatically dereferenced, whereas pointers must be explicitly dereferenced. The third difference is that a reference must be initialized when it is declared. The initialization is treated specially—it sets what the reference refers to—while any other use of the reference implicitly refers to whatever is referenced. The fourth difference, which is a corollary of these first two differences, is that we cannot have NULL references. The fifth difference is that we cannot have a “reference to a reference” (int &&x is not a reference to a reference to an int5 ). Similarly, we cannot have a pointer to a reference (so int&* x is not legal); however, we can have a reference to a pointer (so int *&x is legal). The sixth difference is that we cannot perform “reference arithmetic,” even though we can perform pointer arithmetic. For the most part, we can think of the behavior of references in terms of imagining a translation of the code with references to equivalent code with pointers. In the

code below, the first piece of code shows two functions that use references (they do not really accomplish useful tasks nor use the references in a useful way—they are just simple functions for the purposes of example). The second shows code with equivalent behavior that uses pointers instead of references. Code with References 1 int f(int & x, int y) { 2 int z = x + y; 3 x = z; 4 return z - 2; 5} 6 int g(int x) { 7 int z = f (x, 3); 8 int & r = z; 9 r++; 10 return z * x; 11 } Equivalent Code With Pointers 1 int f(int * const x, int y) { 2 int z = (*x) + y; 3 (*x) = z; 4 return z - 2; 5} 6 int g(int x) { 7 int z = f (&x, 3); 8 int * const r = &z; 9 (*r)++; 10 return z * x; 11 } More generally, we can (for the most part) translate reference-based code to pointer-based according to the following rules. Declaration If we have a declaration of a variable or parameter of type T & (where T is some type), we can translate it to a declaration of a pointer of type T * const (that is, a pointer to a T