5. Absract Data Types
 

5.1  What is an Abstract Data Type?

A type that is defined entirely by a set of operations is called an "Abstract Data Type", or ADT. The operations provide a resentation-independent specification. C++ supports abstract data types by allowing the user to define new types beyond the primitive types. The data type is defined via a class.

The hiding of the representation is consistent with the use of primitive types in a language. A programmer need not be aware of  the internal representation of the primitive objects. Integers might be  represented as two's complement binary numbers or binary-coded decimal digits. In most languages, there is no way of finding out the particular representation without investigating the implementation.

There are two major advantages to defining a type as an abstract data type:

• The operations can be itemized in a list and made clear to the user.
• The separation of operations from representation results in data independence. The representation can be changed without corresponding changes in the main part of the program, and the correctness of the program will be unaffected.

The concept of ADT is developed in the mathematical research. An ADT consists of set of elements together with operations on the sets and axioms to descibe the operations. This constitutes an algebra.

5.2  Rational Number Example

The first example is a class for rational numbers. The idea of this program is drawn from [Budd, 1994].  C++ does not have the rational number as a built-in type. In the implementation of the rational number below, we provide all arithmetic operations usually used and comparison operations in the same way C++ provides for integers. By using this class, a user can manipulate rational number just like integers, including the use of input/output streams.

When the  example program is compiled and executed, the following output will appear.

a = 3
b = 3/4
c = 1/2
b + c = 5/4
b - c = 1/4
x = 1
c / x = 1/2
x = 6
a / x == c is true
-x = -6

The class is as follows:
 

#include <iostream.h> #include <string.h> class rational { public:    rational();    rational(int);    rational(int, int);    rational(rational&);    int numerator();    int denominator();    void operator = (rational&);    rational operator + (rational&);    rational operator - (rational&);    rational operator * (rational&);    rational operator / (rational&);    rational operator - (); private:    int top;    int bottom;    void normalize(); }; The following member functions are quite simple. rational::rational() {top = 0; bottom = 1;} rational::rational(int numerator) {top = numerator; bottom = 1;} rational::rational(int numerator, int denominator) {    top = numerator; bottom = denominator; normalize();} rational::rational(rational& value) {    top = value.numerator(); bottom = value.denominator();} int rational::numerator()   {return top;} int rational::denominator() {return bottom;} void rational::operator = (rational& right) {    top    = right.numerator();    bottom = right.denominator(); } To define the remaining member functions, we first give a definition of the private member  function for normalizing a rational member. For instance, the number 9/12 is normalized as 3/4. unsigned int gcd(unsigned int n, unsigned int m) {    if (n == 0) return m;    if (m == 0) return n;    while (m != n) {       if (n > m) n = n - m;       else m = m - n;    }    return n; } void rational::normalize() {    int d, sign;    sign = 1;    if (top < 0) {      sign = -1;      top = -top;    }    d = gcd(top, bottom);    top = sign*(top / d);    bottom = bottom / d; } rational rational::operator + (rational& right) {    rational result;    result.top    = (this.numerator()*right.denominator() +                    right.numerator()*this.denominator());    result.bottom = this.denominator()*right.denominator();    result.normalize();    return result; } The arithmetic operators given as member functions are straight forward. Notice that the first operand for  each operator is assumed. This is because an expression like A + B is really a shorthand for A. "+" (B)  where "+" is a member function for an object A of class rational. B is the argument to "+" which is added to A. The "this" in the definitions refgers to first operand, for example the A in A + B. rational rational::operator - (rational& right) {    rational result;    result.top    = (this.numerator()*right.denominator() -                    right.numerator()*this.denominator());    result.bottom = this.denominator()*right.denominator();    result.normalize();    return result; } rational rational::operator * (rational& right) {    rational result;    result.top    = this.numerator()*right.numerator();    result.bottom = this.denominator()*right.denominator();    result.normalize();    return result; } rational rational::operator / (rational& right) {    rational result;    result.top    = this.numerator()*right.denominator();    result.bottom = this.denominator()*right.numerator();    result.normalize();    return result; } rational rational::operator - () {    rational result;    result.top    = (-1) * this.numerator();    result.bottom = this.denominator();    return result; } The equality and redirection operators are not defined as member functions. They are given  as overloaded binary operators, and hence take two arguments. int operator == (rational& left, rational& right) {    return (left.numerator()*right.denominator() ==            right.numerator()*left.denominator()); } ostream& operator << (ostream& outstream, rational& value) {    outstream  << value.numerator();    if (value.denominator() != 1)       outstream << '/' << value.denominator();    return outstream; } Finally, the main program itself. main() {    rational x;    rational a(3);    rational b(3, 4);    rational c(2, 4);    cout << "a = "     << a     << endl;    cout << "b = "     << b     << endl;    cout << "c = "     << c     << endl;    cout << "b + c = " << b + c << endl;    cout << "b - c = " << b - c << endl;    x = b - c;    x = x + b;    cout << "x = "     << x     << endl;    cout << "c / x = " << c / x << endl;    x = 6;    cout << "x = "     << x     << endl;    cout << "a / x == c is ";    if ((a / x) == c)  cout  << "true\n";    else               cout  << "false\n";    cout << "-x = "    << -x    << endl; }

