All of Programming [ PART I ]

Video 15.9 revisits the earlier example with our updated Polygon class that contains a copy constructor. 15.3.2 Assignment Operator The other form of copying that can occur is copying during assignment. Unlike copying during initialization, copying during an assignment changes the value of an object that already exists (and is already initialized) to be a copy of another object. Copying by assignment makes use of the assignment operator, operator=. Classes may overload the assignment operator to specify how their objects should be copied during assignment. 1 class Polygon { 2 Point * points; 3 size_t numPoints; 4 public: 5 Polygon(size_t n) : points(new Point[n]), numPo 6 //copy constructor: makes a deep copy 7 Polygon(const Polygon & rhs) : points(new Point 8 numPoints(rhs.nu 9 for (size_t i = 0; i < numPoints; i++) { 10 points[i] = rhs.points[i]; 11 } 12 } 13 Polygon & operator=(const Polygon & rhs) { 14 if (this != &rhs) { 15 Point * temp = new Point[rhs.numPoints]; 16 for (size_t i = 0; i < rhs.numPoints; i++) 17 temp[i] = rhs.points[i]; 18 } 19 delete[] points; 20 numPoints = rhs.numPoints; 21 points = temp; 22 } 23 return *this; 24 } 25 ~Polygon() { 26 delete[] points; 27 } 28 };

Like the copy constructor, the copy assignment operator takes a constant6 reference7 to its own type. We could overload the assignment operator on other types. However, we should only do so if it makes sense to do so. For example, if we were writing a class for arbitrary size integers (typically called “BigInt” or “BigNum”), we might overload the assignment operator to take a normal int. Such an overloading would make sense (as it allows us to write myNum = 3;); however, it is not the copy assignment operator that we are concerned with here. The copy assignment operator also has rather similar internal behavior to the copy constructor (which makes sense, as both specify how to copy the object). However, there are some important distinctions between the two. First, the assignment operator returns a value. Specifically, it returns a reference to this object (as do most operators that modify the current object). Remember that when we initialize a reference (in this case, the return value) from an object, we implicitly take the object’s address to get the underlying pointer. Therefore, the pointer that is the value of the reference returned is &*this, which is just this. The second difference between the assignment operator and the copy constructor is that the operator begins by checking if this != &rhs. That is, if the object being assigned to is distinct from the object copied. As a general rule, we should check for this condition in writing an assignment operator, as we might otherwise run into problems (we may delete a pointer in this object, then use it dangling in rhs). Note that we perform this check by comparing pointers (i.e., we do this != &rhs), not values (i.e., do not do *this != &rhs). Comparing pointers tells us what we want to know—are this and rhs referencing exactly the same object in memory (also, comparing pointers is one or two instructions, while calling the !=

operator may involve a complex comparison via an overloaded != operator). The third difference relative to the copy constructor is that the assignment operator must clean up the existing object before we assign the copied values to it. In the copy constructor, there is nothing to cleanup at the start: the object is uninitialized. However, in the assignment operator, we are overwriting an existing object with a copy. Much like the copy constructor, if the user does not write an assignment operator, one is automatically provided. The automatically provided assignment operator generally looks like this: 1 class SomeClass { 2 Type1 field1; 3 Type2 field2; 4 ... 5 TypeN fieldN; 6 public: 7 //this is what the automatically provided assignment ope 8 SomeClass & operator=(const SomeClass & rhs) { 9 field1 = rhs.field1; 10 field2 = rhs.field2; 11 ... 12 fieldN = rhs.fieldN; 13 return *this; 14 } 15 }; The automatically provided assignment operator does not check for self-assignment before copying the fields. All it does is copy each field in the class (using the appropriate assignment operator for each field’s type) then return a reference to the object that was assigned to. If you want any other behavior, you must define the operator yourself. The provided assignment operator is considered “trivial” under similar circumstances to when

the copy constructor is considered trivial (it is automatically provided, each field in the class has a trivial assignment operator, and some other conditions related to topics we will learn about later). We might be tempted to write our assignment operator in a slightly simpler (although, as we shall see, less correct) fashion: 1 Polygon & operator=(const Polygon & rhs) { 2 if (this != &rhs) { 3 delete[] points; 4 points = new Point[rhs.numPoints]; 5 for (size_t i = 0; i < rhs.numPoints; i++) { 6 points[i] = rhs.points[i]; 7} 8 numPoints = rhs.numPoints; 9} 10 return *this; 11 } The two implementations are fairly similar; however, the second one deletes the existing data first to avoid the use of a temporary pointer. It then allocates the memory, assigning the result of new directly to this->points, copies the values from the array, then initializes numPoints. This second implementation will work just fine under most conditions; however, it is technically less correct because of its behavior if new fails (e.g., no more memory is available). We cannot discuss the exact behavior that occurs when new fails until Chapter 19, when we will learn about exceptions. However, the important distinction is that if new fails, the first implementation of the assignment operator leaves the object in a valid state, but the second implementation leaves the object with a dangling pointer. We will discuss these issues in much more detail in Chapter 19.

15.3.3 Executing Code with Copying C++’s copy constructors and assignment operators change the rules of executing code by hand. Whenever you are going to copy an object, you must first determine whether to use the copy constructor or assignment operator and then determine what that constructor/operator does (which may be the automatically provided constructor/operator discussed previously). The first decision—whether to use the copy constructor or assignment operator—is strictly a matter of whether you are initializing an object that you are newly creating or changing the values in an existing object. A seemingly appealing approach would be to just look for the equals sign, which signifies assignment. However, there is a problem with this approach— sometimes the equals sign can be used as part of initialization of a new object. C++ consider the following to be initialization, not assignment: 1 MyClass something = anotherThing; As this statement is initialization, many programmers consider it preferable to write the following instead: 1 MyClass something(anotherThing); The two have the same exact behavior (the copy constructor will be used if anotherThing is a MyClass object). However, the second way of writing this piece of code avoids confusing the inexperienced C++ programmer with respect to what happens. Once you have determined whether you are using the copy constructor or the assignment operator, you must determine if that constructor/operator is trivial or not. Recall that (for now at least) the constructor/operator

is trivial if it was automatically provided by the compiler, and all constructors/operators that it makes use of are also trivial. If the constructor/operator is trivial, then you can simply copy the values directly as you have been doing in C since Chapter 2. If the constructor/operator is non-trivial, then you must call it like a function (passing in the object being initialized/assigned to as this) and step through its code line-by-line to execute its effects. Video 15.10: Executing code with an overloaded copy assignment operator. 15.3.4 Rule of Three If you have fully internalized the lessons of this chapter, you may have noticed that there seems to be a relationship between needing a destructor, needing a copy constructor, and needing an assignment operator in a class. If a class needs custom behavior to destroy an object, then that class needs custom behavior to copy the object—performing a deep copy, so that the destruction of an object does not leave dangling pointers in other objects. Likewise, if a class needs special copying behavior for initialization (the copy constructor), that class needs special copying behavior for assignment, and vice versa. Completing the relationship, if a class needs special copying behavior, it almost certainly has resources that need to be cleaned up by a destructor. Not only is this observation true, it is important enough to have a name. This principle is called the rule of three. The rule of three states that if you write a destructor, copy constructor, or assignment operator in a class, you must write all three of them.

15.4 Unnamed Temporaries While we are discussing object creation, it is useful to discuss the concept of unnamed temporaries—values that are created as the result of an expression but not given a name (i.e., no variable is declared for them, so they do not have a name). We have actually seen unnamed temporaries in practice in C; however, there is much less to say about them. For example, when we compute 4 + 3 * 5, the computation of 3 * 5 occurs first, producing 15. The value 15 is an unnamed temporary—it is the result of an expression that is not given a name. The program must store this value somewhere to be able to perform the computation 4 + 15. However, that storage is quite short-lived. As soon as the program computes 4 + 15, the value of this temporary is no longer needed and may be discarded. The compiler orchestrates all of this behind the scenes. In C, there is not much interesting about unnamed temporaries. They exist, but we do not need to think carefully about them when executing code by hand. In the example above, we would likely perform the math in our heads without even writing down the 15 anywhere— that is fine, as long as we do it correctly. If we had a longer-lived temporary (such as if we did f(3) + g(4) and had to remember the result of f(3) while executing g(4)), we might write it down over the expression that generated it. We did this before without explicitly talking about it because it is fairly simple. In C++, however, we must be more careful about unnamed temporaries when they are objects, as they can have more complex behavior. Like any other objects, unnamed temporaries are initialized by constructors and destroyed by destructors, which we need to account for when we consider the behavior of the program. For

example, if we write a + b * c, and a, b, and c are objects (whose types have overloaded the + and * operators), then the result of b * c is an unnamed temporary with an object type. The creation and destruction of this object may be nontrivial, thus we must account for their effects in executing the code. There are a variety of ways that unnamed temporaries are created. The simplest way is to declare an object with no name by writing the class name, followed by parentheses and the initializers of the object. For example: 1 MyClass(42); //create an unnamed object Such a statement will allocate space for an object of type MyClass in the current stack frame. Unlike most objects we create, the “box” will not have any name. The next effect of the statement will be to initialize it by passing 42 to its constructor. The this argument of the constructor will be an arrow pointing at the unnamed box. In this particular example, the object will then be immediately destroyed. The destructor will be invoked to clean up the object (again, this will point at the unnamed box), and then the temporarily allocated storage for it will be deallocated, removing the unnamed box from the current stack frame. More generally, an unnamed temporary object is deallocated at the end of the full expression (that is, an expression that is not a piece of a larger expression) containing its creation. For example, suppose MyClass overloads the + and * operators (to also return MyClass objects), and consider the following code: 1 x = MyClass(42) + MyClass(17) * MyClass(3);

This fragment of code creates five unnamed temporaries (MyClass(42), MyClass(17), MyClass(3), the result of the multiplication, and the result of the addition)8. These temporaries are destroyed (in reverse order of their creation) at the end of the entire assignment expression—that is, after the result of the addition is assigned to x. You may note that we wrote assignment expression—recall that in C and C++ “lvalue = expression” is itself an expression, thus the entire full expression here is 1 x = MyClass(42) + MyClass(17) * MyClass(3) This rule is another great example of a rule where remembering its details are not that important, as long as you write code where it does not matter. If you do not care about the precise places where these temporaries are destroyed (just the fact that they are destroyed properly), you do not need to remember the specific details. However, if you write code where the specifics of object destruction (or creation order) matter, you should fully understand the rules. 15.4.1 Parameter Passing Unnamed temporaries can be useful in passing parameters to functions. For example, suppose we have a function that takes a MyClass object: 1 int someFunction(MyClass something) { ... } We can pass an unnamed temporary as a parameter to the function: 1 someFunction(MyClass(42)); This call is legal and constructs an unnamed temporary (as we discussed before), copies that

unnamed temporary object into the stack frame for someFunction, and then destroys the temporary after someFunction returns (as the full expression containing its creation ends there). We could instead write: 1 MyClass temp(42); 2 someFunction(temp); However, there is a subtle difference. In the first version (where we construct an unnamed temporary), the compiler is allowed to optimize away the copy. That is, rather than constructing an unnamed temporary and copying it into someFunction’s frame, the compiler is allowed to create the object directly in someFunction’s frame to avoid the extra copy operation. The object that it creates is still destroyed at the proper time (after evaluation of the full expression where it was created). The alert reader may be a bit perplexed as to how this destruction happens, as we have shown the called function’s frame being destroyed, along with all objects in it before execution returns to the caller. However, the called function cannot be responsible for destroying these objects, as execution must return to the caller first. Technically speaking, most implementations will have the called function destroy everything except the parameters, and the caller destroy the parameters. However, this level of detail introduces complexities that are not significant in most cases (anything we have done or will do in this book). If you write code where this level of detail of destruction order matters then (a) you should be an expert in not only these details, but also what precisely the C++ standard does and does not guarantee, as well as what your compiler (and any you might port your code to) does exactly and (b) you should have a really good reason for writing such code.

We will further note that it is generally preferable to have functions take a const reference rather than a copy of an object. That is, we probably should write someFunction like this instead: 1 int someFunction(const MyClass & something) { .. Now, no copying is involved in any case. As the reference is a const reference, we can still pass an unnamed temporary to it. The compiler will create a “box” for the unnamed temporary and pass the address of that box as the pointer that is the reference. If the reference is non-const, then we would not be able to pass an unnamed temporary, as it is not an lvalue. 15.4.2 Return Values Unnamed temporaries are also involved in returning a value from a function. In our earlier MyClass(42) + MyClass(17) * MyClass(3) example, the result of the multiplication (which is an unnamed temporary) comes from the return value of the multiplication operator (which is a function). There are, however, two ways in which the creation of this unnamed temporary can happen. The most intuitive approach from the perspective of the rules that we have learned so far is that the function (in this case, multiplication operator) creates an object, and that object is explicitly copied to initialize the unnamed temporary. This copying would make use of the copy constructor (as the unnamed temporary is a newly created object), after which the local object inside the function would be destroyed.

However, that approach is inefficient from a perspective of requiring an explicit copy. C++ allows the compiler to elide the copy, even if the copy constructor has noticeable effects. If the compiler elides the copy, then it arranges for the result to be directly initialized from within the function. This optimization is called the return value optimization. If you are executing code by hand, you can typically choose whether to assume the compiler performs return value optimization or not. For most code, the optimization does not change the correctness or behavior of the code (although it is permitted to perform this optimization even if it does change the behavior of the code). If you are experiencing strange problems, you might execute the code both ways to see if there is a difference in behavior. If you are writing code where the presence of return value optimization poses problems, you are almost certainly doing something wrong. If you have a good reason for whatever you are doing, you should dynamically allocate the object with new, return a pointer, then explicitly delete the object when appropriate. 15.4.3 Implicit Conversions We just saw that we can pass an unnamed temporary to someFunction like this: 1 int someFunction(const MyClass & something) { .. 2 ... 3 ... 4 someFunction(MyClass(42)); However, what is perhaps more surprising is that we can write the call to someFunction like this (even if someFunction is not overloaded to take an int):

1 someFunction(42); This behavior may seem quite shocking, as 42 has type int, and someFunction requires an argument of type MyClass. The fact that the C++ compiler accepts this function call makes it appear that the rules of type checking as you have come to know them are being completely disregarded. In actuality, this behavior is a broad generalization of behavior we have been familiar with since Section 3.4.1. Recall that we discussed what happens if you try to add an int and a double. The int is implicitly converted to a double before the arithmetic happens. In C++, any constructor that takes one argument is considered as a way to implicitly convert from its argument type to the type of the class it resides in, unless that constructor is declared explicit. In the case of this particular example, this means that the C++ compiler considers MyClass’s constructor, which takes an int, as a valid way to implicitly convert the int (42), which we have passed as an argument to an object of type MyClass, which is required for the function call. This implicit conversion creates an unnamed temporary object according to all the rules that we just discussed. The compiler is only allowed to apply this rule once per initialization. That is, if class A has a constructor that takes a B, and B has a constructor that takes a C, then we may not pass a C where an A is required and expect the compiler to make a temporary B from which it then can then make a temporary A. As a general rule, you should declare all of your single-argument constructors except your copy constructors as explicit, such as: 1 class MyClass {

2 //other stuff here... 3 public: 4 explicit MyClass(int x) : someField(x) { ... } 5 MyClass(const MyClass & rhs) : someField(rhs.so 6 //other stuff here... 7 }; In general, the fact that the compiler can insert “what it thinks you mean” in place of “what you said” allows for mistakes to slide by unnoticed. If you meant to construct a temporary of type MyClass, you should have written that. Remember the principle that we have mentioned several times before: you want the compiler to catch as many of your mistakes as possible. Having implicit conversions available reduces the compiler’s ability to help you in this fashion—rather than telling you that you passed the wrong parameter type, it may convert it to a legal type, which may not even be the one you wanted. Another danger lurks in abusing implicit conversions, especially combined with function overloading. You may write code that works perfectly fine right now and relies on an implicit conversion. However, later, another programmer may add an overloading of the function you are calling that is a better choice (does not require implicit conversion) but does something else. As a simple example, imagine if we had an Image class and a draw function, which draws an Image on the screen at specified coordinates. The Image class has a constructor that takes a string (C++ introduces a string class, but we will not learn about that until Chapter 16, so we will use const char *s for now): 1 class Image { 2 public: 3 //should be explicit. 4 //but we omit that for the purpose of the example 5 Image(const char * filename) { ... } 6 };

1 void draw(int x, int y, const Image & image) { . Now, suppose that since the Image constructor is not explicit, the code makes use of the implicit conversion: 1 draw(xpos, ypos, \"someImage.png\"); The compiler sees that it can use the constructor of Image, which takes a single const char * argument to implicitly convert, and the code compiles just fine. Let us suppose that this code works exactly as intended for the moment. The programmer tests the code and all is well. In fact, perhaps, the programmer makes use (or should we say “abuses”) these implicit conversions in many other places in the program. All are perfectly legal, and may well work just fine (for now). Now suppose that at some later date, another programmer decides to write a function to draw a string of text on the screen. That is, it takes a string and prints the image of those letters onto the screen at a particular set of coordinates: 1 void draw(int x, int y, const char * message) { The programmer adds this code then recompiles the program. Now, the calls that abused the implicit conversion: draw(xpos, ypos, \"someImage.png\"); actually call the newly added draw function, as it is a better match (no conversions are required)! Instead of reading the file and drawing the image, they draw the file name on the screen. The programmer testing the new draw function will be quite surprised by the new behavior of the program and need to invest some debugging effort to find out what is happening. After the problem is identified, the programmer will need to go in and add explicit

conversions everywhere that the implicit conversion was abused. Declaring your constructor with explicit prevents the compiler from making use of it unless you explicitly create the unnamed temporary, like this: 1 draw(xpos, ypos, Image(\"someImage.png\")); As we just mentioned, you should generally declare all single-argument constructors to be explicit, except for the copy constructor. The copy constructor should never be declared as explicit. It cannot be used for an implicit conversion (it would only convert from one type to the same type) and must be used in a variety of implicit circumstances, such as copying parameters into a callee’s frame and copying the return value out of a function. 15.5 Practice Exercises Selected questions have links to answers in the back of the book. • Question 15.1 : What is a constructor? How are they declared? Why are they useful? • Question 15.2 : If you write a constructor in a class, can that class be POD? Why or why not? • Question 15.3 : Why can you not use malloc with non-POD types? • Question 15.4 : What is an initializer list, and why should you use them in your constructors? • Question 15.5 : What is a destructor? How are they named? Why are they useful? When are they invoked? • Question 15.6 : Suppose that C is a class, and c1 is previously declared to be of type C (and

initialized). If I write C c2 = c1;, which gets used: the copy constructor or the assignment operator? • Question 15.7 : What is the output when the following code is run? 1 #include <cstdio> 2 #include <cstdlib> 3 4 class Example { 5 private: 6 int data; 7 public: 8 Example() : data(0) { 9 printf(\"Example default constru 10 } 11 Example(int x) : data(x) { 12 printf(\"Example constructor (%d 13 } 14 Example(const Example & e) : data 15 printf(\"Example copy constructo 16 } 17 Example & operator=(const Example 18 data = rhs.data; 19 printf(\"Example assign operator 20 return *this; 21 } 22 ~Example() { 23 printf(\"Example destructor [wit 24 } 25 void add(int x) { 26 data += x; 27 } 28 }; 29 30 void f(Example & a, Example b) { 31 printf(\"Inside f\\n\"); 32 a.add(10); 33 b.add(20); 34 } 35 36 int main(void) { 37 printf(\"e1:\\n\"); 38 Example e1; 39 printf(\"e2:\\n\"); 40 Example e2(4); 41 printf(\"e3:\\n\"); 42 Example e3 = e2;

43 e3.add(5); 44 printf(\"e1 = e2:\\n\"); 45 e1 = e2; 46 printf(\"f(e1,e2):\\n\"); 47 f(e1, e2); 48 printf(\"back in main\\n\"); 49 return EXIT_SUCCESS; 50 } (Note that there is really no need to overload the copy constructor nor assignment operator here, except to have them print messages so you can check your understanding of their behavior). • Question 15.8 : What is the rule of three? • Question 15.9 : Write an IntArray class with the following behaviors: – A default constructor, which initializes the array to an empty (zero-element) array. – A constructor that takes a size_t, which initializes the array to have the passed-in number of elements and initializes each element to 0. Recall that size_t is an unsigned int type that is appropriate for the size of an array. – A copy constructor, which makes a deep copy of the IntArray. – A destructor, which properly frees the memory associated with the IntArray. – A copy assignment operator, which makes a deep copy of the assigned IntArray (and frees up any resources previously held by the assigned-to IntArray, which are no longer needed). – An overloaded int & operator[] (size_t index), which returns a reference to the specified item of the array.

– An overloaded const int & operator[] (size_t index) const, which returns a const reference to the specified item of the array. – A size_t size() const function, which returns the size of the array. You should also write a main to test your code extensively. • Question 15.10 : Write a program that demonstrates the automatically provided assignment operator (for a class that does not explicitly define one) does not check for self assignment. Your program does not need to accomplish any particular “useful” task but should convince anyone who sees its code and output of the behavior of this rule. 14 Transition to C++16 Strings and IO Revisited Generated on Thu Jun 27 15:08:37 2019 by L T XML

II C++15 Object Creation and Destruction17 Templates

Chapter 16 Strings and IO Revisited C++ introduces new classes for strings and for performing IO. Although the C approaches are still valid, most C++ programmers use the C++-specific approaches. The advantage of these new approaches is that they provide a more object-oriented approach than their C counterparts. However, as with most things, there are tradeoffs. 16.1 Strings In C, a string is simply a sequence of characters, terminated by the special null-terminator character (’\\0’). Although this implementation of strings is sufficient to define and manipulate them, it is not at all in line with the object-oriented paradigm of C++. Instead, C++ provides a string class (std::string, for which you need to #include <string>). Of course, you can still define and manipulate C-style strings via a char * whenever it is appropriate (and in fact, argv is still a char ** just as it is in C). The string class encapsulates the sequence of bytes that form a string into an object that provides a variety of methods and operators to operate on that type. For example, strings have a length() method, which tells how many characters are in the string. There are also operators such as +=, which appends one string to the end of another, and [], which indexes into the string, returning a reference to the requested character. As the [] operator returns a char & (when applied to a non-const

string—otherwise a const char &, it can be used to modify the contents of a string (e.g., myString[0] = ’a’;). The string class also provides a variety of constructors, including one that takes a const char * (i.e., a C-style string) as an argument. This constructor allows creation of C++ strings from C strings, including string literals (which still retain the same const char * type in C++). For example, you can write std::string s(\"Hello World\"); to create a C++ string object (locally in the current frame) and initialize it with the (C) string literal \"Hello World\". For full reference on C++’s string, consult http://www.cplusplus.com/reference/string/string/. 16.1.1 Cautionary Example Our discussion of C++’s strings provides an excellent opportunity for a cautionary example. Consider the following C++ code to reverse a string, using recursion: 1 #include <string> 2 //This code is terribly inefficient 3 std::string reverse(std::string s, std::s 4 if (s.length() == 0) { 5 return ans; 6} 7 return reverse(s.substr(1), s[0] + ans) 8} 9 //Note that the next function is not recursive. 10 //It calls the other (overloaded) reverse functio 11 std::string reverse(std::string s) { 12 return reverse(s, \"\"); 13 } At first glance, this code appears to be a reasonable C++ implementation of code to reverse a string using recursion. In fact, a naïve examination of this code would

lead one to believe that this implementation is tail recursion (recall from Chapter 7 that a tail recursive function immediately returns the recursive result with no further computation). However, this function is not actually tail recursive, so the compiler cannot apply tail call optimization to it. If you fully understood and internalized the information from Chapter 15, you will realize why this function is not tail recursive—the frames for reverse have four string objects (s, ans, as well as temporary objects for s.substr(1) and s[0] + ans), which have nontrivial destructors. Thus, these objects must be destructed after the recursive call of reverse returns. However, being head recursive is not the only inefficiency in this function (if it were, the impact would be fairly minor). The larger inefficiency arises from the fact that we are creating many new objects and performing significant copying. When we call s.substr(1), we are creating a new local string object, which has all but the first character of s and almost certainly involves copying that data into the new object. We also create a new string object that is the concatenation of s[0] and ans, which also requires copying characters from those strings into the newly created object. We then copy the temporary objects into the parameters of the recursive call! You may think “ok, so we make a few copies—how big of a deal can that be?” If we compare to a more efficient implementation (which actually is tail recursive and eliminates the extra copying): 1 #include <string> 2 //This code is much more efficient! 3 std::string reverse(const std::string & s 4 if (ind == s.length()) { 5 return ans; 6} 7 ans[ind] = s[s.length() - ind - 1]; 8 return reverse(s, ans, ind + 1);

9} 10 //Note that the next function is not recursive. 11 //It calls the other (overloaded) reverse functio 12 std::string reverse(std::string s) { 13 std::string ans(s.length(), ’\\0’); 14 return reverse(s, ans, 0); 15 } We find that this more efficient implementation is about 2000x faster (yes, two thousand times), when reversing large strings. On the computer we timed these implementations on, the first reversed a 10,000-character string in 42,500 microseconds. The second implementation reversed the same 10,000-character string in 20 microseconds. The first implementation could not reverse 100,000 character strings because the stack overflowed (the head recursive functions created more frames than there were space for on the stack). We note that we can also implement the reverse function iteratively, which has indistinguishable performance from the efficient recursive implementation: 1 #include <string> 2 3 std::string reverse(std::string s) { 4 std::string ans(s.length(), ’\\0’); 5 for (size_t i = 0; i < s.length(); i++) 6 ans[i] = s[s.length() - 1 - i]; 7} 8 return ans; 9} We present this cautionary tale not for the specific details of implementing string reverse, but to underscore the importance of understanding the implications of all of the code you write. In C++, it is very easy to write code that copies values excessively and creates/destroy many temporary objects. Such code can be painfully slow. While we are not focusing on performance optimization in

this book, we note that writing code multiple orders of magnitude slower than it should be is often unacceptable. You should think carefully about what exactly your C++ code does and whether it really needs to make copies or create new temporary objects. Observe that by learning exactly what C++ code means and how to execute it by hand, you have exactly the tools required to think through these concerns as you write code. When you find yourself having such problems, consider ways to pass parameters by reference (or const reference) instead of value, as well as where temporary objects are created, and how they might be eliminated. 16.2 Output In C, we used FILE *s for output. These represented an open file, including stdout and stderr. We then used functions such as fprintf or printf (which is like fprintf but always writes to stdout) to print output. These two functions provided format conversions (%d, %s, etc) to allow us to print the values of expressions of various types. If we wanted to write a function to print a complex data structure, we would write it to take a const pointer to that structure as a parameter. The C-style mechanisms for printing are great for C; however, they do not align with the object-oriented principles C++ strives for. The C approach requires us to write a function that takes in the data to be printed. An OO approach lets a class define how to print itself with a method encapsulated inside of it. Reconciling such a design goal with the way printf is designed is a bit tricky. Instead, the designers of C++ decided to leverage operator overloading to devise an entirely different style of printing anything. In C++, the fundamental type for

output operations is a std::ostream, and the << operator is overloaded to work with it as the left-hand operand with a variety of possible types for its right-hand operand. When using the << operator to work with std::ostreams, it is called the “stream insertion operator” (otherwise, it is typically called the “left shift operator,” as it performs bit shift left for integers). Instead of using stdout (which is a FILE *), C++ introduces std::cout, which is a std::ostream (likewise, there is std::cerr, which is analogous to stderr). To see this in action, let us start by rewriting the “Hello World” program in C++: 1 #include <iostream> 2 #include <cstdlib> 3 4 int main(void) { 5 std::cout << \"Hello World\\n\"; 6 return EXIT_SUCCESS; 7} Here, we #include <iostream> for the C++ stream library, including std::cout, the std::ostream type, and the built-in overloadings of <<. We #include <cstdlib> for the definition of EXIT_SUCCESS. Inside of main, we use the stream insertion operator to print the string \"Hello World\\n\" to std::cout. The << operator is overloaded to allow its use with a variety of built-in types as its right operand. For example, we might write the following code: 1 #include <iostream> 2 #include <cstdlib> 3 4 int main(void) { 5 for (int i = 0; i < 10; i++) { 6 std::cout << \"i = \" << i << \"\\n\"; 7 std::cout << \"and i / (i + 1) = \" << 8}

9 return EXIT_SUCCESS; 10 } This code has two C++-style print statements. The first, on line 6, prints the literal string \"i = \" then prints the decimal (base 10) representation of the value of integer i, then the literal string \"\\n\". That is, it behaves basically like printf(\"i = %d\\n\", i). Similarly, the next line behaves like printf(\"and i / (i + 1) = %f\\n\", i / (double)(i + 1)) would in C. Note that while C’s printf requires us to explicitly write format specifiers (such as %d or %f), C++’s output streams do not. Instead, the C++ << is overloaded on multiple types. The << operator applied to an ostream and an int is a different function from the << operator applied to an ostream and a double. 16.2.1 Return Type of Stream Insertion A natural question from the previous example is “How does it work to have multiple <<s in a single statement?” Each << operator evaluates to a value, which in this case (and by convention, in general for stream operators) is its left operand. The fact that the operator evaluates to the stream means that std::cout << \"i = \" evaluates to std::cout (after printing the string \"i = \"), so the next << operator again has std::cout as its left operand. To make this concept a bit more concrete, we could imagine the implementation of << with int as the right operand type as: 1 std::ostream & operator<<(std::ostream & 2 char asString[16]; //decimal representation 3 snprintf(asString, 16, \"%d\", num); 4 stream.write(asString, strlen(asString) 5 return stream; 6}

That is, we might convert the integer to a sequence of characters then write those characters to the underlying ostream (the write method of an ostream takes an array of characters and a count of how many characters to write then writes them to the stream). After we write the data to the stream, we then return the original stream as the return result of the operator, which is what it evaluates to in the expression in which it was used. This convention is important to remember if you overload the << for your own types. If you make the overloaded operator return the ostream & that was passed in as its left operand, your << will be usable in the “normal” way—that is, you can chain multiple of your << operators and/or mix them with other overloadings in a single statement. If you make your << return void (as one might naïvely do), you will not be able to chain them together. 16.2.2 Writing Stream Insertion for Your Own Classes In an ideal world, we would write the overloading of the << operator inside of a class that we were writing. Such a design would fit with the OO design principle of encapsulation: how we print the class would be contained inside of it. However, writing it inside of the class would require the object being printed to be the left operand instead of the right—for operators that are members of classes, the left operand is this. Instead, we must write a method outside of the class that looks like this: 1 std::ostream & operator<<(std::ostream & stream, 2 //whatever it takes to print things (elided)... 3 return stream; 4}

Besides design idealism, this approach presents a pragmatic difficulty: our << operator is now outside the class but may require access to the private internals of the class to print out an instance. That is, we may wish for our printing method to have access to fields and methods of our class that are not exposed in the public interface (especially if we want to use the << operator to print objects for debugging). C++ resolves this conundrum by allowing a class to declare functions or class as its friend. When a class declares a function or a class as its friend, that function or class is allowed access to the private elements of the declaring class. The friend declaration is placed inside of the class wishing to grant access to its private members: 1 class MyClass { 2 //declarations of fields, methods, etc. 3 friend std::ostream & operator<<(std::ostream 4 const MyClass 5 }; Observe that for functions, we declare the friendship by writing the entire prototype of the function. As overloaded functions are different from each other, a function with the same name but different parameter types as a friend would not itself be a friend (unless also declared as such explicitly). Friendship declarations are a feature that should be used quite rarely. Declaring something as a friend inherently violates the core principles of OO design: it lets something outside of the class alter its private internal state. Using it for operators that are overloaded and are, in principle, part of the class but are just declared outside of the class due to the ordering of the parameters is a legitimate use of friend. Except for that use, you can

probably avoid the use of friend in any C++ program you write and not have any problems. 16.2.3 Object Orientation of This Approach C++ adopts this approach (in favor of C’s printf) as it presents a more object-oriented way to handle IO operations. By using objects, the underlying IO functionality is encapsulated into a class—the << and >> operators ask the stream object to perform output and input (respectively) with their right operands as arguments. While this may seem like a subtle distinction, it has some practical uses. In Section 16.4, we will see that we can have streams that read/write from/to things that are not files (such as strings). We could then write code that prints to any stream (whether that stream actually writes to a file, builds up a string, or does something else) and not worry about what kind of stream will be passed in. We will see in Section 18.4 how we can pass different stream types in to the same function. 16.2.4 Controlling Formatting One last useful detail we mention in case you need it for C++ output streams is how to control the specifics of formatting. In C, we can print an integer in decimal with %d and in hexadecimal with %x; however, with C++’s streams, we do not have a place to put such a format string. Instead, the stream (which is an object) has internal state that keeps track of the current formatting specifications. The current format state is altered by either inserting special values (called manipulators) with the << operator or by calling methods on the stream. To change the base in which integers are printed, the first

approach is used, using std::hex, std::dec, or std::oct accordingly. For example, 1 int x = 42; 2 std::cout << x << \"\\n\"; 3 std::cout << std::hex << x << \"\\n\"; 4 std::cout << std::oct << x << \"\\n\"; 5 std::cout << std::dec << x << \"\\n\"; Here, we print the integer x four times. The first time converts the number in whatever base the cout stream was previously left in. Assuming we have not modified its base, it is in decimal, as the C++ library is guaranteed to start the streams in decimal mode. The next line first changes the mode of the stream to hexadecimal then prints x (so it would print out 2a). The third line repeats this process in octal (base 8, so it prints 52). Finally, the stream is converted back to decimal and prints 42. We note that it is generally good practice to put a stream back into decimal mode when you are done printing things in other modes. Other types of formatting are controlled via methods in the stream class. For example, the std::cout.width(5); would set the field width of cout to five, meaning that an output conversion that uses field width (e.g., printing integers) will print at least five characters. What extra characters get printed is controlled by calling the fill method and passing in the desired character. Similarly, the floating point precision can be controlled with the precision method. 16.3 Input In addition to introducing new ways to perform output, C++ also introduces new ways to perform input. Here, we again use stream objects (in this case, istreams), and the stream extraction operator, >>. Much like stdout has an

analog of std::cout, stdin has an analogous std::cin. For example, we might do 1 int x; 2 std::cin >> x; to read an integer from standard input. As with output streams, input streams have a base they work in, which is by default decimal (base 10), so unless we have changed the base of std::cin (e.g. with std::cin >> hex), the integer will be converted from the text typed on standard input as a decimal number. Just like for output streams and the stream insertion operator, you can overload the stream extraction operator for input streams and classes that you write. Many of the lessons from the stream insertion operator that we discussed earlier still apply. You should write your stream extraction operator to take a reference to the input stream (which it returns at the end) and a reference to the type of data you want to read (of course, this reference is not const, as you plan to modify it). For example: 1 std::istream & operator>>(std::istream & stream, 2 //whatever it takes to read things (elided)... 3 return stream; 4} As with stream insertion, you may wish to make this overloaded operator a friend of your class so that it can modify the internal data directly in ways that may not be possible through the external interface. 16.3.1 Errors Remember the code fragment we just saw above to read an integer:

1 int x; 2 std::cin >> x; What happens if you execute this code, but the user enters xyz? Clearly, it cannot be converted to an integer, since the text the user entered is not the base 10 representation of any number. The design of the C++ operator precludes using the return value (which is already used to return the stream so the >>s can be chained together) or passing another argument (the >> operator can only take two arguments) to report the error. Instead, the input stream object contains an error state internally. When an operation produces an error, it sets the stream’s error state. This error state persists, causing future operation to fail, until it is explicitly cleared. When an error occurs, the input that could not be converted is left unread, so future read operations can try to read it (after the error state is cleared). For example, we might write: 1 int x; 2 std::cin >> x; 3 if (!std::cin.good()) { //check if any errors hap 4 std::cin.clear(); //clear the error state 5 std::string badinput; 6 std::cin >> badinput; //read a string 7 if (!std::cin.good()) { 8 std::cerr << \"Cannot read anything from cin! 9} 10 else { 11 std::cerr << \"Oops! \" << badinput << \" wasn 12 } 13 } In the above example, we try to read an int from std::cin. After doing so, we check std::cin.good(), which returns true if no errors have happened and false otherwise. If an error has happened, we use std::cin.clear() to clear the error state so that

subsequent operations can succeed. We then read a string, which could also fail (for example, if we have reached the end of the file). Of course, if the user has entered input that is just not a valid integer, we can succeed in reading it as a string but not in converting it to an int. We therefore check again if we succeeded and print an appropriate error message about the problem that happened. C++’s input streams actually distinguish between three types of failures: end of file (which can be checked with the .eof() method), logical errors on the operation— such as an inability to perform the proper conversion (which can be checked with the .fail() method), and errors with the underlying I/O operation (which can be checked with the .bad() method if .fail() returned false). Of course, output streams can experience errors too and can have similar methods applied to them as needed. It is important to know that if you use the >> operator to read a string, it will only read one “word,” not one line. That is, it will stop at whitespace for what it converts into the string. If you want to read an entire line, use the std::getline,1 function, which takes an input stream reference and a string reference and fills in the string with the next line of input from the stream (unless an error occurs). Note that std::getline is not a member of any class; it is just a function. 16.4 Other Streams C++’s streams can be used for more things than just printing to standard output or reading from standard input. In much the same way that C’s stdio library can be used to work with files, C++’s stream library has classes

that work with files (although, unlike C’s stdio, the types are slightly different between different types of streams). C++ also has streams that collect the data into an internal buffer (or extract it from the buffer), allowing us to manipulate the data within the program (analogously to C’s snprintf and sscanf functions). 16.4.1 Files In C++, files are manipulated using the std::ifstream (for reading), std::ofstream (for writing), and std::fstream (for reading and writing) classes. These classes have default constructors (which create an object with no file associated with it—you can open one later with the open method) and constructors that take a const char * specifying the file name (they also take a second parameter for the mode, but it has an appropriate default value). An open file can be closed with the close method. To use any of these classes, #include <fstream>. When using these classes, data is written to the file with the stream insertion operator (<<) and read from the file with the stream extraction operator (>>). We will note that even though these are not exactly the same types as the ostream and istream we saw earlier, they work with the same operators as if they were the same types. We will understand how exactly this works when we learn about inheritance and polymorphism in Chapter 18. The short version for now is that an ofstream is a special type of ostream and thus is compatible with things that expect pointers or references to ostreams. An fstream is compatible with both ostream and istream, so we can use both << and >> on it. 16.4.2 String Streams

Sometimes we want to manipulate text in ways that the functionality provided by the << or >> operators are convenient, but we do not want to print the output to an external file (or read it in from a file). Instead, we may want to perform this functionality in such a way that we can get the resulting string into a variable (for <<) or extract the fields from a string variable (for >>). We can accomplish such behavior with the std::stringstream class. If we want to use a string stream to “build up” a string into a variable, we can default construct one and then use the << to add elements to the stream. Whenever we use <<, the string stream accumulates the text that would be printed if we were using a “normal” stream. Whenever we are done building the string up, we can use the .str() method to get a std::string with all the text we have inserted into the stream. We can also use a string stream to “pull apart” a string as formatted input; that is, we can use >> to extract pieces from the string the string stream holds in much the same way that we would use >> to read them from cin or a file. Typically, when we do so, we construct the string stream with the constructor that takes a string, passing in the string we want to pull apart. Then we use >> to extract fields into variables of appropriate types. Of course, as with other streams, the extraction could fail, so we must check for errors. The two behaviors are not mutually exclusive—we can insert text into a string stream with << then extract it back out with >>. 16.5 Practice Exercises Selected questions have links to answers in the back of the book.

• Question 16.1 : Use the C++ documentation to find a way to extend a string by appending the contents of another string to the end of it. • Question 16.2 : How do you convert from a C string (char *) to a C++ std::string? What about from a C++ std::string to a C string? • Question 16.3 : What value does the expression std::cout << \"hi\" evaluate to? (Note: this question is not asking what this prints, but what value it evaluates to). Why is the value it evaluates to important? • Question 16.4 : Write the function int myatoi(const std::string & str), which behaves like the atoi function, except that it takes a C++ string (do not use library functions to accomplish this task for you, such as atoi, strtol, or std::stoi). • Question 16.5 : Write the function int myatoiHex(const char * strconst std::strin g * str), which behaves like the atoi function except that it (a) interprets the string as a hexadecimal (base 16) number rather than decimal and (b) takes a std::string (again, do not use library functions to do the work for you.) • Question 16.6 : Re-write the myEcho, myCat, and fileSum programs from Question 11.5, Question 11.5, and Question 11.5. 15 Object Creation and Destruction17 Templates Generated on Thu Jun 27 15:08:37 2019 by L T XML

II C++16 Strings and IO Revisited18 Inheritance

Chapter 17 Templates Often, programmers find themselves needing to perform similar operations on different data types in a similar fashion. For example, if we want to find the largest item in an array of any type of data, we use the same basic algorithm—the only real difference is what the underlying comparison operator does to compare particular elements. For example, consider the following two functions that find the maximum element of an array (and return a pointer to that element). The first operates on an array of ints, while the second operates on an array of strings: 1 int * arrMax(int * array, 2 size_t n) { 3 if (n == 0) { 4 return NULL; 5} 6 int * ans = &array[0]; 7 for (size_t i = 1; i < n; i++) { 8 if (array[i] > *ans) { 9 ans = &array[i]; 10 } 11 } 12 return ans; 13 } 1 string * arrMax(string * array, 2 size_t n) { 3 if (n == 0) { 4 return NULL; 5} 6 string * ans = &array[0]; 7 for (size_t i = 1; i < n; i++) { 8 if (array[i] > *ans) { 9 ans = &array[i]; 10 }

11 } 12 return ans; 13 } These two functions are the same except for the three places where int has been replaced with string (in the return type, in the parameter type, and in the declaration of the local variable answer). In fact, for any type for which the > operator is defined, we could find the maximum element of an array of that type with this same algorithm. We could overload this function for any type we want; however, that approach is unappealing as it requires significant duplication of code. Instead, what we desire (and what C++ gives us, but C does not) is parametric polymorphism. Polymorphism, which literally means “many shapes” or “many forms,” is the ability of the same code to operate on different types. This ability to operate on multiple types reduces code duplication by allowing the same piece of code to be reused across the different types it can operate on. Polymorphism comes in a variety of forms. What we are interested in at the moment is parametric polymorphism, meaning that we can write our code so that it is parameterized over what type it operates on (we will see a different kind of polymorphism in Chapter 18). That is, we want to declare a type parameter T and replace int with T in the above code. Then, when we want to call the function, we can specify the type for T and get the function we desire. C++ provides parametric polymorphism through templates. 17.1 Templated Functions In C++, you can write a templated function by using the keyword template followed by the template parameters in

angle brackets (<>). Unlike function parameters, template parameters may be types, which are specified with typename where the type of the parameter would typically go.1 The template parameters have a scope of the entire templated function. For example, we might write our function that returns a pointer to the largest element in an array as a template as follows: 1 template<typename T> 2 T * arrMax(T * array, size_t n) { 3 if (n == 0) { 4 return NULL; 5} 6 T * ans = &array[0]; 7 for (size_t i = 1; i < n; i++) { 8 if (array[i] > *ans) { 9 ans = &array[i]; 10 } 11 } 12 return ans; 13 } In this example, the templated function has one parameter T, which is a type. In the function, we can use T anywhere we could use any other type. In this particular case, we use T in three places: the return type, the parameter type for array, and the type used to declare the local variable ans. Recall from before that these three places are exactly the places we had to change to alter the original example function when changing it to work on strings instead of ints. Templates may take multiple parameters, and their parameters may be “normal” types, such as int. For example, it would be perfectly valid to write a templated function that looked generally like this: 1 template<typename T, typename S, int N> 2 int someFunction(const T & t, S s) { 3 ... 4}

This templated function takes three parameters, two types and one integer. We do not really care what it does for the purposes of this example, just that we could write it. 17.1.1 Instantiating Templated Functions In much the same way that a function takes parameters and returns a value, we can think of a template as taking parameters and creating a function. The templated function itself is not actually a function. Instead, we must instantiate the template—giving it “values” for its parameters—to create an actual function. Note that even though there is similarity between calling a function (giving it parameters and getting a value in return) and instantiating a template (giving it parameters and getting a function), the two have different terminology as well as other important distinctions, which we will discuss shortly. To instantiate a template, we write the name of the templated function, followed by the arguments we wish to pass inside of angle brackets. The result is a function, which we then call as we normally would: 1 int * m1 = arrMax<int>(myIntArray, nIntElements) 2 string * m2 = arrMax<string>(myStringArray, nStri 3 int x = someFunction<int *, double, 42>(m1, 3.14 Whenever you instantiate a template, the C++ compiler creates a template specialization (or just specialization)—a “normal” function derived from a template for particular values of its parameters—if one does not already exist. If the compiler needs to create the specialization, it does so by taking the template definition and replacing the template parameters with the actual arguments passed in the instantiation. In our example above, the specialization the compiler generates for

arrMax<int> would look exactly like the arrMax function for ints at the start of the chapter. Similarly, the specialization created for arrMax<string> would look just like the arrMax for strings at the start of the chapter. 17.2 Templated Classes In much the same way that C++ allows a programmer to write templated functions, it also allows templated classes. Like a templated function, a templated class has template parameters, which can be either types or values. The scope of the template parameter is the entire class declaration. For example, we could write an Array class that holds an array of any type T (and keeps the size along with it): 1 template<typename T> 2 class Array { 3 private: 4 T * data; 5 size_t size; 6 public: 7 Array() : data(NULL), size(0) {} 8 Array(size_t n) : data(new T[n]()), siz 9 Array(const Array & rhs) : data(NULL), 10 (*this) = rhs; 11 } 12 ~Array() { 13 delete[] data; 14 } 15 Array & operator=(const Array & rhs) { 16 if (this != &rhs) { 17 T * temp = new T[rhs.size]; 18 for (int i = 0; i < rhs.size; i++) 19 temp[i] = rhs.data[i]; 20 } 21 delete[] data; 22 data = temp; 23 size = rhs.size; 24 } 25 return *this; 26 }

27 T & operator[](unsigned ind) { 28 return data[ind]; 29 } 30 const T & operator[] (unsigned ind) con 31 return data[ind]; 32 } 33 size_t getSize() const { 34 return size; 35 } 36 }; As with functions, whenever we instantiate the templated class (by supplying the actual arguments for the parameters), the compiler creates a specialization of that template (if one does not already exist). For example, we could instantiate the template for ints by writing Array<int> and for strings by writing Array<std::string>. The specializations created by (or, if they already exist, referenced by) these two instantiations are different classes. As these two classes are different, they are not interchangeable. For example, the following code is illegal: 1 Array<int> intArray(4); 2 Array<std::string> stringArray(intArray); //illeg There is no constructor in Array<std::string> that can take a Array<int>. The copy constructor can only copy from another Array<std::string>, which is a different type. If you think about this rule, it makes perfect sense: we can not create an array of ints by copying an array of strings. 17.2.1 Templates as Template Parameters There is a third option for template parameters, which we have not yet discussed: they can also be another template! For example, we might write:

1 template<typename T, template<typename> class Con 2 class Something { 3 private: 4 Container<T> data; 5 //other code in the rest of the class... 6 }; Here, Something is a template whose second parameter is another template (specifically, one that takes one type as a parameter—such as the Array template we just made). Inside of the templated class, we can use the template parameter (Container) just like we would use any other template that has the same parameter types. In this particular example, we make a field called data, whose type is Container<T>. With the Array template we wrote above, we could instantiate this templated class like this: 1 Something<int, Array> x; This instantiation will create a specialization whose data field is an Array<int>. Of course, if we always wanted to use an Array to store our data, we could just write that in our class—so why would we want to parameterize this template over this templated class? This is just another example of abstraction—we decouple the specific implementation for how the Container stores its data from the interface required to do so. Our Something template will work with any templated class that conforms to the interface it expects. We then have greater flexibility in how we use it later. 17.3 Template Rules

There are several rules related to the workings of templates. Each of these rules has a good reason based on the way templates work, which we will explain as we present the corresponding rule. We will note that these rules are all quite specific to C++’s templates. Other languages provide similar forms of parametric polymorphism with different rules. 17.3.1 Template Definitions Must Be “Visible” at Instantiations By now, we are used to being able to declare a prototype for a function or the interface for a class in a header file, and place the implementation in the .c or .cpp file. For templates, this rule changes. Instead, the actual definition (i.e., implementation) of the templated function or class must be “visible” to the compiler at the point where the template is instantiated. The compiler cannot just generate a call to it and find it in an object file. The reason for this rule is that a templated function (or class) is not actually a function (or class)—just a recipe to create the specialization when the template is instantiated. When the compiler finds the instantiation of the template, it needs the definition (i.e., recipe) in order to create the actual specialization. It is only at the time when the compiler creates the specialization that there is actual concrete code that can be placed in an object file. Because of this rule, you should write your entire templated classes and functions in their header files. Although this prescription goes against our prior advice on how to do things, it is a special case. The C++ compiler is aware of the problems that typically arise in placing implementations in header files and takes special care to make sure the linker does not encounter

problems when the header file is included by multiple source files, which are then linked together. 17.3.2 Template Arguments Must Be Compile-Time Constants The arguments that are passed to a template must be compile-time constants—they may be an expression, but the compiler must be able to directly evaluate that expression to a constant. For example, if f is a function templated over an int, the following is illegal: 1 for (int i = 0; i < 4; i++) { 2 x += f<i>(x); //illegal: i is not a compile-time cons 3} Note that we can achieve a similar effect with legal code: 1 x += f<0>(x); 2 x += f<1>(x); 3 x += f<2>(x); 4 x += f<3>(x); Even though both do the same basic thing, the second is legal because the template arguments are constants. The compiler is not clever enough (in fact, is not allowed to be clever enough) to convert the former to the latter. The reason for this rule is that the compiler must create a specialization for the argument values given. When it sees f<0>, it has to go create a version of f where the parameter’s value is 0 and then compile that code. If the compiler cannot figure out the exact value of the parameter (easily), then it has no idea what

specializations of the template it should create and thus cannot compile the code. 17.3.3 Templates Are Only Type Checked When Specialized In C++, a template is only type checked when it is specialized. That is, you can write a template that can only legally be instantiated with some types, but not others. This rule is actually quite important, as otherwise we would be heavily restricted in what templates we can write. To see the importance of this rule, let us consider our earlier example of finding the maximum element of an array: 1 template<typename T> 2 T * arrMax(T * array, size_t n) { 3 if (n == 0) { 4 return NULL; 5} 6 T * ans = &array[0]; 7 for (size_t i = 1; i < n; i++) { 8 if (array[i] > *ans) { 9 ans = &array[i]; 10 } 11 } 12 return ans; 13 } If we carefully scrutinize this code, we find that it is legal only for Ts where the > operator is defined to compare two Ts and return a bool. Instantiating this template is therefore legal on int and std::string where this operator is defined. However, there may be other types for which this operator is not defined (and possibly even does not make sense). Fully understanding this rule requires us to be a little bit more precise about exactly when the compiler does

what in regards to specializing a template. For a function, the details are fairly straightforward: the first time the function encounters an instantiation of the templated function with a particular set of arguments, it specializes (and thus type checks) the function. For a class, however, only the specialization occurs in parts. Whenever an instance of the class is created, the compiler specializes the part of the class definition that is required to make the object’s in-memory representation—the fields, as well as virtual methods (which we will learn about in Chapter 18). The “normal” methods (a.k.a. member functions) do not actually affect the in-memory representation of an instance of the object, as they are not placed in the object but rather the code segment (we will learn more about the details of how objects are laid out in memory in Chapter 29). The (non-virtual) methods of a templated class are only specialized when the corresponding method is used. Although this piece-by-piece specialization may seem a bit odd, it actually proves quite useful in the way that C++ templates are used. A programmer can write a templated class and provide methods in that template that only work on types where certain functions or operators are defined. The programmer can then use the template on classes that do not have these functions or operators defined, as long as she does not use the methods that require them. For example, we might write: 1 template<typename T> 2 class Something { 3 T data; 4 //other stuff... 5 public: 6 bool operator==(const Something & rhs) const { 7 return data == rhs.data; 8} 9 bool operator<(const Something & rhs) const { 10 return data < rhs.data;

11 } 12 }; If we instantiate the Something template on a type (T) that admits equality (has an == operator defined) but not ordering (does not have a < operator defined), that is legal. We can use the == operator to compare two Something<T>s. However, if we attempt to compare two Something<T>s with <, then the compiler will specialize the < operator for Something, try to type check it, and produce an error as the < operator is not defined on T. 17.3.4 Multiple Close Brackets Must Be Separated by Whitespace Sometimes you will need to close multiple template angle brackets in succession. For example, suppose you were to instantiate the std::vector template (which we will learn about in Section 17.4.1) with a std::pair (which we will learn about in Section 17.4.2) with an int and a std::string: 1 std::vector<std::pair<int, std::string> > myVecto The white space between the two >s is required. If we wrote this code without the space: 1 //illegal: needs a space between the >>s 2 std::vector<std::pair<int, std::string>> myVector Then we will get an error such as: error: ’>>’ should be ’> >’ within a nested template argument list std::vector<std::pair<int,std::string>> myVector;