| |
|
|
|
CHAPTER 8 Finishing Our homegrown string class
8.1. Objectives of This Chapter
By the end of this chapter, you should
1. Understand how to implement all the concrete data type functions for a class that uses pointers, namely our homegrown string class.
2. Understand in detail the operation and structure of a string class that is useful in some real programming situations.
3. Understand how to write appropriate input and output functions (operator >> and operator <<) for the objects of our string class.
4. Understand how to use some additional C library functions such as memcmp and memset.
5. Understand the (dreaded) C data type, the array, and some of the reasons why it is hazardous to use.
6. Understand the friend declaration, which allows access to private members by selected nonmember functions.
Why We Need a Reference Argument for operator =
Now we're finally ready to examine exactly why the code for our operator = needs a reference argument rather than a value argument. I've drawn two diagrams that illustrate the difference between a value argument and a reference argument. First, Figure 8.1 illustrates what happens when we call a function with a value argument of type string using the compiler-generated copy constructor.1
FIGURE 8.1. Call by value ("normal argument") using the compiler-generated copy constructor
In other words, with a value argument, the called routine makes a copy of the argument on its stack. This won't work properly with a string argument; instead, it will destroy the value of the caller's variable upon return to the calling function. Why is this?
Premature Destruction
The problem occurs when the destructor is called at the end of a function's execution to dispose of the copy of the input argument made at entry. Since the copy points to the same data as the caller's original variable, the destruction of the copy causes the memory allocated to the caller's variable to be freed prematurely.
This is due to the way in which a variable is copied in C++ by the compiler-generated copy constructor. This constructor, like the compiler-generated operator =, makes a copy of all of the parts of the variable (a so-called memberwise copy). In the case of our string variable, this results in copying only the length m_Length and the pointer m_Data, and not the data that m_Data points to. That is, both the original and the copy refer to the same data, as indicated by Figure 8.1. If we were to implement our operator = with a string argument rather than a string& argument, then the following sequence of events would take place during execution of the statement s = n;:
1. A default copy like the one illustrated by Figure 8.1 would be made of the input argument n, causing the variable Str in the operator = code to point to the same data as the caller's variable n.
2. The Str variable would be used in the operator = code.
3. The Str variable would be destroyed at the end of the operator = function. During this process, the destructor would free the memory that Str.m_Data points to by calling delete [].
Since Str.m_Data holds the same address as the caller's variable n.m_Data, the latter now points to memory that has been freed and may be overwritten or assigned to some other use at any time. This is a bug in the program caused by the string destructor being called for a temporary copy of a string that shares data with a caller's variable. When we use a reference argument, however, the variable in the called function is nothing more (and nothing less) than another name for the caller's variable. No copy is made on entry to the operator = code; therefore, the destructor is not called on exit. This allows the caller's variable n to remain unmolested after operator = terminates.
That may sound good, but Susan wanted some more explanation.
Susan: I don't get why a value argument makes a copy and a reference argument doesn't. Help.
Steve: The reason is that a argument:valuevalue argument is actually a new auto variable, just like a regular auto variable, except that it is initialized to the value of the caller's actual argument. Therefore, it has to be destroyed when the called function ends. On the other hand, a reference argument just renames the caller's variable; since the compiler hasn't created a new auto variable when the called routine starts, it doesn't need to call the destructor to destroy that variable at the end of the routine.
Figure 8.2 helped her out a bit by illustrating the same call as in Figure 8.1, using a reference argument instead of a value argument.
FIGURE 8.2. Call by reference
Finally, we've finished examining the intricacies that result from the apparently simple statement s = n; in our test program (Figure 8.3).
FIGURE 8.3. Our first test program for the string class (code\strtst1.cpp)
#include "string1.h"
int main()
{
string s;
string n("Test");
string x;
s = n;
n = "My name is Susan";
x = n;
return 0;
}
Now let's take a look at the next statement in that test program, n = "My name is Susan";. The type of the C string literal expression "My name is Susan" is char*; that is, the compiler stores the character data somewhere and provides a pointer to it. In other words, this line is attempting to assign a char* to a string. Although the compiler has no built-in knowledge of how to do this, we don't have to write any more code to handle this situation because the code we've already written is sufficient. That's because if we supply a value of type char* where a string is needed, the constructor string::string(char*) is automatically invoked. Such automatic conversion is another of the features of C++ that makes user defined types more like native types.2
The sequence of events during compilation of the line n = "My name is Susan"; is something like this:
1. The compiler sees a string on the left of an =, which it interprets as a call to some version of string::operator =.
2. It looks at the expression on the right of the = and sees that its type is not string, but char*.
3. Have we defined a function with the signature string::operator = (char*)? If so, use it.
4. In this case, we have not defined such an operator. Therefore, the compiler checks to see whether we have defined a constructor with the signature string::string(char*) for the string class.
5. Yes, there is such a constructor. Therefore, the compiler interprets the statement as n.operator = (string("My name is Susan"));. If there were no such constructor, that line would be flagged as an error.
So the actual interpretation of n = "My name is Susan"; is n.operator = (string("My name is Susan"));. What exactly does this do?
Figure 8.4 is a picture intended to illustrate the compiler's "thoughts" in this situation; that is, when we assign a C string with the value "My name is Susan" to a string called n via the constructor string::string(char*).3
The Compiler Generates a Temporary Variable
Let's go over Figure 8.4, step by step. The first thing that the compiler does is to call the constructor string::string(char*) to create a temporary (jargon for temporary variable) of type string, having the value "My name is Susan". This temporary is then used as the argument to the function string::operator = (const string& Str) (see Figure 7.15).
FIGURE 8.4. Assigning a char* value to a string via string::string(char*)
Since the argument is a reference, no copy is made of the temporary; the variable Str in the operator = code actually refers to the (unnamed) temporary variable. When the operator = code is finished executing, the string n has been set to the same value as the temporary (i.e., "My name is Susan"). Upon return from the operator = code, the temporary is automatically destroyed by a destructor call inserted by the compiler.
This sequence of events also holds the key to understanding why the argument of string::operator = must be a const string& (that is, a constant reference to a string) rather than just a string& (that is, a reference to a string) if we want to allow automatic conversion from a C string to a string. You see, if we declared the function string::operator = to have a string& argument rather than a const string& argument, then it would be possible for that function to change the value of the argument. However, any attempt to change the caller's argument wouldn't work properly if, as in the current example, the argument turned out to be a temporary string constructed from the original argument (the char* value "My name is Susan"); clearly, changing the temporary string would have no effect on the original argument. Therefore, if the argument to string::operator = were a string&, the line n = "My name is Susan"; would produce a compiler warning to the effect that we might be trying to alter an argument that was a temporary value. The reason we don't get this warning is that the compiler knows that we aren't going to try to modify the value of an argument that has the specification const string&; therefore, constructing a temporary value and passing it to string::operator = is guaranteed to have the behavior that we want.4
This example is anything but intuitively obvious and as you might imagine, led to an extended discussion with Susan.
Susan: So no copy of the argument is made, but the temporary is a copy of the variable to that argument?
Steve: The temporary is an unnamed string created from the C string literal that was passed to operator = by the statement n = "My name is Susan";.
Susan: Okay. But tell me this: Is the use of a temporary the result of specifying a reference argument? If so, then why don't you discuss this when you first discuss reference arguments?
Steve: It's not exactly because we're using a reference argument. When a function is called with the "wrong" type of argument but a constructor is available to make the "right" type of argument from the "wrong" one that was supplied, then the compiler will supply the conversion automatically. In the case of calling operator = with a char* argument rather than a string, there is a constructor that can make a string from a char*. Therefore, the compiler will use that constructor to make a temporary string out of the supplied char* and use that temporary string as the actual argument to the function operator =. However, if the argument type were specified as a string& rather than a const string&, then the compiler would warn us that we might be trying to change the temporary string that it had constructed. Since we have a const string& argument, the compiler knows that we won't try to change that temporary string, so it doesn't need to warn us about this possibility.
Susan: Well, I never looked at it that way, I just felt that if there is a constructor for the argument then it is an OK argument.
Steve: As long as the actual argument matches the type that the constructor expects, there is no problem.
Susan: So, if the argument type were a string& and we changed the temporary argument, what would happen? I don't see the problem with changing something that was temporary; I see that it would be a problem for the original argument but not the temporary.
Steve: The reason why generating a temporary is acceptable in this situation is that the argument is a const reference. If we didn't add the const in front of the argument specifier, then the compiler would warn us about our possibly trying to modify the temporary. Since we have a const reference, the compiler knows that we won't try to modify the argument and thus it's safe for the compiler to generate the temporary value.
Susan: OK, then the temporary is created any time you call a reference argument? I thought that the whole point of a temporary was so you could modify it and not the original argument and the purpose of the const was to ensure that would be the case.
Steve: The point is precisely that nothing would happen to the original argument if we changed the copy. Since one of the reasons that reference arguments are available is to allow changing of the caller's argument, the compiler warns us if we appear to be interested in doing that (a non-const reference argument) in a situation where such a change would have no effect because the actual argument is a temporary.
Susan: So, if we have a non-const string& argument specification with an actual argument of type char* then a temporary is made that can be changed (without affecting the original argument). If the argument is specified as a const string& and the actual argument is of type char* then a temporary is made that cannot be changed.
Steve: You've correctly covered the cases where a temporary is necessary, but haven't mentioned the other cases. Here is the whole truth and nothing but the truth:
1. If we specify the argument type as string& and a temporary has to be created because the actual argument is a char* rather than a string, then the compiler will warn us that changes to that temporary would not affect the original argument.
2. If we specify the argument type as const string& and a temporary has to be created because the actual argument is a char*, then the compiler won't warn us that our (hypothetical) change would be ineffective, because it knows that we aren't going to make such a change.
3. However, if the actual argument is a string, then no temporary needs to be made in either of these cases (string& or const string&). Therefore, the argument that we see in the function is actually the real argument, not a temporary, and the compiler won't warn us about trying to change a (nonexistent) temporary.
Susan: OK, this clears up another confusion I believe, because I was getting confused with the notion of creating a temporary that is basically a copy but I remember that you said that a reference argument doesn't make a copy; it just renames the original argument. So that would be the case in 3 here, but the temporary is called into action only when you have a situation such as in 1 or 2, where a reference to a string is specified as the argument type in the function declaration, while the actual argument is a char*.
Steve: Right.
8.2. The string Copy Constructor
Assuming you've followed this so far, you might have noticed one loose end. What if we want to pass a string as a value argument to a function? As we have seen, with the current setup bad things will happen since the compiler-generated copy constructor doesn't copy strings correctly. Well, you'll be relieved to learn that this, too, can be fixed. The answer is to implement our own version of the copy constructor. Let's take another look at the header file for our string class, in Figure 8.5.
FIGURE 8.5. The string class interface (code\string1.h)
string& operator = (const string& Str);
The line we're interested in here is string(const string& Str);. This is a constructor, since its name is the class name string. It takes one argument, the type of which is const string& (a reference to a constant string). This means that we're not going to change the argument's value "through" the reference, as we could do via a non-const reference. The code in Figure 8.6 implements this new constructor.
FIGURE 8.6. The copy constructor for the string class (from code\string1.cpp)
string::string(const string& Str)
: m_Length(Str.m_Length),
m_Data(new char [m_Length])
{
memcpy(m_Data,Str.m_Data,m_Length);
}
This function's job is similar to that of operator =, which makes sense because both of these functions are in the copying business. However, there are also some differences; otherwise, we wouldn't need two separate functions.
One difference is that because a copy constructor is a constructor, we can use a member initialization list to initialize the member variables; this convenience is not available to operator =, as it is not a constructor.
The other difference is that we don't have to delete any previously held storage that might have been assigned to m_Data. Of course, this is also because we're building a new string, not reusing one that already exists. Therefore, we know that m_Data has never had any storage assigned to it previously.
One fine point that might have slipped past you is why we can't use a value argument rather than a reference argument to our copy constructor. The reason is that using a value argument of a class type requires a copy of the actual argument to be made, using ... the copy constructor! Obviously this won't work when we're writing the copy constructor for that type, so the compiler will let us know if we try to do this accidentally.
Now that we have a correct copy constructor, we can use a string as a value argument to a function, and the copy that's made by the compiler when execution of the function starts will be an independent string, not connected to the caller's variable. When this copy is destroyed at the end of the function, it will go away quietly and the caller's original variable won't be disturbed. This is all very well in theory, but it's time to see some practice. Let's write a function that we can call with a string to do some useful work, like displaying the characters in the string on the screen.
Screen Output
As I hope you remember from the previous chapters, we can send output to the screen via cout, a predefined output destination. For example, to write the character 'a' to the screen we could use the statement cout << 'a';. Although we have previously used cout and << to display string variables of the standard library string class, the current version of our string class doesn't support such output. If we want this ability, we'll have to provide it ourselves. Since variables that can't be displayed are limited in usefulness, we're going to start to do just that right now. Figure 8.7 is the updated header file.
I strongly recommend that you print out the files that contain this interface and its implementation, as well as the test program, for reference as you are going through this part of the chapter; those files are string3.h, string3.cpp, and strtst3.cpp, respectively.
FIGURE 8.7. The string class interface, with Display function (code\string3.h)
string& operator = (const string& Str);
As you can see, the new function is declared as void Display();. This means that it returns no value, its name is Display, and it takes no arguments. This last characteristic may seem odd at first, because surely Display needs to know which string we want to display. However, as we've already seen, each object has its own copy of all of the variables defined in the class interface. In this case, the data that are to be displayed are the characters pointed to by m_Data.
Figure 8.8 is an example of how Display can be used.
FIGURE 8.8. The latest version of the string class test program, using the Display function (code\strtst3.cpp)
See the line that says, n.Display();? That is how our new Display function is called. Remember, it's a member function, so it is always called with respect to a particular string variable; in this case, that variable is n.
As is often the case, Susan thought she didn't understand this idea, but actually did.
Susan: This Display stuff... I don't get it. Do you also have to write the code the classes need to display data on the screen?
Steve: Yes.
Before we get to the code for the Display function, let's take a look at the first few lines of the implementation file for this new version of the string class, which is shown in Figure 8.9.
FIGURE 8.9. The first few lines of the latest implementation of the string class (from string3.cpp)
#include <iostream>
#include <string.h>
using std::cout;
The first two lines of this file aren't anything new: all they do is specify two header files from the standard C++ library to allow us to access the streams and C string functions from that library. But the third line, "using std::cout;" is new. What does it do?
Up until now, our only use of using has been to import all the names from the std namespace, where the names from the standard library are defined. When we are writing our own string class, however, we can't import all those names without causing confusion between our own string class and the one from the standard library.
Luckily, there is a way to import only specific names from the standard library. That's what that line does: it tells the compiler to import the specific name cout from the standard library. Therefore, whenever we refer to cout without qualifying which cout we mean, the compiler will include std::cout in the list of possible matches for that name. We'll have to do that once in a while, whenever we want to use some standard library names, and some of our own.
Susan had some questions about this new use of using.
Susan: What does this new using thing do that's different from the old one?
Steve: When we say using namespace std;, that means that we want all the names from the standard library to be "imported" into the present scope. In this case, however, we don't want it to do that because we have written our own string class. If we wrote using namespace std;, the compiler would get confused between the standard library string class and our string class. For that reason, we will just tell the compiler about individual names from the standard library that we want it to import, rather than doing it wholesale.
Now that that's cleared up, let's look at the implementation of this new member function, Display, in Figure 8.10.
FIGURE 8.10. The string class implementation of the Display function (from string3.cpp)
void string::Display()
{
short i;
for (i = 0; i < m_Length-1; i ++)
cout << m_Data[i];
}
This should be looking almost sensible by now; here's the detailed analysis. We start out with the function declaration, which says we're defining a void function (i.e., one that returns no value) that is a member function of the class string. This function is named Display, and it takes no arguments. Then we define a short called i. The main part of the function is a for loop, which is executed with the index starting at 0 and incremented by one for each character, as usual. The for loop continues while the index is less than the number of displayable characters that we use to store the value of our string; of course, we don't need to display the null byte at the end of the string. So far, so good. Now comes the tricky part. The next statement, which is the controlled block of the for loop, says to send something to cout; that is, display it on the screen. This makes sense, because after all that's the purpose of this function. But what is it that is being sent to cout?
The Array
It's just a char but that may not be obvious from the way it's written. This expression m_Data[i] looks just like a Vec element, doesn't it? In fact, m_Data[i] is an element, but not of a Vec. Instead, it's an element of an array, the C equivalent of a C++ Vec.
What's an array? Well, it's a bunch of data items (elements) of the same type; in this case, it's an array of chars. The array name, m_Data in this case, corresponds to the address of the first of these elements; the other elements follow the first one immediately in memory. If this sounds familiar, it should; it's very much like Susan's old nemesis, a pointer. However, like a Vec, we can also refer to the individual elements by their indexes; so, m_Data[i] refers to the ith element of the array, which in the case of a char array is, oddly enough, a char.
So now it should be clear that each time through the loop, we're sending out the ith element of the array of chars where we stored our string data.
Susan and I had quite a discussion about this topic, and here it is.
Susan: If this is an array or a Vec (I can't tell which), how does the class know about it if you haven't written a constructor for it?
Steve: Arrays are a native feature of C++, left over from C. Thus, we don't have to (and can't) create a constructor and the like for them.
Susan: The best I can figure out from this discussion is that an array is like a Vec but instead of numbers it indexes char data and uses a pointer to do it?
Steve: Very close. It's just like a Vec except that it's missing some rather important features of a Vec. The most important one from our perspective is that an array doesn't have any error-checking; if you give it a silly index you'll get something back, but exactly what is hard to determine.
Susan: If it is just like a Vec and it is not as useful as a real Vec, then why use it? What can it do that a Vec can't?
Steve: A Vec isn't a native data type, whereas an array is. Therefore, you can use arrays to make Vecs, which is in fact how a Vec is implemented at the lowest level. We also wouldn't want to use Vecs to hold our string data because they're much more "expensive" (i.e., large and slow) to use. I'm trying to illustrate how we could make a string class that would resemble one that would actually be usable in a real program and although simplicity is important, I didn't want to go off the deep end in hiding arrays from the reader.
Susan: So when you say that "we're sending out the ith element of the array of chars where we stored our value" does that mean that the "ith" element would be the pointer to some memory address where char data is stored?
Steve: Not exactly. The ith element of the array is just like the ith element of a Vec. If we had a Vec of four chars called x, we'd declare it as follows:
Then we could refer to the individual chars in that Vec as x[0], x[1], x[2], or x[3]. It's much the same for an array. If we had an array of four chars called y, we'd declare it as follows:
Then we could refer to the individual chars in that array as y[0], y[1], y[2], or y[3].
That's all very well, but there's one loose end. We defined m_Data as a char*, which is a pointer to (i.e., the address of) a char. As is common in C and C++, this particular char* is the first of a bunch of chars one after the other in memory. So where did the array come from?
The Equivalence of Arrays and Pointers
Brace yourself for this one. In C++, a pointer and the address of an array are for almost all purposes the same thing. You can treat an array address as a pointer and a pointer as an array address, pretty much as you please. This is a holdover from C and is necessary for compatibility with C programs. People who like C will tell you how "flexible" the equivalence of pointers and arrays is in C. That's true, but it's also extremely dangerous because it means that arrays have no error checking whatsoever. You can use whatever index you feel like, and the compiled code will happily try to access the memory location that would have corresponded to that index. The program in Figure 8.11 is an example of what can go wrong when using arrays.
FIGURE 8.11. Dangerous characters (code\dangchar.cpp)
#include <iostream>
using std::cout;
using std::endl;
int main()
{
char High[10];
char Middle[10];
char Low[10];
char* Alias;
short i;
for (i = 0; i < 10; i ++)
{
Middle[i] = `A' + i;
High[i] = `0';
Low[i] ='1';
}
Alias = Middle;
for (i = 10; i < 20; i ++)
{
Alias[i] = `a' + i;
}
cout << "Low: ";
for (i = 0; i < 10; i ++)
cout << Low[i];
cout << endl;
cout << "Middle: ";
for (i = 0; i < 10; i ++)
cout << Middle[i];
cout << endl;
cout << "Alias: ";
for (i = 0; i < 10; i ++)
cout << Alias[i];
cout << endl;
cout << "High: ";
for (i = 0; i < 10; i ++)
cout << High[i];
cout << endl;
}
First, before trying to analyze this program, I should point out that it contains two using statements to tell the compiler that we want to import individual names from the standard library. In this case, we want the compiler to consider the names std::cout and std::endl as matching the unqualified names cout and endl, respectively.
Now, let's look at what this program does when it's executed. First we define three variables, High, Middle, and Low, each as an array of 10 chars. Then we define a variable Alias as a char*; as you may recall, this is how we specify a pointer to a char. Such a pointer is essentially equivalent to a plain old memory address.
Susan wanted to know something about this program before we got any further into it.
Susan: Why are these arrays called High, Low and Middle?
Steve: Good question. They are named after their relative positions on the stack when the function is executing. We'll see why that is important later.
In the next part of the program, we use a for loop to set each element of the arrays High, Middle, and Low to a value. So far, so good, except that the statement Middle[i] = 'A' + i; may look a bit odd. How can we add a char value like 'A' and a short value such as i?
The char As a Very Short Numeric Variable
Let us return to those thrilling days of yesteryear, or at least Chapter 3. Since then, we've been using chars to hold ASCII values, which is their most common use. However, every char variable actually has a "double life"; it can also be thought of as a "really short" numeric variable that can take on any of 256 values. Thus, we can add and subtract chars and shorts as long as we're careful not to try to use a char to hold a number greater than 255 (or greater than 127, for a signed char). In this case, there's no problem with the magnitude of the result, since we're starting out with the value A and adding a number between 0 and 9 to it; the highest possible result is J, which is still well below the maximum value that can be stored in a char.
With that detail taken care of, let's proceed with the analysis of this program. The next statement after the end of the first for loop is the seemingly simple line Alias = Middle;. This is obviously an assignment statement, but what is being assigned?
The value that Alias receives is the address of the first element of the array Middle. That is, after the assignment statement is executed, Alias is effectively another name for Middle. Therefore, the next loop, which assigns values to elements 10 through 19 of the "array" Alias, actually operates on the array Middle, setting those elements to the values k through t.
The rest of the program is pretty simple; it just displays the characters from each of the Low, Middle, Alias, and High arrays. Of course, Alias isn't really an array, but it acts just like one. To be precise, it acts just like Middle, since it points to the first character in Middle. Therefore, the Alias and Middle loops will display the same characters. Then the final loop displays the values in the High array.
Running off the End of an Array
That's pretty simple, isn't it? Not quite as simple as it looks. If you've been following along closely, you're probably thinking I've gone off the deep end. First, I said that the array Middle had 10 elements (which are numbered 0 through 9 as always in C++); now I'm assigning values to elements numbered 10 through 19. Am I nuts?
No, but the program is. When you run it, you'll discover that it produces the output shown in Figure 8.12.
FIGURE 8.12. Reaping the whirlwind
Most of these results are pretty reasonable; Low is just as it was when we initialized it, and Middle and Alias have the expected portion of the alphabet. But look at High. Shouldn't it be all 0s?
Yes, it should. However, we have broken the rules by writing "past the end" of an array, and the result is that we have overwritten some other data in our program, which in this case turned out to be most of the original values of High. You may wonder why we didn't get an error message as we did when we tried to write to a nonexistent Vec element in an earlier chapter. The reason is that in C, the name of an array is translated into the address of the first element of a number of elements stored consecutively in memory. In other words, an array acts just like a pointer, except that the address of the first element it refers to can't be changed at run time.
In case this equivalence of arrays and pointers isn't immediately obvious to you, you're not alone; it wasn't obvious to Susan, either.
Susan: And when you say that "that is, a pointer (i.e., the address of) a char, which may be the first of a bunch of chars one after another in memory", does that mean the char* points to the first address and then the second and then the third individually, and an array will point at all of them at the same time?
Steve: No, the char* points to the first char, but we (and the compiler) can figure out the addresses of the other chars because they follow the first char sequentially in memory. The same is true of the array; the array name refers to the address of the first char, and the other chars in the array can be addressed with the index added to the array name. In other words, y[2] in the example means "the char that is 2 bytes past the beginning of the array called y".
You might think that this near-identity between pointers and arrays means that the compiler does not keep track of how many elements are in an array. Actually, it does, and it is possible to retrieve that information in the same function where the array is declared, via a mechanism we won't get into in this book. However, array access has no bounds-checking built into it, so the fact that the compiler knows how many elements are in an array doesn't help you when you run off the end of an array. Also, whenever you pass an array as an argument, the information on the number of elements in the array is not available in the called function. So the theoretical possibility of finding out this information in some cases isn't much help in most practical situations.
This is why pointers and arrays are the single most error-prone construct in C (and C++, when they're used recklessly). It's also why we're not going to use either of these constructs except when there's no other reasonable way to accomplish our goals; even then, we'll confine them to tightly controlled circumstances in the implementation of a user defined data type. For example, we don't have to worry about going "off the end" of the array in our Display function, because we know exactly how many characters we've stored (m_Length), and we've written the function to send exactly that many characters to the screen via cout. In fact, all of the member functions of our string class are carefully designed to allocate, use, and dispose of the memory pointed to by m_Data so that the user of this class doesn't have to worry about pointers or arrays, or the problems they can cause. After all, one of the main benefits of using C++ is that the users of a class don't have to concern themselves with the way it works, just with what it does.
Assuming that you've installed the software from the CD in the back of this book, you can try out this program. First, you have to compile it by following the compilation instructions on the CD. Then type dangchar to run the program. You'll see that it indeed prints out the erroneous data shown in Figure 8.12. You can also run it under the debugger, by following the usual instructions for that method.
Susan and I had quite a discussion about this program:
Susan: It is still not clear to me why you assigned values to elements numbered 10-19. Was that for demonstration purposes to force "writing past the end"?
Steve: Yes.
Susan: So by doing this to Middle then it alters the place the pointer is going to point for High?
Steve: No, it doesn't change the address of High. Instead, it uses some of the same addresses that High uses, overwriting some of the data in High.
Susan: So then when High runs there isn't any memory to put its results in? Why does Middle overwrite High instead of High overwriting Middle? But it was Alias that took up high's memory?
Steve: Actually High is filled up with the correct values, but then they're overwritten by the loop that stores via Alias, which is just another name for Middle.
Susan: Is that why High took on the lower case letters? Because Middle took the first loop and then Alias is the same as middle, so that is why it also has the upper case letters but then when High looped it picked up the pointer where Alias left off and that is why it is in lower case? But how did it manage two zeros at the end? I better stop talking, this is getting too weird. You are going to think I am nuts.
Steve: No. You're not nuts, but the program is. We're breaking the rules by writing "past the end" of the array Middle, using the pointer Alias to do so. We could have gotten the same result by storing data into elements 10 through 19 of Middle, but I wanted to show the equivalence of pointers and arrays.
Susan: I was just going to ask if Middle alone would have been sufficient to do the job.
Steve: Yes, it would have been. However, it would not have made the point that arrays and pointers are almost identical in C++.
Susan: I am confused as to why the lower case letters are in High and why k and l are missing and two zeros made their way in. You never told me why those zeros were there.
Steve: Because the end of one array isn't necessarily immediately followed by the beginning of the next array; this depends on the sizes of the arrays and on how the compiler allocates local variables on the stack. What we're doing here is breaking the rules of the language so it shouldn't be a surprise that the result isn't very sensible.
Susan: OK, so if you are breaking the rules you can't predict an outcome? Here I was trying to figure out what was going on by looking at the results even knowing it was erroneous. Ugh.
Steve: Indeed. I guess I should have a couple of diagrams showing what the memory layout looks like before and after the data is overwritten. Let's start with Figure 8.13. Most of that should be fairly obvious, but what are those boxes with question marks in them after the data that we put in the various arrays?
FIGURE 8.13. The memory layout before overwriting the data
Those are just bytes of memory that aren't being used to hold anything at the moment. You see, the compiler doesn't necessarily use every consecutive byte of memory to store all of the variables that we declare. Sometimes, for various reasons which aren't relevant here, it leaves gaps between the memory addresses allocated to our variables.
One more point about this diagram is that I've indicated the location referred to by the expression Alias[10], which as we've already seen is an invalid pointer/array reference. That's where the illegal array/pointer operations will start to mess things up.
Now let's see what the memory layout looks like after executing the loop where we try to store something into memory through Alias[10] through Alias[19].
FIGURE 8.14. The memory layout after overwriting the data
What we have done here is write off the end of the array called Middle and overwrite most of the data for High in the process. Does that clear it up?
Susan: Yes, I think I've got it now. It's sort of like if you dump garbage in a stream running through your back yard and it ends up on your neighbor's property.
Steve: Exactly.
8.3. More about the private Access Specifier
Now that we have disposed of the correspondence between arrays and pointers, it's time to return to our discussion of the private access specifier that we've used to control access to the member variables of the class. First of all, let me refresh your memory as to what this access specifier means: only member functions of the string class can refer to variables or functions marked private. As a rule, no member variables of a class should be public. By contrast, most member functions are public, because such functions provide the interface that is used by programmers who need the facilities of the class being defined. However, non-public member functions are sometimes useful for handling implementation details that aren't of interest or use to the "outside world" beyond the class boundaries, as we'll see later.
Now that I've clarified the role of these access specifiers, let's take a look at the program in Figure 8.15. This program won't compile because it tries to refer to m_Length, a private member variable of string.
FIGURE 8.15. Attempted privacy violation (code\strtst3a.cpp)
Figure 8.16 is the result of trying to compile this program.
FIGURE 8.16. Trying to access a private member variable illegally
STRTST3A.cpp:
Error E2247 STRTST3A.cpp 8: `string::m_Length' is not accessible in function main()
As discussed previously, the reason that we want to prevent access to a member variable is that public member variables cause problems similar to those caused by global variables. To begin with, we want to guarantee consistent, safe behavior of our strings, which is impossible if a nonmember function outside our control can change one of our variables. In the example program, assigning a new value to the m_Length member variable (if that were allowed by the compiler) would trick our Display member function into trying to display 12 characters, when our string contains only four characters of displayable data. Similar bad results would occur if a nonmember function were to change the value of m_Data; we wouldn't have any idea of what it was pointing to or whether we should call delete in the destructor to allow the memory formerly used for our string data to be reused.
Of course, Susan had some questions about access restrictions and public data.
Susan: What's the difference between public and global? I see how they are similar, but how are they different?
Steve: Both global variables and public member variables are accessible from any function, but there is only one copy of any given global variable for the whole program. On the other hand, there is a separate copy of each public member variable for each object in the class where that member variable is defined.
Susan: Okay. Now let me see if I get the problem with Figure 8.15. When you originally wrote m_Length, it was placed in a private area, so it couldn't be accessed through this program?
Steve: Right.
Susan: I am confused on your use of the term nonmember function. Does that mean a nonmember of a particular class or something that is native?
Steve: A nonmember function is any function that is not a member of the class in question.
Susan: A simple concept but easy to forget for some reason.
Steve: Probably because it's stated negatively.
While this may be a convincing argument against letting nonmember functions change our member variables, what about letting them at least retrieve the values of member variables? In other words, why does the private access specifier prevent outside functions from even reading our member variables?
The Advantages of Encapsulation
Unfortunately, even allowing that limited access would be hazardous to the maintainability of our programs, too. The problem here is akin to the other difficulty with global variables: removing or changing the type of a global variable can cause repercussions everywhere in the program. If we decide to implement our string class by a different mechanism than a char* and a short, or even change the names of the member variables from m_Data and m_Length, any programs that rely on those types or names would have to be changed. If our string class were to become popular, this might amount to dozens or even hundreds of programs that would need to be changed if we were to make the slightest change in our member variables. Therefore, the private access specifier rightly prevents nonmember functions from having any direct access to the values of member variables.
Even so, it is sometimes useful for a program that is using an object to find out something about the object's internal state. For example, a user of a string variable might very well want to know how many characters it is storing at the moment, such as when formatting a report. Each string might require a different amount of padding to make the columns on the report line up, depending on the number of visible characters in the string. However, we don't want the length the user sees to include the null byte, which doesn't take up any space on the page. Susan wanted to know how we could allow the user to find out the string's length.
Susan: So how would you "fix" this so that it would run? If you don't want to change m_Length to something public, then would you have to rewrite another string class for this program?
Steve: No, you would generally fix this by writing a member function that returns the length of the string. The GetLength function to be implemented in Figure 8.18 is an example of that.
Susan: Oh, so m_Length stays private but GetLength is public?
Steve: Exactly.
As I've just mentioned to Susan, it is indeed possible to provide such a service without compromising the safety or maintainability of our class, by writing a function that tells the user how long the string is. Figure 8.17 shows the new interface that includes GetLength.
I strongly recommend that you print out the files that contain this interface and its implementation, as well as the test program, for reference as you are going through this part of the chapter; those files are string4.h, string4.cpp, and strtst4.cpp, respectively.
FIGURE 8.17. Yet another version of the string class interface (code\string4.h)
string& operator = (const string& Str);
As you can see, all we have done here is to add the declaration of the new function, GetLength. The implementation in Figure 8.18 is extremely simple: it merely returns the number of chars in the string, deducting 1 for the null byte at the end.
FIGURE 8.18. The string class implementation of the GetLength function (from code\string4.cpp)
short string::GetLength()
{
return m_Length-1;
}
This solves the problem of letting the user of a string variable find out how long the string is without allowing functions outside the class to become overly dependent on our implementation. It's also a good example of how we can provide the right information to the user more easily by creating an access function rather than letting the user get at our member variables directly. After all, we know that m_Length includes the null byte at the end of the string's data, which is irrelevant to the user of the string, so we can adjust our return value to indicate the "visible length" rather than the actual one.
With this mechanism in place, we can make whatever changes we like in how we store the length of our string; as long as we don't change the name or return type of GetLength, no function outside the string class would have to be changed. For example, we could eliminate our m_Length member variable and just have the GetLength call strlen to figure out the length. Because we're not giving access to our member variable, the user's source code wouldn't have to be changed just because we changed the way we keep track of the length. Of course, if we were to allow strings longer than 32767 bytes, we would have to change the return type of GetLength to something more capacious than a short, which would require our users to modify their programs slightly. However, we still have a lot more leeway to make changes in the implementation than we would have if we allowed direct access to our member variables.
The example program in Figure 8.19 illustrates how to use this new function.
FIGURE 8.19. Using the GetLength function in the string class (code\strtst4.cpp)
#include <iostream>
using std::cout;
using std::endl;
#include "string4.h"
int main()
{
short len;
string n("Test");
len = n.GetLength();
cout << "The string has " << len << " characters." << endl;
return 0;
}
8.4. First Review
After finishing most of the requirements to make the string class a concrete data type in the previous chapter, we went back to look at why operator = needs a reference argument rather than a value argument. When we use a value argument, a copy of the argument is made for the use of the called function. In the case of a user-defined data type, this copy is made via the copy constructor defined for that type. If we don't define our own copy constructor, the compiler will generate one for us, which will use memberwise copy; that is, simply copying all of the member variables in the object. While a memberwise copy is fine for simple objects whose data are wholly contained within themselves, it isn't sufficient for objects that contain pointers to data stored in other places, because copying a pointer in one object to a pointer in another object results in the two objects sharing the same actual data. Since our string class does contain such a pointer, the result of this simple(minded) copy is that the newly created string points to the same data as the caller's string. Therefore, when the newly created local string expires at the end of the operator = function, the destructor for that string frees the memory that the caller's string was using to store its data.
This problem is very similar to the reason why we had to write our own operator = in the first place; the compiler-generated version of operator = also simply copies the member variables from the source to the destination object, which causes similar havoc when one of the two "twinned" strings is changed. In the case of our operator =, we can solve the twinning problem by using a reference argument rather than a value argument. A reference argument is another name for the caller's variable rather than a copy of the value in that variable, so no destructor is called for a reference argument when the function exits; therefore, the caller's variable is unchanged.
Next, we examined how it was possible to assign a C string to one of our string variables. This didn't require us to write any more code because we already had a constructor that could create a string from a C string, and an operator = that could assign one string to another one. The compiler helps us out here by employing a rule that can be translated roughly as follows: if we need an object of type A (string, in this case) and we have an object of type B (char*, in this case), and there is a constructor that constructs an A and requires exactly one argument, of type B, then invoke that constructor automatically. The example code is as follows:
where n is a string, and "My name is Susan" is a C string literal, whose type is char*. We have an operator = with the declaration:
string& string::operator = (const string& Str);
that takes a string reference argument, and we have a constructor of the form:
that takes a char* argument and creates a new string. So we have a char*, "My name is Susan", and we need a string. Since we have a constructor string::string(char*), the compiler will use that constructor to make a temporary string with the same value as the char*, and then use the assignment operator string::operator = (const string& Str) to assign the value of that temporary string to the string n. The fact that the temporary is created also provides a clue as to why the argument to string::operator = (const string& Str) should be a const reference, rather than just a (non-const) reference, to a string. The temporary string having the value "My name is Susan" created during the execution of the statement n = "My name is Susan "; disappears after operator = is executed, taking with it any changes that operator = might have wanted to apply to the original argument. With a const reference argument, the compiler knows that operator = doesn't wish to change that argument and therefore doesn't give us a warning that we might be changing a temporary value.
At this point, we've taken care of operator =. However, to create a concrete data type, we still have to allow our string variables to be passed as value arguments, which means we need a copy constructor to handle that task. Unfortunately, the compiler-generated copy constructor suffers from the same drawback as the compiler-generated operator =; namely, it copies the pointer to the actual data of the string, rather than copying the data itself. Logically, therefore, the solution to this problem is quite similar to the solution for operator =; we write our own copy constructor that allocates space for the character data to be stored in the newly created string, and then copies the data from the old string to the new string.
However, we still can't use a value argument to our copy constructor, because a value argument needs a copy constructor to make the copy which would cause an infinite regress.5 This obviously won't work, and will be caught by the compiler. Therefore, as in the case of operator =, we have to use a reference argument; since this is actually just another name for the caller's variable rather than a copy of it, this does not cause an infinite regress. Since we are not going to change the caller's argument, we specify a constant reference argument of type string, or a const string& in C++ terms.
At that point in the chapter, we had met the requirements for a concrete data type, but such a type is of limited usefulness as long as we can't get the values displayed on the screen. Therefore, the next order of business was to add a Display member function that takes care of this task. This function isn't particularly complicated, but it does require us to deal with the notion of a C legacy type, the array. Since the compiler treats an array in almost the same way as a pointer, we can use array notation to extract each character that needs to be sent out to the screen. Continuing with our example of the Display function's use, the next topic was a discussion of how chars can be treated as numeric variables.
Then we saw a demonstration of how easy it is to misuse an array so that you destroy data that belong to some other variable. This is an important warning of the dangers of uncontrolled use of pointers and arrays; these are the most error-prone constructs in both C and C++, when not kept under tight rein.
We continued by revisiting the topic of access control and why it is advantageous to keep member variables out of the public section of the class definition. The reasons are similar to the reasons why we should avoid using global variables; it's too hard to keep track of where the value of a public member variable is being referenced, which in turn makes it very difficult to update all the affected areas of the code when changing the class definition. However, it is often useful to allow external functions access to certain information about a class object. We saw how to do this by adding a GetLength member function to our string class.
8.5. Adding Further Facilities to our string class
At this point, we have a fairly minimal string class. We can create a string, assign it a literal value in the form of a C string literal, and copy the value of one string to another; we can even pass a string as a value argument. Now we'll use our existing techniques along with some new ones to improve the facilities that the string class provides.
To make this goal more concrete, let's suppose that we want to modify the sorting program of Chapter 4 to sort strings, rather than shorts. To use the sorting algorithm from that program, we'll need to be able to compare two strings to see which would come after the other in the dictionary, as we can compare two shorts to see which is greater. We also want to be able to use cout and << to display strings on the screen and cin and >> to read them from the keyboard.
Before we go into the changes needed in the string class to allow us to write a string sorting program, Figure 8.20 shows our goal: the selection sort adapted to sort a Vec of strings instead of one of shorts.
Assuming that you've installed the software from the CD in the back of this book, you can compile this program in the usual way, then run it by typing strsort1. You'll see that it indeed prints out the information in the StockItem object. You can also run it under the debugger, by following the usual instructions for that method.
FIGURE 8.20. Sorting a Vec of strings (code\strsort1.cpp)
string HighestName = "zzzzzzzz";
cout << "I'm going to ask you to type in five last names." << endl;
cout << "Please type in name #" << i+1 << ": ";
Name[FirstIndex] = HighestName;
cout << "Here are the names, in alphabetical order: " << endl;
cout << SortedName[i] << endl;
Susan had a couple of comments and questions about this program:
Susan: Why aren't you using caps when you initiate your variable of HighestName; I don't understand why you use "zzzzzzzzzz" instead of "ZZZZZZZZZZ"? Are you going to fix this later so that caps will work the same way as lower case letters?
Steve: If I were to make that change, the program wouldn't work correctly if someone typed their name in lower case letters because lower case letters are higher in ASCII value than upper case letters. That is, "abc" is higher than "ZZZ". Thus, if someone typed in their name in lower case, the program would fail to find their name as the lowest name. Actually, the way the string sorting function works, "ABC" is completely different from "abc"; they won't be next to one another in the sorted list. We could fix this by using a different method of comparing the strings that would ignore case, if that were necessary.
If you compare this program to the original one that sorts short values (Figure 4.6 on page 164), you'll see that they are very similar. This is good because that's what we wanted to achieve. Let's take a look at the differences between these two programs.
1. First, we have several using declarations to tell the compiler what we mean by cin, cout, and endl. In the original program, we used a blanket using namespace std; declaration, so we didn't need specific using declarations for these names. Now we're being more specific about which names we want to use from that library and which are ours.
2. The next difference is that we're sorting the names in ascending alphabetical order, rather than descending order of weight as with the original program. This means that we have to start out by finding the name that would come first in the dictionary (the "lowest" name). By contrast, in the original program we were looking for the highest weight, not the lowest one; therefore, we have to do the sort "backward" from the previous example.
3. The third difference is that the Vecs Name and SortedName are collections of strings, rather than the corresponding Vecs of shorts in the first program: Weight and SortedWeight.
4. The final difference is that we've added a new variable called HighestName, which plays the role of the value 0 that was used to initialize HighestWeight in the original program. That is, it is used to initialize the variable LowestName to a value that will certainly be replaced by the first name we find, just as 0 was used to initialize the variable HighestWeight to a value that had to be lower than the first weight we would find. The reason why we need a "really high" name rather than a "really low" one is because we're sorting the "lowest" name to the front, rather than sorting the highest weight to the front as we did originally.
You may think these changes to the program aren't very significant. That's a correct conclusion; we'll spend much more time on the changes we have to make to our string class before this program will run, or even compile. The advantage of making up our own data types (like strings) is that we can make them behave in any way we like. Of course, the corresponding disadvantage is that we have to provide the code to implement that behavior and give the compiler enough information to use that code to perform the operations we request. In this case, we'll need to tell the compiler how to compare strings, read them in via >> and write them out via <<. Let's start with Figure 8.21, which shows the new interface specification of the string class, including all of the new member functions needed to implement the comparison and I/O operators, as well as operator ==, which we'll implement later in the chapter.
FIGURE 8.21. The updated string class interface, including comparison and I/O operators (code\string5.h)
friend std::ostream& operator << (std::ostream& os, const string& Str);
friend std::istream& operator >> (std::istream& is, string& Str);
string& operator = (const string& Str);
bool operator < (const string& Str);
bool operator == (const string& Str);
I strongly recommend that you print out the files that contain this interface and its implementation, as well as the test program, for reference as you are going through this part of the chapter; those files are string5.h, string5.cpp, and strtst5.cpp, respectively.
Implementing operator <
Our next topic is operator < (the "less than" operator), which we need so that we can use the selection sort to arrange strings by their dictionary order. The declaration of this operator is similar to that of operator =, except that rather than defining what it means to say x = y; for two strings x and y, we are defining what it means to say x < y. Of course, we want our operator < to act analogously to the < operator for short values; that is, our operator will compare two strings and return true if the first string would come before the second string in the dictionary and false otherwise, as needed for the selection sort.
All right, then, how do we actually implement this undoubtedly useful facility? Let's start by examining the function declaration bool string::operator < (const string& Str); a little more closely. This means that we're declaring a function that returns a bool and is a member function of class string; its name is operator <, and it takes a constant reference to a string as its argument. As we've seen before, operators don't look the same when we use them as when we define them. In the sorting program in Figure 8.20, the line if (Name[k] < LowestName) actually means if (Name[k].operator < (LowestName)). In other words, if the return value from the call to operator < is false, then the if expression will also be considered false and the controlled block of the if won't be executed. On the other hand, if the return value from the call to operator < is true, then the if expression will also be considered true and the controlled block of the if will be executed. To make this work correctly, our version of operator < will return the value true if the first string is less than the second and false otherwise.
Now that we've seen how the compiler will use our new function, let's look at its implementation, which follows these steps:
1. Determine the length of the shorter of the two strings.
2. Compare a character from the first string with the corresponding character from the second string.
3. If the character from the first string is less than the character from the second string, then we know that the first string precedes the second in the dictionary, so we're done and the result is true.
4. If the character from the first string is greater than the character from the second string, then we know that the first string follows the second in the dictionary. Therefore, we're done and the result is false.
5. If the two characters are the same and we haven't come to the end of the shorter string, then move to the next character in each string, and go back to step 2.
6. When we run out of characters to compare, if the strings are the same length then the answer is that they are identical, so we're done and the result is false.
7. On the other hand, if the strings are different in length, and if we run out of characters in the shorter string before finding a difference between the two strings, then the longer string follows the shorter one in the dictionary. In this case, the result is true if the second string is longer and false if the first string is longer.
You may be wondering why we need special code to handle the case where the strings differ in length. Wouldn't it be simpler to compare up to the length of the longer string?
Details of the Comparison Algorithm
As it happens, that approach would work properly so long as both of the strings we're comparing have a null byte at their ends and neither of them have a null byte anywhere else. To see the reason for the limitation of that approach, let's look at what the memory layout might look like for two string variables x and y, with the contents "post" and "poster" respectively. In Figure 8.22, the letters in the box labeled "string contents" represent themselves, while the 0s represent the null byte, not the digit 0.
If we were to compare the strings up to the longer of the two lengths with this memory layout, the sequence of events would be:
1. Get character p from location 12345600.
2. Get character p from location 1234560a.
3. They are the same, so continue.
4. Get character o from location 12345601.
5. Get character o from location 1234560b.
6. They are the same, so continue.
7. Get character s from location 12345602.
8. Get character s from location 1234560c.
9. They are the same, so continue.
10. Get character t from location 12345603.
11. Get character t from location 1234560d.
12. They are the same, so continue.
13. Get a null byte from location 12345604.
14. Get character e from location 1234560e.
15. The character e from the second string is higher than the null byte from the first string, so we conclude (correctly) that the second string comes after the first one.
FIGURE 8.22. strings x and y in memory
This works because the null byte, having an ASCII code of 0, in fact has a lower value than whatever non-null byte is in the corresponding position of the other string.
However, this plan wouldn't work reliably if we had a string with a null byte in the middle. To see why, let's change the memory layout slightly to stick a null byte in the middle of string y. Figure 8.23 shows the modified layout.
FIGURE 8.23. strings x and y in memory, with an embedded null byte
You may reasonably object that we don't have any way to create a string with a null byte in it. That's true at the moment, but one reason we're storing the actual length of the string rather than relying on the null byte to mark the end of a string, as is done with C strings, is that keeping track of the length separately makes it possible to have a string that has any characters whatever in it, even nulls.
For example, we could add a string constructor that takes an array of bytes and a length and copies the specified number of bytes from the array. Since an array of bytes can contain any characters in it, including nulls, that new constructor would obviously allow us to create a string with a null in the middle of it. If we tried to use the preceding comparison mechanism, it wouldn't work reliably, as shown in the following analysis.
1. Get character p from location 12345600.
2. Get character p from location 1234560a.
3. They are the same, so continue.
4. Get character o from location 12345601.
5. Get character o from location 1234560b.
6. They are the same, so continue.
7. Get character s from location 12345602.
8. Get character s from location 1234560c.
9. They are the same, so continue.
10. Get character t from location 12345603.
11. Get character t from location 1234560d.
12. They are the same, so continue.
13. Get a null byte from location 12345604.
14. Get a null byte from location 1234560e.
15. They are the same, so continue.
16. Get character t from location 12345605.
17. Get character r from location 1234560f.
18. The character t from the first string is greater than the character r from the second string, so we conclude that the first string comes after the second one.
Unfortunately, this conclusion is incorrect; what we have actually done is run off the end of the first string and started retrieving data from the next location in memory. Since we want to be able to handle the situation where one of the strings has one or more embedded nulls, we have to stop the comparison as soon as we get to the end of the shorter string. Whatever happens to be past the end of that string's data is not relevant to our comparison of the two strings.
Let's listen in on the discussion Susan and I had on this topic.
Susan: Why is the return value from operator < a bool?
Steve: Because there are only two possible answers that it can give: either the first string is less than the second string or it isn't. In the first case true is the appropriate answer, and in the second case, of course, false is the appropriate answer. Thus, a bool is appropriate for this use.
Susan: Again I am not seeing where we're using string::operator < (const string& Str); in the sorting program.
Steve: That's because all you have to say is a < b, just as with operator =; the compiler knows that a < b, where a and b are strings, means string::operator < (const string&).
Susan: Why are you bringing up this stuff about what the operator looks like and the way it is defined? Do you mean that's what is really happening even though it looks like built in code?
Steve: Yes.
Susan: Who puts those null bytes into memory?
Steve: The compiler supplies a null byte automatically at the end of every literal string, such as "abc".
Susan: I don't get where you are not using a null byte when storing the length; it looks to me that you are. This is confusing. Ugh.
Steve: I understand why that's confusing, I think. I am including the null byte at the end of a string when we create it from a C string literal, so that we can mix our strings with C strings more readily. However, because we store the length separately, it's possible to construct a string that has null bytes in the middle of it as well as at the end. This is not possible with a C string, because that has no explicit length stored with it; instead, the routines that operate on C strings assume that the first null byte means the C string is finished.
Susan: Why do you jump from a null byte to a t? Didn't it run out of letters? Is this what you mean by retrieving data from the next location in memory? Why was a t there?
Steve: Yes, this is an example of retrieving random information from the next location in memory. We got a t because that just happened to be there. The problem is that since we're using an explicit length rather than a null byte to indicate the end of our strings, we can't count on a null byte stopping the comparison correctly. Thus, we have to worry about handling the case where there is a null byte in the middle of a string.
Now that we've examined why the algorithm for operator < works the way it does, it will probably be easier to understand the code if we follow an example of how it is used. I've written a program called strtst5x.cpp for this purpose; Figure 8.24 has the code for that program.
FIGURE 8.24. Using operator < for strings (code\strtst5x.cpp)
#include <iostream>
#include "string5.h"
using std::cout;
using std::endl;
int main()
{
string x;
string y;
x = "ape";
y = "axes";
if (x < y)
cout << x << " comes before " << y << endl;
else
cout << x << " doesn't come before " << y << endl;
return 0;
}
You can see that in this program the two strings being compared are "ape" and "axes", which are assigned to strings x and y respectively. As we've already discussed, the compiler translates a comparison between two strings into a call to the function string::operator <(const string& Str); in this case, the line that does that comparison is if (x < y).
Now that we've seen how to use this comparison operator, Figure 8.25 shows one way to implement it.
FIGURE 8.25. The implementation of operator < for strings (from code\string5a.cpp)
bool string::operator < (const string& Str)
{
short i;
bool Result;
bool ResultFound;
short CompareLength;
if (Str.m_Length < m_Length)
CompareLength = Str.m_Length;
else
CompareLength = m_Length;
ResultFound = false;
for (i = 0; (i < CompareLength) && (ResultFound == false); i ++)
{
if (m_Data[i] < Str.m_Data[i])
{
Result = true;
ResultFound = true;
}
else
{
if (m_Data[i] > Str.m_Data[i])
{
Result = false;
ResultFound = true;
}
}
}
if (ResultFound == false)
{
if (m_Length < Str.m_Length)
Result = true;
else
Result = false;
}
return Result;
}
The variables we'll use in this function are:
1. i, which is used as a loop index in the for loop that steps through all of the characters to be compared.
2. Result, which is used to hold the true or false value that we'll return to the caller.
3. ResultFound, which we'll use to keep track of whether we've found the result yet.
4. CompareLength, which we'll use to determine the number of characters to compare in the two strings.
After defining variables, the next four lines of the code determine how many characters from each string we actually have to compare; the value of CompareLength is set to the lesser of the lengths of our string and the string referred to by Str. In this case, that value is 4, the length of our string (including the terminating null byte).
Now we're ready to do the comparison. This takes the form of a for loop that steps through all of the characters to be compared in each string. The header of the for loop is for (i = 0; (i < CompareLength) && (ResultFound == false); i ++). The first and last parts of the expression controlling the for loop should be familiar by now; they initialize and increment the loop control variable. But what about the continuation expression (i < CompareLength) && (ResultFound == false)?
The Logical AND Operator
That expression states a two-part condition for continuing the loop. The first part, (i < CompareLength), is the usual condition that allows the program to execute the loop as long as the index variable is within the correct range. The second part, (ResultFound == false), should also be fairly clear; we want to test whether we've already found the result we're looking for and continue only as long as that isn't the case (i.e., ResultFound is still false). The () around each of these expressions are used to tell the compiler that we want to evaluate each of these expressions first, before the && is applied to their results. That leaves the && symbol as the only mystery.
It's really not too mysterious. The && operator is the symbol for the "logical AND" operator, which means that we want to combine the truth or falsity of two expressions each of which has a logical value of true or false. The result of using && to combine the results of these two expressions will also be a logical value. Here is the way the value of that expression is determined:
1. If both of the expressions connected by the && are true, then the value of the expression containing the && is also true;
2. Otherwise, the value of the expression containing the && is false.
If you think about it for a minute, this should make sense. We want to continue the loop as long as both of the conditions are true; that is,
1. i is less than CompareLength; and
2. ResultFound is false (we haven't found what we're looking for).
That's why the && operator is called logical AND; it checks whether condition 1 and condition 2 are both true. If either is false, we want to stop the loop, and this continuation expression will do just that.6
Now let's trace the path of execution through the for loop in Figure 8.25. On the first time through the loop, the index i is 0 and ResultFound is false. Therefore, the continuation expression allows us to execute the statements in the loop, where we test whether the current character in our string, namely m_Data[i], is less than the corresponding character from the string Str, namely Str.m_Data[i].
By the way, in case the expression in the if statement, if (m_Data[i] < Str.m_Data[i]), doesn't make sense immediately, perhaps I should remind you that the array notation m_Data[i] means the ith character of the data pointed to by m_Data; an index value of 0 means the first element, as is always the case when using an array or Vec. We've already covered this starting with the section entitled "The Equivalence of Arrays and Pointers" on page 491; you should go back and reread that section if you're not comfortable with the equivalence between pointers and arrays.
The code in Figure 8.26 compares characters from the two strings.
FIGURE 8.26. Is our character less than the one from the other string? (from code\string5a.cpp)
if (m_Data[i] < Str.m_Data[i])
{
Result = true;
ResultFound = true;
}
If the current character in our string were less than the corresponding character in Str, we would have our answer; our string would be less than the other string. If that were the case, we would set Result to true and ResultFound to true and would be finished with this execution of the for loop.
As it happens, in our current example both m_Data[0] and Str.m_Data[0] are equal to `a', so they're equal to each other as well. What happens when the character from our string is the same as the one from the string Str?
In that case, the first if, whose condition is stated as if (m_Data[i] < Str.m_Data[i]), is false. So we continue with the else clause of that if statement, which looks like Figure 8.27.
FIGURE 8.27. The else clause in the comparison loop (from code\string5a.cpp)
if (m_Data[i] > Str.m_Data[i])
This clause contains another if statement that compares the character from our string to the one from Str. Since the two characters are the same, this if also comes out false so the controlled block of the if isn't executed. After this if statement, we've reached the end of the controlled block of the for statement. The next iteration of the for loop starts by incrementing i to 1. Then the continuation expression is evaluated again; i is still less than CompareLength and ResultFound is still false, so we execute the controlled block of the loop again with i equal to 1.
On this pass through the for loop, m_Data[1] (the character from our string) is `p' and Str.m_Data[1] (the character from the other string) is `x'. Therefore, the condition in the first if statement (that the character from our string is less than the character from the other string) is true, so we execute the controlled block of the if statement. This sets Result to true, and ResultFound also to true, as you can see in Figure 8.26.
We're now at the end of the for loop, so we return to the for statement to continue execution. First, i is incremented again, to 2. Then the continuation expression (i < CompareLength) && (ResultFound == false) is evaluated. The first part of the condition, i < CompareLength is true, since i is 2 and CompareLength is 4. However, the second part of the condition, ResultFound == false, is false, because we've just set ResultFound to true. Since the result of the && operator is true only when both subconditions are true, the for loop terminates, passing control to the next statement after the controlled block of the loop (Figure 8.28).
FIGURE 8.28. Handling the return value (from code\string5a.cpp)
In the current scenario, ResultFound is true because we have found a character from m_Data that differs from the corresponding character from Str.m_Data; therefore, the condition in the first if is false, and we proceed to the next statement after the end of the if statement, return Result;. This shouldn't come as too much of a surprise; we know the answer to the comparison, namely, that our string is less than the other string, so we're ready to tell the caller the information that he requested by calling our routine.
Other Possible Results of the Comparison
The path of execution is almost exactly the same if, the first time we find a mismatch between the two strings, the character from our string is greater than the character from the other string. The only difference is that the if statement that handles this scenario sets Result to false rather than true (Figure 8.27), because our string is not less than the other string; of course, it still sets ResultFound to true, since we know the result that will be returned.
There's only one other possibility; that the two strings are the same up to the length of the shorter one (e.g., "post" and "poster"). In that case, the for loop will expire of natural causes when i gets to be greater than or equal to CompareLength. Then the final if statement shown in Figure 8.28 will evaluate to true, because ResultFound is still false. In this case, if the length of our string is less than the length of the other string, we will set Result to true, because a shorter string will precede a longer one in the dictionary if the two strings are the same up to the length of the shorter one.
Otherwise, we'll set Result to false, because our string is at least as long as the other one; since they're equal up to the length of the shorter one, our string can't precede the other string. In this case, either they're identical, or our string is longer than the other one and therefore should follow it. Either of these two conditions means that the result of operator < is false, so that's what we tell the caller via our return value.
Using a Standard Library Function to Simplify the Code
This implementation of operator < for strings works. However, there's a much simpler way to do it. Figure 8.29 shows the code.
FIGURE 8.29. Implementing operator < for strings (from code\string5.cpp)
bool string::operator < (const string& Str)
{
short Result;
short CompareLength;
if (Str.m_Length < m_Length)
CompareLength = Str.m_Length;
else
CompareLength = m_Length;
Result = memcmp(m_Data,Str.m_Data,CompareLength);
if (Result < 0)
return true;
if (Result > 0)
return false;
if (m_Length < Str.m_Length)
return true;
return false;
}
This starts out in the same way as our previous version, by figuring out how much of the two strings we actually need to compare character by character. Right after that calculation, though, the code is very different; where's that big for loop?
It's contained in the standard library function memcmp, a carryover from C, which does exactly what that for loop did for us. Although C doesn't have the kind of strings that we're implementing here, it does have primitive facilities for dealing with arrays of characters, including comparing one array with another, character by character. One type of character array supported by C is the C string, which we've already encountered. However, C strings have a serious drawback for our purposes here; they use a null byte to mark the end of a group of characters. This isn't suitable for our strings, whose length is explicitly stored; as noted previously, our strings could theoretically have null bytes in them. There are several C functions that compare C strings, but they rely on the null byte for their proper operation so we can't use them.
However, these limitations of C strings are so evident that the library writers have supplied another set of functions that act almost identically to the ones used for C strings, except that they don't rely on null bytes to determine how much data to process. Instead, whenever you use one of these functions, you have to tell it how many characters to manipulate. In this case, we're calling memcmp, which compares two arrays of characters up to a specified length. The first argument is the first array to be compared (corresponding to our string), the second argument is the second array to be compared (corresponding to the string Str), and the third argument is the length for which the two arrays are to be compared. The return value from memcmp is calculated by the following rules:
1. It's less than 0 if the first array would precede the second in the dictionary, considering only the length specified;
2. It's 0 if they are the same up to the length specified;
3. It's greater than 0 if the first array would follow the second in the dictionary, considering only the length specified.
This is very convenient for us, because if the return value from memcmp is less than 0, we know that our result will be true, while if the return value from memcmp is greater than 0, then our result will be false. The only complication, which isn't very complicated, is that if the return value from memcmp is 0, meaning that the two arrays are the same up to the length of the shorter character array, we have to see which is longer. If the first one is shorter, then it precedes the second one; therefore, our result is true. Otherwise, it's false.
Susan had some questions about this version of operator <, including why we had to go through the previous exercise if we could just use memcmp.
Susan: What is this? I suppose there was a purpose to all the confusing prior discussion if you have an easier way of defining operator <? UGH! This new stuff just pops up out of the blue! What is going on? Please explain the reason for the earlier torture.
Steve: I thought we should examine the character-by-character version of operator < before taking the shortcut. That should make it easier to follow the explanation of the "string overrun" problem, as each character comparison shows up in the code.
Susan: So, memcmp is another library function, and does it stand for memory compare? Also, are the return values built into memcmp? This is very confusing, because you have return values in the code.
Steve: Yes, memcmp stands for "memory compare". As for return values; yes, it has them, but they aren't exactly the ones that we want. We have to return the value true for "less than" and false for "not less than", which aren't the values that memcmp returns. Also, memcmp doesn't do the whole job when the strings aren't the same length; in that case, we have to handle the trailing part of the longer string manually.
One small point that shouldn't be overlooked is that in this version of the operator < code, we have more than one return statement; in fact, we have four! That's perfectly legal and should be clear to a reader of this function. It's usually not a good idea to scatter return statements around in a large function, because it's easy to overlook them when trying to follow the flow of control through the function. In this case, though, that's not likely to be a problem; any reasonably fluent reader of C++ code will find this organization easy to understand.
Implementing operator ==
Although our current task requires only operator <, another comparison operator, operator ==, will make an interesting contrast in implementation; in addition, a concrete data type that allows comparisons should really implement more than just operator <. Since we've just finished one comparison operator, we might as well knock this one off now (Figure 8.30).
This function is considerably simpler than the previous one. Why is this, since they have almost the same purpose? It's because in this case we don't care which of the two strings is greater than the other, just whether they're the same or different. Therefore, we don't have to worry about comparing the two char arrays if they're of different lengths. Two arrays of different lengths can't be the same, so we can just return false. Once we have determined that the two arrays are the same length, we do the comparison via memcmp. This gives us the answer directly, because if Result is 0, then the two strings are equal; otherwise, they're different.
FIGURE 8.30. Implementing operator == for strings (from code\string5.cpp)
bool string::operator == (const string& Str)
{
short Result;
if (m_Length != Str.m_Length)
return false;
Result = memcmp(m_Data,Str.m_Data,m_Length);
if (Result == 0)
return true;
return false;
}
Even though this function is simpler than operator <, it's not simple enough to avoid Susan's probing eye:
Susan: Does == only check to see if the lengths of the arrays are the same? Can it not ever be used for a value?
Steve: It compares the values in the arrays, but only if they are the same length. Since all it cares about is whether they are equal, and arrays of different length can't be equal, it doesn't have to compare the character data unless the arrays are of the same length.
Implementation vs. Declaration Revisited
Before moving on to see how we will display a string on the screen via operator <<, I should bring up a couple of points here because otherwise they might pass you by. First, we didn't have to change our interface header file string5.h (Figure 8.21) just because we changed the implementation of operator < between string5a.cpp and string5.cpp. Since the signature of this function didn't change, neither the header file nor the user program had to change. Second, we didn't even implement operator == in the string5a.cpp version of the string library and yet our test program still compiled without difficulty. How can this be?
In C++, you can declare all of the functions you want to, whether they are member functions or global functions, without actually defining them. As long as no one tries to actually use the functions, everything will work fine. In fact, the compiler doesn't even care whether any functions you do refer to are available; that's up to the linker to worry about. This is very handy when you know that you're going to add functions in a later revision of a class, as was the case here. Of course, you should warn your class users if you have listed functions in the interface header file that aren't available. It's true that they'll find out about the missing functions the first time they try to link a program that uses one of these functions, because the linker will report that it can't find the function; however, if they've spent a lot of time writing a program using one of these functions, they're likely to get mad at you for misleading them. So let them know what's actually implemented and what's "for later".
Now let's continue with our extensions to the string class, by looking at how we send a string out to the screen.
Using cout With User-defined Types
We've been using cout and its operator << for awhile, but have taken them for granted. Now we have to look under the hood a bit.
The first question is what type of object cout is. The answer is that it's an ostream (short for "output stream"), which is an object that you can use to send characters to some output device. I'm not sure of the origin of this term, but you can imagine that you are pushing the characters out into a "stream" that leads to the output device.
As you may recall from our uses of cout, you can chain a bunch of << expressions together in one statement, as in Figure 8.31. If you compile and execute that program, it will display:
Notice that it displays the short as a number and the char as a letter, just as we want it to do. This desirable event occurs because there's a separate version of << for each type of data that can be displayed; in other words, operator << uses function overloading, just like the constructors for the StockItem class and the string class. We'll also use function overloading to add support for our string class to the I/O facilities supplied by the iostream library.
FIGURE 8.31. Chaining several operator << expressions together (code\cout1.cpp)
#include <iostream>
using namespace std;
int main()
{
short x;
char y;
x = 1;
y = `A';
cout << "On test #" << x << ", your mark is: " << y << endl;
return 0;
}
How cout Works With Pre-existing Types
Before we examine how to accomplish this goal, though, we'll have to go into some detail about how the pre-existing output functions behave. Let's start with a simple case using a version of operator << supplied by the iostream header file. The simplest possible use of ostream's operator <<, of course, uses only one occurrence of the operator. Here's an example where the value is a char:
As you may remember, using an operator such as << on an object is always equivalent to a "normal" function call. This particular example is equivalent to the following:
which calls ostream::operator << (char) (i.e., the version of the operator << member function of the iostream class that takes a char as its input) for the predefined destination cout, which writes the char on the screen.
That takes care of the single occurrence of operator <<. However, as we've already seen, it's possible to string together any number of occurrences of operator <<, with the output of each successive occurrence following the output created by the one to its left. We want our string output function to behave just like the ones predefined in iostream, so let's look next at an example that illustrates multiple uses of operator <<, taking a char and a C string:
This is equivalent to
(cout.operator << ('a')).operator << (" string");
What does this mean? Well, since an expression in parentheses is evaluated before anything outside the parentheses, the first thing that happens is that ostream::operator << (char) is called for the predefined destination cout, which writes the `a' to the screen. Now here's the tricky part: the return value from every version of ostream::operator << is a reference to the ostream that it operates on (cout, in this case). Therefore, after the `a' has been written on the screen, the rest of the expression reduces to this:
That is, the next output operation behaves exactly like the first one. In this case, ostream::operator << (char*) is the function called, because char* is the type of the argument to be written out. It too returns a reference to the ostream for which it was called, so that any further << calls can add their data to that same ostream. It should be fairly obvious how the same process can be extended to handle any number of items to be displayed.
Writing Our Own Standard Library-Compatible operator <<
That illustrates how the designers of ostream could create member functions that would behave in this convenient way. However, we can't use the same mechanism that they did; we can't modify the definition of the ostream class in the library, because we didn't write it in the first place and don't have access to its source code.7 Is there some way to give our strings convenient input and output facilities?
In fact, there is. To do this, we create a global function called operator << that accepts an ostream& (that is, a reference to an ostream), adds the contents of our string to the ostream, and then returns a reference to the same ostream. This will support multiple occurrences of operator << being chained together in one statement, just like the operator << member functions from the iostream library. The implementation of this function is shown in Figure 8.32.
As usual, we should first examine the function declaration; in this case, a couple of points are worth noting. We've already seen that the first argument is an ostream&, to which we will add the characters from the string that is the second argument. Also notice that the second argument is a const string&, that is, a reference to a constant string. This is the best way to declare this argument because we aren't going to change the argument, and there's no reason to make a copy of it.
FIGURE 8.32. An operator << function to output a string (from code\string5.cpp)
std::ostream& operator << (std::ostream& os, const string& Str)
{
short i;
for (i=0; i < Str.m_Length-1; i ++)
os << Str.m_Data[i];
return os;
}
But possibly the most important point about the function declaration is that this operator << is not a member function of the string class, which explains why it isn't called string::operator <<. It's a global function that can be called anywhere in a program that needs to use it, so long as that program has included the header file that defines it. Its operation is pretty simple. Since there is no ostream function to write out a specified number of characters from a char array, we have to call ostream::operator << (char) for each character in the array.
Therefore, we use the statement
os << Str.m_Data[i];
to write out each character from the array called m_Data that we use to store the data for our string on the ostream called os, which is just another name for the ostream that is the first argument to this function.
After all the characters have been written to the ostream, we return it so that the next operator << call in the line can continue producing output.
However, there's a loose end here. How can a global function, which by definition isn't a member function of class string, get at the internal workings of a string? We declared that m_Length and m_Data were private, so that they wouldn't be accessible to just any old function that wandered along to look at them. Is nothing sacred?
The friend Keyword
In fact, private data aren't accessible to just any function. However, operator << (std::ostream&, const string&) isn't just any function. Take a look at string5.h in Figure 8.21 to see why. The line we're interested in here is this one:
friend std::ostream& operator << (std::ostream& os, const string& Str);
The key word here is friend. We're telling the compiler that a function with the signature std::ostream& operator << (std::ostream&, const string&) is permitted to access the information normally reserved for member functions of the string class; i.e., anything that isn't marked public. It's possible to make an entire class a friend to another class; here, we're specifying one function that is a friend to this class.8
You probably won't be surprised to learn that Susan had some questions about this operator. Let's see how the discussion went:
Susan: Let's start with friend. . . what is that?
Steve: A friend is a function or class that is allowed to access internals of this class, as though the friend were a member function. In other words, the private access specifier doesn't have any effect on friends.
Susan: What is an ostream? How is it related to istream?
Steve: An ostream is a stream that is used for output; streams can be either input (istream) or output (ostream).
Susan: Why does it have std:: in front of it?
Steve: Because we are specifying that we mean the ostream that is in the standard library. It's a good idea to avoid using declarations in commonly used header files, as I've explained previously, and this is another way of telling the compiler exactly which ostream we mean.
Susan: This stream character seems to have a lot of relatives.
Steve: You're right; there are lots of classes in the stream family, including istream, ostream, ifstream, and ofstream. And it really is a family, in the C++ sense at least; these classes are related by inheritance, which we'll get to in Chapter 9.
That explains why this global function can access our non-public data. But why did we have to create a global function in the first place, rather than just adding a member function to our string class?
Because a member function of a class has to be called for an object of that class, whose address then becomes the this pointer; in the case of the << operator, the class of the object is ostream, not string. Figure 8.33 is an example.
FIGURE 8.33. Why operator << has to be implemented via a global function
The line cout << x; is the same as cout.operator << (x);. Notice that the object to which the operator << call is applied is cout, not x. Since cout is an ostream, not a string, we can't use a member function of string to do our output, but a global function is perfectly suitable.
Reading a string from an istream
Now that we have an output function that will write our string variables to an ostream, such as cout, it would be very handy to have an input function that could read a string from an istream, such as cin. You might expect that this would be pretty simple now that we've worked through the previous exercise, and you'd be mostly right. As usual, though, there are a few twists in the path.
Let's start by looking at the code in Figure 8.34.
FIGURE 8.34. A operator >> function to input a string (from code\string5.cpp)
std::istream& operator >> (std::istream& is, string& Str)
{
const short BUFLEN = 256;
char Buf[BUFLEN];
memset(Buf,0,BUFLEN);
if (is.peek() == `\n')
is.ignore();
is.getline(Buf,BUFLEN,'\n');
Str = Buf;
return is;
}
The header is pretty similar to the one from the operator << function, which is reasonable, since they're complementary functions. In this case, we're defining a global function with the signature std::istream& operator >> (std::istream& is, string& Str). In other words, this function, called operator >>, has a first argument that is a reference to an istream, which is just like an ostream except that we read data from it rather than writing data to it. One significant difference between this function signature and the one for operator << is that the second argument is a non-const reference, rather than a const reference, to the string into which we want to read the data from the istream. That's because the whole purpose of this function is to modify the string passed in as the second argument; to be exact, we're going to fill it in with the characters taken out of the istream.
Continuing with the analysis of the function declaration, the return value is another istream reference, which is passed to the next operator >> function to the right, if there is one; otherwise it will just be discarded.
After decoding the header, let's move to the first line in the function body, const short BUFLEN = 256;. While we've encountered const before, specifying that we aren't going to change an argument passed to us, that can't be the meaning here. What does const mean in this context?
It specifies that the item being defined, which in this case is short BUFLEN, isn't a variable, but a constant, or const value. That is, its value can't be changed. Of course, a logical question is how we can use a const, if we can't set its value.9
8.6. Initialization vs. Assignment
This is another of the places where it's important to differentiate between initialization and assignment. We can't assign a value to a const, but we can initialize it; in fact, because an uninitialized const is useless, the attempt to define a const without specifying its initial (and only) value is a compile-time error. In this case, we're initializing it to the value 256; if we just wrote const short BUFLEN;, we'd get an error report something like the one in Figure 8.35 when we tried to compile it.
FIGURE 8.35. Error from an uninitialized const (code\string5x.err)
STRING5X.cpp:
Error E2304 STRING5X.cpp 82: Constant variable `BUFLEN' must be initialized in function operator >>(_STL::istream &,string &)
Error E2313 STRING5X.cpp 84: Constant expression required in function operator >>(_STL::istream &,string &)
*** 2 errors in Compile ***
Susan wanted some further explanation.
Susan: I still don't get why const is used here.
Steve: This is a different use of const than we've seen before; in this case, it's an instruction to the compiler meaning "the following 'variable' isn't really variable, but constant. Don't allow it to be modified." This allows us to use it where we would otherwise have to use a literal constant, like 256 itself. The reason that using a const is better than using a literal constant is that it makes it easier to change all the occurrences of that value. In the present case, for example, we use BUFLEN three times after its definition; if we used the literal constant 256 in all of those places, we'd have to change all of them if we decided to make the buffer larger or smaller. As it is, however, we only have to change the definition of BUFLEN and all of the places where it's used will use the new value automatically.
Susan: Okay, I think I have it now.
Now that we've disposed of that detail, let's continue with our examination of the implementation of operator >>. The next nonblank line is char Buf[BUFLEN];. This is a little different from any variable definition we've seen before; however, you might be able to guess something about it from its appearance. It seems to be defining a variable called Buf whose type is related in some way to char. But what about the [BUFLEN] part?10
This is a definition of a variable of that dreaded type, the array; specifically, we're defining an array called Buf, which contains BUFLEN chars. As you may recall, this is somewhat like the Vec type that we've used before, except that it has absolutely no error checking; if we try to access a char that is past the end of the array, something will happen, but not anything good.11 In this case, as in our previous use of pointers, we'll use this dangerous construct only in a very small part of our code, under controlled circumstances; the user of our string class won't be exposed to the array.
Before we continue analyzing this function, I should point out that C++ has a rule that the number of elements of an array must be known at compile time. That is, the program in Figure 8.36 isn't legal C++.
FIGURE 8.36. Use of a non-const array size (code\string5y.cpp)
int main()
{
short BUFLEN = 256;
char ch;
char Buf[BUFLEN];
ch = Buf[0];
}
I'll admit that I don't understand exactly why using a non-const array size is illegal; a C++ compiler has enough information to create and access an array whose length is known at run time. In fact, some compilers do allow it.12 But it is not compliant with the standard, so we won't use it in our programs. Instead, we'll use the const value BUFLEN to specify the number of chars in the array Buf in the statement char Buf[BUFLEN];.
The memset Standard Library Function
Now we're up to the first line of the executable part of the operator >> function in Figure 8.34 on page 541: memset(Buf,0,BUFLEN);. This is a call to a function called memset (short for "memory set"), which is in the standard C library. You may be able to guess from its name that it is related to the function memcmp that we used to compare two arrays of chars. If so, your guess would be correct; memset is C-talk for "set all the bytes in an area of memory to the same value". The first argument is the address of the area of memory to be set to a specified value, the second argument is the char value to which all the bytes will be set, and the third argument is the number of bytes to be set to that value, starting at the address given in the first argument. In other words, this statement will set all of the bytes in the array called Buf to 0. This is important because we're going to treat that array as a C string later. As you may recall, a C string is terminated by a null byte, so we want to make sure that the array Buf doesn't contain any junk that might be misinterpreted as part of the data we're reading in from the istream.
Next, we have an if statement controlling a function called ignore:
What exactly does this sequence do? It solves a problem with reading C string data from a file; namely, where do we stop reading? With a numeric variable, that's easy; the answer is "whenever we see a character that doesn't look like part of a number". However, with a data type like our string that can take just about any characters as part of its value, it's more difficult to figure out where we should stop reading. The solution I've adopted is to stop reading when we get to a newline ('\n') character; that is, the end of a line.13 This is no problem when reading from the keyboard, as long as each data item is on its own line, but what about reading from a file?
When we read a C string from a file via the standard function getline (described in detail below), as we do in our operator >> implementation, the newline at the end of the line is discarded. As a result, the next C string to be read in starts at the beginning of the next line of the file, as we wish. This approach to handling newline characters works well as long as all of the variables being read in are strings. However, in the case of the StockItem class (for example), we needed to be able to mix shorts and strings in the file. In that case, reading a value for a short stops at the newline, because that character isn't a valid part of a numeric value. This is OK as long as the next variable to be read is also a short, because spaces and newlines at the beginning of the input data are ignored when we're reading a numeric value. However, when the next variable to be read after a short is a string, the leftover newline from the previous read is interpreted as the beginning of the data for the string, which terminates input for the string before we ever read anything into it. Therefore, we have to check whether the next available char in the input stream is a newline, in which case we have to skip it. On the other hand, if the next character to be read in is something other than a newline, we want to keep it as the first character of our string. That's what the if statement does. First, the s.peek() function call returns the next character in the input stream without removing it from the stream; then, if it turns out to be a newline, we tell the input stream to ignore it, so it won't mess up our reading of the actual data in the next line.
You won't be surprised to hear that Susan had a couple of questions about this function.
Susan: Where do peek and ignore come from?
Steve: They're defined in the iostream header file <iostream>.
Susan: How did you know that they were available?
Steve: By reading a book called C++ IOstreams Handbook by Steve Teale. However, that book is obsolete now that the standard library has been adopted. A newer book that I understand is very good is Standard C++ IOStreams and Locales Advanced Programmer's Guide and Reference by Angelika Langer & Klaus Kreft (Addison-Wesley, January 2000, ISBN 0-201-18395-1). Of course, there is also a fair amount of coverage of streams in both The C++ Programming Language and The C++ Standard Library, but those are both quite technical and not terribly well suited for beginning programmers.
Now that we've dealt with that detail, we're ready to read the data for our string. That's the job of the next line in the function: is.getline(Buf,BUFLEN,'\n');. Since is is an istream, this is a member function of istream. To be precise, it's the member function that reads a number of characters into a char array. The arguments are as follows:
1. The array into which to read characters
2. The number of characters that the array can contain
3. The "terminating character", where getline should stop reading characters
This function will read characters into the array (in this case Buf) until one of two events occurs:
1. The size of the array is reached
2. The "terminating character" is the next character to be read
Note that the terminating character is not read into the array.
Before continuing with the rest of the code for operator >>, let's take a closer look at the following two lines, so we can see why it's a bad idea to use the C string and memory manipulation library any more than we have to. The lines in question are
The problem is that we have to specify the length of the array Buf explicitly (as BUFLEN, in this case). In this small function, we can keep track of that length without much effort, but in a large program with many references to Buf, it would be all too easy to make a mistake in specifying its length. As we've already seen, the result of specifying a length that is greater than the actual length of the array would be a serious error in the functioning of the program; namely, some memory belonging to some other variable would be overwritten. Whenever we use the mem functions in the C library, we're liable to run into such problems. That's an excellent reason to avoid them except in strictly controlled situations, such as the present one, where the definition of the array is in the same small function as the uses of the array. By no coincidence, this is the same problem caused by the indiscriminate use of pointers; the difficulty with the C memory manipulation functions is that they use pointers (or arrays, which are essentially interchangeable with pointers), with all of the hazards that such use entails.
Now that I've nagged you sufficiently about the dangers of arrays, let's look at the rest of the operator >> code. The next statement is Str = Buf;, which sets the argument Str to the contents of the array Buf. Buf is the address of the first char in an array of chars, so its type is char*; Str, on the other hand, is a string. Therefore, this apparently innocent assignment statement actually calls string::string(char*) to make a temporary string, and then calls string::operator=(const string&) to copy that temporary string to Str. Because Str is a reference argument, this causes the string that the caller provided on the right of the >> to be set to the value of the temporary string that was just created.
Finally, we have the statement return is;. This simply returns the same istream that we got as an argument, so that the next input operator in the same statement can continue reading from the istream where we left off. Now our strings can be read from an input stream (such as cin) and written to an output stream (such as cout), just like variables known to the standard library. This allows our program that sorts strings to do some useful work.14
Assuming that you've installed the software from the CD in the back of this book, you can try out this program. First, you have to compile it by following the compilation instructions on the CD. Then type strsort1 to run the program. You can also run it under the debugger, by following the usual instructions for that method.
Now that we've finished our upgrades to the string class, let's look back at what we've covered since our first review in this chapter.
8.7. Second Review
After finishing the requirements to make the string class a concrete data type, we continued to add more facilities to this class; to be precise, we wanted to make it possible to modify the sorting program of Chapter 4 to handle strings rather than shorts. To do this, we had to be able to compare two strings to determine which of the two would come first in the dictionary and to read strings from an input stream (like cin) and write them to an output stream (like cout). Although the Display function provided a primitive mechanism for writing a string to cout, it's much nicer to be able to use the standard >> and << operators that can handle all of the native types so we resolved to make those operators available for strings as well.
We started out by implementing the < operator so that we could compare two strings x and y to see which would come before the other in the dictionary, simply by writing if (x < y). The implementation of this function turned out to be a bit complicated because of the possibility of "running off the end" of one of the strings, when the strings are of different lengths.
Once we worked out the appropriate handling for this situation, we examined two implementations of the algorithm for operator <. The first implementation compared characters from the two strings one at a time, while the second used memcmp, a C function that compares two sets of bytes and returns a different value depending on whether the first set is "less than", "equal to", or "greater than" the second one, using ASCII ordering to make this determination.
Then we developed an implementation of operator == for strings, which turned out to be considerably simpler than the second version of operator <, even though both functions used memcmp to do most of the work; the reason is that we have to compare the contents of the strings only if they are of the same length, because strings of different lengths cannot be equal.
Then we started looking beneath the covers of the output functions called operator<<, starting with the predefined versions of << that handle char and C string arguments. The simplest case of using this operator, of course, is to display one expression on the screen via cout. Next, we examined the mechanism by which several uses of this operator can be chained together to allow the displaying of a number of expressions with one statement.
The next issue was how to provide these handy facilities for the users of our string class. Would we have to modify the ostream classes to add support for strings? Luckily, the designers of the stream classes were foresightful enough to enable us to add support for our own data types without having to modify their code. The key is to create a global function that can add the contents of our string to an existing ostream variable and pass that ostream variable on to the next possible user, just as in "chaining" for native types.
The implementation of this function wasn't terribly complicated; it merely wrote each char of the string's data to the output stream. The unusual attribute of this function was that it wasn't a member function of string, but a global function, as is needed to maintain the same syntax as the output of native types. We used the friend specifier to allow this version of operator << to access private members of string such as m_Length and m_Data.
After we finished the examination of our version of operator << for sending strings to an ostream, we went through the parallel exercise of creating a version of operator >> to read strings from an istream. This turned out to be a bit more complicated, since we had to make room for the incoming data. This limited the maximum length of a string that we could read. In the process of defining this maximum length, we also encountered a new construct, the const. This is a data item that is declared just like a variable, except that its value is initialized once and cannot be changed . This makes the const ideal for specifying a constant size for an array, a constant loop limit, or another value that doesn't change from one execution of the program to the next. Next, we used this const value to declare an array of chars to hold the input data to be stored in the string, and filled the array with null bytes, by calling the C function memset. We followed this by using some member functions of the istream class to eliminate any newline ('\n') character that might have been left over from a previous input operation.
Finally, we were ready to read the data into the array of chars, in preparation for assigning it to our string. After doing that assignment, we returned the original istream to the caller, to allow chaining of operations as is standard with operator << and operator >>.
That completes the review of this chapter. Now let's do some exercises to help it all sink in.
8.8. Exercises
1. What would happen if we compiled the program in Figure 8.37? Why?
FIGURE 8.37. Exercise 1 (code\strex5.cpp)
class string
{
public:
string(const string& Str);
string(char* p);
string& operator = (const string& Str);
~string();
private:
string();
short m_Length;
char* m_Data;
};
int main()
{
string n("Test");
string x = n;
n = "My name is Susan";
return 0;
}
2. What would happen if we compiled the program in Figure 8.38? Why?
FIGURE 8.38. Exercise 2 (code\strex6.cpp)
class string
{
public:
string();
string& operator = (const string& Str);
private:
string(char* p);
short m_Length;
char* m_Data;
};
int main()
{
string n;
n = "My name is Susan";
return 0;
}
3. We have already implemented operator < and operator ==. However, a concrete data type that allows for ordered comparisons such as < should really implement all six of the comparison operators. The other four of these operators are >, >=, <=, and != ("greater than", "greater than or equal to", "less than or equal to", and "not equal to", respectively). Add the declarations of each of these operators to the string interface definition.
4. Implement the four comparison operators that you declared in the previous exercise.
5. Write a test program to verify that all of the comparison operators work. This program should test that each of the operators returns the value true when its condition is true; equally important, it should test that each of the operators returns the value false when the condition is not true.
8.9. Conclusion
In this chapter, we have significantly improved the string class, learning some generally useful techniques and lessons in the process. In the next chapter, we'll return to our inventory control example, which we'll extend with some techniques that we haven't seen before. First, though, you should finish up with this chapter by doing the exercises.
You have been doing the exercises, haven't you? If not, you should definitely go back and do them. If you can get all of the answers right, including the reasons why the answers are the way they are, then you'll be ready to continue learning some of the more advanced concepts of C++ in the rest of this book.
8.10. Answers to Exercises
1. This one was a little tricky. I'll bet you thought that making the default constructor private would keep this from compiling, but it turns out that we're not using the default constructor. That should be obvious in the line string n("Test");, which clearly uses string::string(char* p), but what does the compiler do with the line string x = n;? You might think that it calls the default constructor to make x and then uses operator = to copy the value of n into it. If that were true, the private status of the default constructor would prevent the program from compiling. However, what actually happens is that the copy constructor string::string(const string&) is used to make a brand new string called x with the same value as n. So, in this case, the private access specifier on the default constructor doesn't get in the way.
2. The output of the compiler should look something like this:
STREX6.cpp:
Error E2247 STREX6.cpp 16: `string::string(char *)' is not accessible in function main()
*** 1 errors in Compile ***
This one is a bit tricky. The actual problem is that making the constructor string::string(char*) private prevents the automatic conversion from char* to string required for the string::operator = (const string&) assignment operator to work. As long as there is an accessible string::string(char*) constructor, the compiler will use that constructor to build a temporary string from a char* argument on the right side of an =. This temporary string will then be used by string::operator = (const string&) as the source of data to modify the string on the left of the =. However, this is not possible if the constructor that makes a string from a char* isn't accessible where it is needed.15
3. The new class interface is shown in Figure 8.39.
FIGURE 8.39. The string class interface file (from code\string6.h)
#ifndef STRING6_H
#define STRING6_H
#include <iostream>
class string
{
friend std::ostream& operator << (std::ostream& os, const string& Str);
friend std::istream& operator >> (std::istream& is, string& Str);
public:
string();
string(const string& Str);
string& operator = (const string& Str);
~string();
string(char* p);
short GetLength();
bool operator < (const string& Str);
bool operator == (const string& Str);
bool operator > (const string& Str);
bool operator >= (const string& Str);
bool operator <= (const string& Str);
bool operator != (const string& Str);
private:
short m_Length;
char* m_Data;
};
#endif
4. The implementations of the comparison operators are shown in Figures 8.40 through 8.43.
FIGURE 8.40. The string class implementation of operator > (from code\string6.cpp)
bool string::operator > (const string& Str)
{
short Result;
short CompareLength;
if (Str.m_Length < m_Length)
CompareLength = Str.m_Length;
else
CompareLength = m_Length;
Result = memcmp(m_Data,Str.m_Data,CompareLength);
if (Result > 0)
return true;
if (Result < 0)
return false;
if (m_Length > Str.m_Length)
return true;
return false;
}
FIGURE 8.41. The string class implementation of operator >= (from code\string6.cpp)
bool string::operator >= (const string& Str)
{
short Result;
short CompareLength;
if (Str.m_Length < m_Length)
CompareLength = Str.m_Length;
else
CompareLength = m_Length;
Result = memcmp(m_Data,Str.m_Data,CompareLength);
if (Result > 0)
return true;
if (Result < 0)
return false;
if (m_Length >= Str.m_Length)
return true;
return false;
}
FIGURE 8.42. The string class implementation of operator != (from code\string6.cpp)
bool string::operator != (const string& Str)
{
short Result;
if (m_Length != Str.m_Length)
return true;
Result = memcmp(m_Data,Str.m_Data,m_Length);
if (Result == 0)
return false;
return true;
}
FIGURE 8.43. The string class implementation of operator <= (from code\string6.cpp)
bool string::operator <= (const string& Str)
Result = memcmp(m_Data,Str.m_Data,CompareLength);
5. The test program appears in Figure 8.44.
FIGURE 8.44. The test program for the comparison operators of the string class (code\strcmp.cpp)
#include <iostream>
#include "string6.h"
using std::cout;
using std::endl;
int main()
{
string x = "x";
string xx = "xx";
string y = "y";
string yy = "yy";
// testing <
if (x < x)
cout << "ERROR: x < x" << endl;
else
cout << "OKAY: x NOT < x" << endl;
if (x < xx)
cout << "OKAY: x < xx" << endl;
else
cout << "ERROR: x NOT < xx" << endl;
if (x < y)
cout << "OKAY: x < y" << endl;
else
cout << "ERROR: x NOT < y" << endl;
// testing <=
if (x <= x)
cout << "OKAY: x <= x" << endl;
else
cout << "ERROR: x NOT <= x" << endl;
if (x <= xx)
cout << "OKAY: x <= xx" << endl;
else
cout << "ERROR: x NOT <= xx" << endl;
if (x <= y)
cout << "OKAY: x <= y" << endl;
else
cout << "ERROR: x NOT <= y" << endl;
// testing >
if (y > y)
cout << "ERROR: y > y" << endl;
else
cout << "OKAY: y NOT > y" << endl;
if (yy > y)
cout << "OKAY: yy > y" << endl;
else
cout << "ERROR: yy NOT > y" << endl;
if (y > x)
cout << "OKAY: y > x" << endl;
else
cout << "ERROR: y NOT > x" << endl;
// testing >=
if (y >= y)
cout << "OKAY: y >= y" << endl;
else
cout << "ERROR: y NOT >= y" << endl;
if (yy >= y)
cout << "OKAY: yy >= y" << endl;
else
cout << "ERROR: yy NOT >= y" << endl;
if (y >= x)
cout << "OKAY: y >= x" << endl;
else
cout << "ERROR: y NOT >= x" << endl;
// testing ==
if (x == x)
cout << "OKAY: x == x" << endl;
else
cout << "ERROR: x NOT == x" << endl;
if (x == xx)
cout << "ERROR: x == xx" << endl;
else
cout << "OKAY: x NOT == xx" << endl;
if (x == y)
cout << "ERROR: x == y" << endl;
else
cout << "OKAY: x NOT == y" << endl;
// testing !=
if (x != x)
cout << "ERROR: x != x" << endl;
else
cout << "OKAY: x NOT != x" << endl;
if (x != xx)
cout << "OKAY: x != xx" << endl;
else
cout << "ERROR: x NOT != xx" << endl;
if (x != y)
cout << "OKAY: x != y" << endl;
else
cout << "ERROR: x NOT != y" << endl;
return 0;
}
1 If this diagram looks familiar, it's the same as the one illustrating the problem with the compiler-generated operator =, Figure 7.11, except for labels.
2 There are situations, however, where this usually helpful feature is undesirable; for this reason, C++ provides a way of preventing the compiler from supplying such conversions automatically. We'll see how to do that in Chapter 12.
3 Rather than showing each byte address of the characters in the strings and C strings as I've done in previous diagrams, I'm just showing the address of the first character in each group, so that the figure will fit on one page.
4 By the way, the compiler insists that a function isn't going to modify an argument with the const specifier; if we wrote a function with a const argument and then tried to modify such an argument, it wouldn't compile.
5 See recursion in the glossary.
6 This operator follows a rule analogous to the one for ||: if the expression on the left of the && is false, then the answer must be false and the expression on the right is not executed at all. The reason for this "short-circuit evaluation rule" is that in some cases you may want to write a right-hand expression for && that will only be legal if the left-hand expression is true.
7 Even if we did have the source code to the ostream class, we wouldn't want to modify it, for a number of reasons. One excellent reason is that every time a new version of the library came out, we'd have to make our changes again. Also, there are other ways to reuse the code from the library for our own purposes using mechanisms that we'll get to later in this book, although we won't use them with the iostream classes.
8 The signature of the function is important here, as elsewhere in C++; this friend declaration would not permit a function with the same name and a different signature, for example std::ostream& operator << (std::ostream&, int) to access non-public members of string.
9 In case you were wondering how I came up with the name BUFLEN, it's short for "buffer length". Also, I should mention the reason that it is all caps rather than mixed case or all lower case: an old C convention (carried over into C++) specifies that named constants should be named in all caps to enable the reader to distinguish them from variables at a glance.
10 This is another common C practice; using "buf" as shorthand for "buffer", or "place to store stuff while we're working on it".
11 See the discussion of arrays starting on page 489.
12 According to Eric Raymond, there is no good reason for this limitation; it's a historical artifact. In fact, it may be removed in a future revision of the C++ standard, but for now we'll have to live with this limitation of C++.
13 Note that this is different from the behavior of the standard library string class, which won't keep reading data for a string from a stream past a blank.
14 The implementation of operator << will also work for any other output destination, such as a file; however, our current implementation of operator >> isn't really suitable for reading a string from an arbitrary input source. The reason is that we're counting on the input data being able to fit into the Buf array, which is 256 bytes in length. This is fine for input from the keyboard, at least under DOS, because the maximum line length in that situation is 128 characters. It will also work for our inventory file, because the lines in that file are shorter than 256 bytes. However, there's no way to limit the length of lines in any arbitrary data file we might want to read from, so this won't do as a general solution. Of course, increasing the size of the Buf array wouldn't solve the problem; no matter how large we make it, we couldn't be sure that a line from a file wouldn't be too long. One solution would be to handle long lines in sections.
15 By the way, in case you're wondering what char * means, it's the same as char*. As I've mentioned previously, I prefer the latter as being easier to understand, but they mean the same to the compiler.
| |
|
|
|