In order to make the program concise, the example only contains one relational operator, ==. The other relational operators can be defined similarly as follows:
 

int operator < (rational& left, rational& right) {    return (left.numerator()*right.denominator() <            right.numerator()*left.denominator());  } int operator <= (rational& left, rational& right) {    return (left.numerator()*right.denominator() <=            right.numerator()*left.denominator());  } int operator > (rational& left, rational& right) {    return (left.numerator()*right.denominator() >            right.numerator()*left.denominator());  } int operator >= (rational& left, rational& right) {    return (left.numerator()*right.denominator() >=            right.numerator()*left.denominator());  } int operator != (rational& left, rational& right) {    return (left.numerator()*right.denominator() !=            right.numerator()*left.denominator());  }

5.3  Bag Example

The next example is a bag class. A bag is simple ADT for a collection of items where duplicates may be present. This example is just for integers, but this container can be implemented in more generic way by using a C++ template. Such generic container classes using C++ templates are shown in the chapter, Templates. The idea of this program is drawn from [Main & Savitch, 1996].

In this example, the user can put any integers. Unlike a set, a bag can contain duplicate elements, for example, {6 9 4 6 12 1 9}. As shown in the class definition, the implementation is hidden and only interfaces, i.e. how to use this bag, are presented.

As mentioned earlier, an abstract data type contains data structures and its manipulating functions. Those functions are called "member functions." In our example, the member functions are written outside of the scope of the class definition. They can also be written inside of the class definition, as shown in later examples.

After compiling this example program, an execution dialog is as follows. Note that the bag contains two 2’s. One is later removed, and the other remains.

Type any number you like.
Type -1 when you are done.
1 2 3 2
-1
In the bag: 1 2 3 2
Type number you want to remove.
Type -1 when you want to exit.
3
OK, removed it.
2
OK, removed it.
1
OK, removed it.
-1
In the bag: 2
Program exited.

The class definition of this bag example is as follows:
 

class bag { public:    enum {CAPACITY = 100};    bag() {used = 0;}    int size();    int occurrences(int& target);    void insert(int&);    void remove(int&);    void operator += (bag&);    void show(); private:    int data[CAPACITY];    int used; }; int bag::size() {return used;} int bag::occurrences(int& target) {    int i, result;    result = 0;    for (i = 0; i < used; i++)       if (target == data[i])          result++;    return result; } void bag::insert(int& entry) {    data[used] = entry;    used++; } void bag::remove(int& target) {    int i;    i = 0;    while ((i < used) && (data[i] != target)) { i++; }      if (i != used) {          // target is in the Bag at data[i].         used--;                // So, reduce used by 1 and         data[i] = data[used];  // copy the last item onto data[i].    } } void bag::operator += (bag& addend) {    int i;    int j;    j = addend.size();    for (i = 0; i < j; i++) {       data[used] = addend.data[i];       used++;    } } void bag::show() {    int i;    cout << "In the bag: ";    for (i = 0; i < used; i++)       cout << data[i] << " ";    cout << endl; } bag operator + (bag& b1, bag& b2) {    bag result;    result = b1;    result = result + b2;    return result; }

The main program using this class is as follows.
 

#include <iostream.h> main() {    int const sentinel = -1;    bag mybag;    int i;    // Put numbers into mybag.    cout << "Type any number you like.\n";    cout << "Type -1 when you are done.\n";    cin >> i;    while (i != sentinel) {       if (mybag.size() < mybag.CAPACITY)          mybag.insert(i);       else          cout << "run out of room; can't put in any more.\n";       cin >> i;    }    // Check numbers out from mybag.    mybag.show();    cout << "Type number you want to remove.\n";    cout << "Type -1 when you want to exit.\n";    cin >> i;    while ((mybag.size() > 0) && (i != sentinel)){       if (mybag.occurrences(i) == 0)          cout << "No, that number is not in!\n";       else {          cout << "OK, removed it.\n";          mybag.remove(i);       }       cin >> i;    }    mybag.show();    cout << "Program exited.\n"; }

References

1. [Budd, 1994] Timothy Budd. Classic Data structures in C++. Addison-Wesley Publishing, 1994.
2. [Hein, 1996] James L. Hein. Discrete Structures, Logic, and Computability, Jones and Bartlett Publishers, 1996.
3. [Ledgard, 1996] Henry F. Ledgard. The Little Book of Object-Oriented Programming. Prentice-Hall, 1996.
4. [Main et al, 1997] Michael Main, Walter Savitch. Data Structures and Other Objects using C++. Addison-Wesley Publishing, 1997.[Stroustrup, 1988]
5. Bjarne Stroustrup. What Is Object-Oriented Programming. IEEE Software, May 1988 (1991 revised version, AT&T.)