The class contains no error checking to keep it small--obviously you would want to add some if this were a commercial product.
Now let's say that you want to modify this class to add two features. First, you want to have a sorted insertion function so that the class maintains a sorted list. Second, you want to keep track of the total sum of all items in the list. Rather than cycling through all elements in the list each time the sum function is called, you want to keep a running total as each item is inserted.
Obviously one way to do this is to simply modify the List class shown above. In C++ you use inheritance to make the changes instead. We will create a SortedList class by inheriting the List class and modifying it. Let's start by adding the sorted insertion feature:
The List class is totally unchanged--we have simply created the SortedList class on top of it. The SortedList class inherits its behavior from the List class--it is derived from the List class. The List class is the base class for SortedList.
The List class is inherited on the fist line:
The colon indicates that we are inheriting something. The word public indicates that we want the public functions and variables in List to remain public in the SortedList class. We could have also used private or protected. In either of these cases any public variables and functions in the inherited class would be converted in the derived class. The use of public here is standard.
The diagram below shows what is happening:
The SortedList class simply extends the List class. Anyone using the SortedList class has access to the functions available in List as well as the new functions available in SortedList.
The constructor for SortedList is also new--we have used a colon here to call the constructor for the inherited class:
This line says that the constructor named List from the base class should be called, and that the SortedList constructor needs to do nothing of its own.
In the remainder of the SortedList class we simply add the new SortedInsert function into the class. This new function makes use of the old Insert, Get, and Size functions from the List class as needed, but it does not access any of the List class data members directly because it can't--they are private to the List class, so they cannot be seen in the inheriting class.
Say that you wanted to have a variable or a function that seems private to outside users of a class but seems public to classes that inherit the class. For example, say that the SortedList class needed direct access to the array variable in List in order to improve its performance, but we still want to keep normal instances of List and SortedList from accessing the array directly. The word protected: can be used in the same manner as public: or private: to indicate this behavior. By declaring array as a protected member in List, it would be accessible by the derived class SortedList but not by normal instances of List or SortedList.
Now let's add the totaling capability to the SortedList class. To do this we will need to add a new variable, and we will also need to modify the Insert function so that each insertion adds to the total. The code is shown below:
In this version of the SortedList class we have added a new data member named total, a new member function GetTotal to retrieve the current total, and a new function Insert which overrides the existing Insert function. We have also modified the SortedList constructor so that it initializes total. Now whenever the SortedList class is used and the Insert function is called, the new version of the Insert function will be accessed instead of the old version in List. The same goes for the SortedInsert function as well--when it calls Insert it is calling the new version.
The code for the new Insert function is straightforward:
This function first adds the new value to the total. It then calls the old Insert function inherited from the base class so that the value is inserted in the list properly. The List:: specifies from which class in the hierarchy the Insert function should be chosen. This is only a two-level hierarchy so it is a simple decision here, but in a hierarchy that has several layers of inheritance you can use this technique to choose a specific function from many. It is this layering, and the ability to work and think in a multi-level inheritance hierarchy as shown here, that gives C++ its 3- dimensional feel.
What is a good way to create the new class in a object-oriented programming environment? One way to think about it is to think in a generic-to-specific way. For example, what is a multi-precision integer? It is simply a list of digits. Therefore, you can start by creating a generic list class that has all of the insertion features needed to implement a mint, and then layer the mint functionality on top of it.
How do we decide which features are needed in the list? A good way to do this is to think about what you will have to do with the digits in typical mint operations, and then use those thoughts to create the list class. Alternatively, you would have a list class laying around and you would simply build on top of it. Let's take the first approach since we don't have a good list class laying around.
How do you initialize a mint? The mint will start off containing no digits. We will then add one digit at a time to create the new mint. For the value 4,269 the mint would look like this:
Each square in this diagram represents one element in the list, and each element in the list contains an integer value between 0 and 9. At the list level we need to be able to add digits to the beginning or the end of the list, depending on where the initial value came from.
Now let's look at a simple addition, as shown in the figure below:
In order to implement addition we will want to start with the last digits of the two mints being summed, add them together, and insert the resulting digit in the new mint being formed as the sum. Then we will go to the previous two digits and do the same thing, and so on. We will therefore need an efficient way to move through the lists from end to beginning (for example, GetLast and GetPrevious functions), and we will also need a way to be able to tell when we have hit the beginning of the list (perhaps a return value from GetPrevious can indicate that the action is not possible, or a Size function can indicate how far to go).
From this discussion and our previous work with lists we can surmise that the list will probably need to have the following capabilities:
The code below implements the list:
This code should all be fairly straightforward to you at this point. List is simply a generic list of integers. A data member named pointer points to one of the elements in the list and is moved by the four Get... functions. Each of these functions returns 0 on success and 1 on failure (for example, if pointer is not on element 0 of the list then there is a previous element to get and GetPrevious function will return a 0). The two Add... functions add at the beginning and end of the list respectively--they currently contain no error checking. The AddToFront function contains an inherent inefficiency because it must move the entire contents of the array down one element for each insertion.
The Mint class inherits List and uses it to build the actual mint type. It implements two constructors (a default constructor that accepts no parameters and a second constructor that accepts a string and uses it to fill the list), as well as functions that add two mints and print a mint. The code is shown below:
The following main function tests the mint class by adding two numbers and printing the sum:
The constructors and the Print function are simple and straightforward. The Add function may remind you of your grade school days, because it is doing addition the old fashioned way. It starts with the last digits of the two numbers being summed, adds those digits, saves the result in the current mint, and remembers the carry value. It then moves forward through the list. Since it is likely that the two mints will not have an equal number of digits, the code must continually check to make sure that it has not run out of digits in one or the other mint. It does this using erra and errb. As soon as both mints have run out it checks carry and saves one last digit if necessary.
Running the test code you will see that the Mint class works as advertised and can add two numbers of up to 100 digits each. After you use the Mint class for awhile though you begin to see a problem with the Add function--there is no way to say something like "m = m + 1", or in the format necessary here "m.Add(m, one);" where one has been initialized to "1". The reason for this lies in the fact that Add must clear out the destination of the result before it can place a value into it, and this forces the loss of needed data in the case shown here.
The solution to this problem lies in the creation of a temporary holding value for the result during the actual addition. Then at the end of the function, the final result is copied into the current instance. The this pointer is used to solve the problem, as shown below:
In this version of Add a temporary value named x has been created. The results of the addition are placed into x digit by digit. The last line of the function copies x into the current instance. The this pointer is available in every instance of a class in C++--it points to the current instance. That is, this is a pointer that points to the data members (the structure) that make up the current instance. In this case we use this because it saves code. The alternative would be to replace the last line with:
The value *this is the structure pointed to by this, and it is more expedient to copy the whole structure at once.
As a final example of the Mint class, let's use it to implement a fibbinocci number finder. The fibbinocci sequence is as follows:
Each number in the sequence is the sum of the prior two numbers. In order to implement this feature we will need a way to check for equality in mints so that we can make a loop. The following member function can be added to the Mint class to check for equality between two mints:
Given the existence of this function, then the following code will find the 100th number in the fibbinocci sequence:
The code uses two values t1 and t2 to remember the previous two values. They are added together and then shifted down by one. The counter is then incremented and the loop continues until the counter has reached the desired value. Using this code, the 100th number was found to be 354,224,848,179,261,915,075.
Although we have accomplished our goal, the Mint class is not very well integrated into the language. We would like to use the "+" operator for addition and the "==" operator to check for equality. We will see how to do this in the next section.