10.3 Abstract Data Types

We all know — the Times knows — but we pretend we don’t.

VIRGINIA WOOLF, Monday or Tuesday

A data type, such as the type int, has certain specified values, such as 0, 1, −1, 2, and so forth. You tend to think of the data type as being these values, but the operations on these values are just as important as the values. Without the operations, you could do nothing of interest with the values. The operations for the type int consist of +, −, *, /, %, and a few other operators and predefined library functions. You should not think of a data type as being simply a collection of values. A data type consists of a collection of values together with a set of basic operations defined on those values.

A data type is called an abstract data type (abbreviated ADT) if the programmers who use the type do not have access to the details of how the values and operations are implemented. The predefined types, such as int, are abstract data types (ADTs). You do not know how the operations, such as + and *, are implemented for the type int. Even if you did know, you would not use this information in any C++ program.

Programmer-defined types, such as the structure types and class types, are not automatically ADTs. Unless they are defined and used with care, programmer-defined types can be used in unintuitive ways that make a program difficult to understand and difficult to modify. The best way to avoid these problems is to make sure all the data types that you define are ADTs. The way that you do this in C++ is to use classes, but not every class is an ADT. To make it an ADT you must define the class in a certain way, and that is the topic of the next subsection.

Classes to Produce Abstract Data Types

A class is a type that you define, as opposed to the types, such as int and char, that are already defined for you. A value for a class type is the set of values of the member variables. For example, a value for the type BankAccount in Display 10.6 consists of two numbers of type double. For easy reference, we repeat the class definition (omitting only the comments):

class BankAccount
{
public:
    BankAccount(int dollars, int cents, double rate);
    BankAccount(int dollars, double rate);
    BankAccount();
    void set(int dollars, int cents, double rate);
    void set(int dollars, double rate);
    void update();
    double getBalance();
    double getRate();
    void output(ostream& outs);
private:
    double balance;
    double interestRate;
    double fraction(double percent);
};

The programmer who uses the type BankAccount need not know how you implemented the definition of BankAccount::update or any of the other member functions. The function definition for the member function BankAccount::update that we used is as follows:

void BankAccount::update()
{
    balance = balance + fraction(interestRate) * balance;
}

However, we could have dispensed with the private function fraction and implemented the member function update with the following slightly more complicated formula:

void BankAccount::update()
{
    balance = balance + (interestRate / 100.0) * balance;
}

The programmer who uses the class BankAccount need not be concerned with which implementation of update we used, since both implementations have the same effect.

Similarly, the programmer who uses the class BankAccount need not be concerned about how the values of the class are implemented. We chose to implement the values as two values of type double. If vacationSavings is an object of type BankAccount, the value of vacationSavings consists of the two values of type double stored in the following two member variables:

vacationSavings.balance
vacationSavings.interestRate

However, you do not want to think of the value of the object vacationSavings as two numbers of type double, such as 1.3546e + 2 and 4.5. You want to think of the value of vacationSavings as the single entry

Account balance $135.46
Interest rate 4.50%

That is why our implementation of BankAccount::output writes the class value in this format.

The fact that we chose to implement this BankAccount value as the two double values 1.3546e + 2 and 4.5 is an implementation detail. We could instead have implemented this BankAccount value as the two int values 135 and 46 (for the dollars and cents part of the balance) and the single value 0.045 of type double. The value 0.045 is simply 4.5% converted to a fraction, which might be a more useful way to implement a percentage figure. After all, in order to compute interest on the account we convert a percentage to just such a fraction. With this alternative implementation of the class BankAccount, the public members would remain unchanged but the private members would change to the following:

class BankAccount
{
public:
        <This part is exactly the same as before>
private:
    int dollarsPart;
    int centsPart;
    double interestRate;
    double fraction(double percent);
};

We would need to change the member function definitions to match this change, but that is easy to do. For example, the function definitions for getBalance and one version of the constructor could be changed to the following:

double BankAccount::getBalance()
{
    return (dollarsPart + 0.01 * centsPart);
}
BankAccount::BankAccount(int dollars, int cents, double rate)
{
    if ((dollars < 0) || (cents < 0) || (rate < 0))
    {
        cout << "Illegal values for money or interest rate.\n";
        exit(1);
    }
    dollarsPart = dollars;
    centsPart = cents;
    interestRate = rate;
}

Similarly, each of the other member functions could be redefined to accommodate this new way of storing the account balance and the interest rate.

Notice that even though the user may think of the account balance as a single number, that does not mean the implementation has to be a single number of type double. You have just seen that it could, for example, be two numbers of type int. The programmer who uses the type BankAccount need not know any of this detail about how the values of the type BankAccount are implemented.

How to write an ADT

These comments about the type BankAccount illustrate the basic technique for defining a class so that it will be an abstract data type. In order to define a class so that it is an abstract data type, you need to separate the specification of how the type is used by a programmer from the details of how the type is implemented. The separation should be so complete that you can change the implementation of the class without needing to make any changes in any program that uses the class ADT. One way to ensure this separation is to follow these rules:

1. Make all the member variables private members of the class.

2. Make each of the basic operations that the programmer needs a public member function of the class, and fully specify how to use each such public member function.

3. Make any helping functions private member functions.

In Chapters 11 and 12 you will learn some alternative approaches to defining ADTs, but these three rules are one common way to ensure that a class is an abstract data type.

The interface of an ADT tells you how to use the ADT in your program. When you define an ADT as a C++ class, the interface consists of the public member functions of the class along with the comments that tell you how to use these public member functions. The interface of the ADT should be all you need to know in order to use the ADT in your program.

