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)

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include "string5.h"

#include "Vec.h"

int main()

{

Vec<string> Name(5);

Vec<string> SortedName(5);

string LowestName;

short FirstIndex;

short i;

short k;

string HighestName = "zzzzzzzz";

cout << "I'm going to ask you to type in five last names." << endl;

for (i = 0; i < 5; i ++)

{

cout << "Please type in name #" << i+1 << ": ";

cin >> Name[i];

}

for (i = 0; i < 5; i ++)

{

LowestName = HighestName;

FirstIndex = 0;

for (k = 0; k < 5; k ++)

{

if (Name[k] < LowestName)

{

LowestName = Name[k];

FirstIndex = k;

}

}

SortedName[i] = LowestName;

Name[FirstIndex] = HighestName;

}

cout << "Here are the names, in alphabetical order: " << endl;

for (i = 0; i < 5; i ++)

cout << SortedName[i] << endl;

return 0;

}

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)

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);

private:

short m_Length;

char* m_Data;

};

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.¹

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;