Implementing ADTs in C++

Tom Kelliher, CS18

Apr. 24, 1996

ADT Example: Employee List

Fields:

• first name --- arbitrary length.
• last name --- arbitrary length.
• department code --- at most 150 departments
• Annual salary --- at most $1,000,000,000 (future growth)
• Manager --- pointer to manager record
• Committee codes --- list of committee memberships (no limit), at most 1,000 committees

Design goals:

• Maintain all employee records
• Minimize memory usage
• Exact representation of numeric values
• Controlled modification through ADT operations only

Common Implementation Details

struct committeeList
{
   unsigned short committeeCode;
   struct committeeList*  next;
};

struct employeeRecord
{
   char* firstName;
   char* lastName;
   unsigned char deptCode;
   long salary;
   struct employeeRecord* manager;
   struct committeList* committees;
   struct employeeRecord* next;
};

ADT employee list operations?

• create
• destroy
• addEmployee
• deleteEmployee
• retrieveEmployee
• displayEmployee
• modifyEmployeeSalary
• addEmployeeToCommittee
• ...

Implementing ADTs in C

Create:

struct employeeRecord* employees = NULL;

Where is the ``wall?''

What information is hidden?

Kludge Information Hiding in C

• Separate modules ( .c files)
• Static globals
• Interface in .h file
• Implementation in separate .c file

Skeleton of main module:

#include "list.h"
...

main(){

create();
addEmployee(...);
...
}

Skeleton of list.h:

/* definitions for committeeList, employeeRecord structs */

int create(void);
int destroy(void);
int addEmployee(<formals>);
...

Skeleton of list.c:

#include "list.h"

static struct employeeRecord* employees;

/* definitions for ADT operations */

Three files:

• main.c
• list.c
• list.h

Implementing ADTs in C++

Create:

EmployeeList employees;   // call constructor

Where is the ``wall?''

What information is hidden?

Information Hiding in C++

• class
• private, public, protected
• Interface in .h file
• Implementation in separate .cc file

Skeleton of main module:

#include "list.h"
...

main(){

EmployeeList employees;
employees.addEmployee(...);
...
}

Skeleton of list.h:

// definitions for committeeList, employeeRecord structs

class EmployeeList
{
 public:
   EmployeeList(void);   // constructor
   ~EmployeeList(void);  // destructor
   int addEmployee(<formals>);
   ...
 private:
   employeeRecord* list;
   ... other hidden members or methods
};

Skeleton of list.cc:

#include "list.h"

EmployeeList::EmployeeList(void)
{
}

EmployeeList::~EmployeeList(void)
{
}

EmployeeList::addEmployee(<formals>)
{
}

Classes in C++

Similarity to Structures

struct foo
{
   int this;
   char that;
};

foo bar;

class Foo
{
 public:
   foo();
   ~foo();
   char moreFoo(int, int);

 private:
   int allMyFoo[FOO_AMOUNT];
   int hiddenFoo(int);
};
Foo bar;

Methods

• Member functions
• ADT operations, private operations

Linking Methods to Classes

• :: --- scope resolution operator

• className::methodName(<formals>)
  {
  }
  

Special Methods

• Constructor
• Destructor
• Default constructor/destructor
• Shallow/deep copy
• Copy constructor:

  ClassName::ClassName(const ClassName&)
  

Member Access

• Private
• Public
• What about structures?