The implementation of the ADT tells how this interface is realized as C++ code. The implementation of the ADT consists of the private members of the class and the definitions of both the public and private member functions. Although you need the implementation in order to run a program that uses the ADT, you should not need to know anything about the implementation in order to write the rest of a program that uses the ADT; that is, you should not need to know anything about the implementation in order to write the main part of the program and to write any nonmember functions used by the main part of the program. The situation is similar to what we advocated for ordinary function definitions in Chapters 4 and 5. The implementation of an ADT, like the implementation of an ordinary function, should be thought of as being in a black box that you cannot see inside.

Separate interface and implementation

Separate Interface and Implementation

In Chapter 12 you will learn how to place the interface and implementation of an ADT in files separate from each other and separate from the programs that use the ADT. That way a programmer who uses the ADT literally does not see the implementation. Until then, we will place all of the details about our ADT classes in the same file as the main part of our program, but we still think of the interface (given in the public section of the class definitions) and the implementation (the private section of the class definition and the member function definitions) as separate parts of the ADT. We will strive to write our ADTs so that the user of the ADT need only know about the interface of the ADT and need not know anything about the implementation. To be sure you are defining your ADTs this way, simply make sure that if you change the implementation of your ADT, your program will still work without your needing to change any other part of the program. This is illustrated in the next Programming Example.

The most obvious benefit you derive from making your classes ADTs is that you can change the implementation without needing to change the other parts of your program. But ADTs provide more benefits than that. If you make your classes ADTs, you can divide work among different programmers, with one programmer designing and writing the ADT and other programmers using the ADT. Even if you are the only programmer working on a project, you have divided one larger task into two smaller tasks, which makes your program easier to design and easier to debug.

Programming Example Alternative Implementation of a Class

Display 10.7 contains the alternative implementation of the ADT class BankAccount discussed in the previous subsection. In this version, the data for a bank account is implemented as three member values: one for the dollars part of the account balance, one for the cents part of the account balance, and one for the interest rate.

Display 10.7 Alternative BankAccount Class Implementation

10.3-4 Full Alternative Text

10.3-4 Full Alternative Text

Notice that, although both the implementation in Display 10.6 and the implementation in Display 10.7 each have a member variable called interestRate, the value stored is slightly different in the two implementations. If the account pays interest at a rate of 4.7%, then in the implementation in Display 10.6 (which is basically the same as the one in Display 10.5), the value of interestRate is 4.7. However, in the implementation in Display 10.7, the value of interestRate would be 0.047. This alternative implementation, shown in Display 10.7, stores the interest rate as a fraction rather than as a percentage figure. The basic difference in this new implementation is that when an interest rate is set, the function fraction is used to immediately convert the interest rate to a fraction. Hence, in this new implementation the private member function fraction is used in the definitions of constructors, but it is not needed in the definition of the member function update because the value in the member variable interestRate has already been converted to a fraction. In the old implementation (shown in Display 10.5 and Display 10.6), the situation was just the reverse. In the old implementation, the private member function fraction was not used in the definition of constructors, but was used in the definition of update.

The public interface is not changed

Although we have changed the private members of the class BankAccount, we have not changed anything in the public section of the class definition. The public member functions have the same function declarations and they behave exactly as they did in the old version of the ADT class given in Display 10.6. For example, although this new implementation stores a percentage such as 4.7% as the fraction 0.047, the member function getRate still returns the value 4.7, just as it would for the old implementation in Display 10.5. Similarly, the member function getBalance returns a single value of type double, which gives the balance as a number with a decimal point, just as it did in the old implementation in Display 10.5. This is true even though the balance is now stored in two member variables of type int, rather than in a single member variable of type double (as in the old versions).

Changing private member functions

Notice that there is an important difference between how you treat the public member functions and how you treat the private member functions. If you want to preserve the interface of an ADT class so that any programs that use it need not change (other than changing the definitions of the class and its member functions), then you must leave the public member function declarations unchanged. However, you are free to add, delete, or change any of the private member functions. In this example, we have added one additional private function called percent, which is the inverse of the function fraction. The function fraction converts a percentage to a fraction, and the function percent converts a fraction back to a percentage. For example, fraction(4.7) returns 0.047, and percent(0.047) returns 4.7.

Information Hiding

We discussed information hiding when we introduced functions in Chapter 3. We said that information hiding, as applied to functions, means that you should write your functions so that they could be used as black boxes, that is, so that the programmer who uses the function need not know any details about how the function is implemented. This principle means that all the programmer who uses a function needs to know is the function declaration and the accompanying comment that explains how to use the function. The use of private member variables and private member functions in the definition of an abstract data type is another way to implement information hiding, but now we apply the principle to data values as well as to functions.

Self-Test Exercises

25. When you define an ADT as a C++ class, should you make the member variables public or private? Should you make the member functions public or private?

26. When you define an ADT as a C++ class, what items are considered part of the interface for the ADT? What items are considered part of the implementation for the ADT?

27. Suppose your friend defines an ADT as a C++ class in the way we described in Section 10.3. You are given the task of writing a program that uses this ADT. That is, you must write the main part of the program as well as any nonmember functions that are used in the main part of the program. The ADT is very long and you do not have a lot of time to write this program. What parts of the ADT do you need to read and what parts can you safely ignore?

28. Redo the three- and two-parameter constructors in Display 10.7 so that all member variables are set using a constructor initialization section.