Computer Algorithms I CS 305 Class Notes

Lecture Notes for Computer Algorithms I

11 September 2003 - Record Data Types

Using arrays in the student problem.
- Arrays give us a straightforward way to implement the student problem.
  - Each student-record part is stored in a separate array.
```
const unsigned s_cnt = 3000;
string   name[s_cnt];
unsigned year[s_cnt];
bool     graduate[s_cnt];
// and so on.
```
- Each student is a slice through the component arrays.
- This is useful but cumbersome.
  - Parameter lists can get huge unless the component arrays are global.
    - And global component arrays are another problem.
Records
- A record is a slice at a constant index through a group of arrays.
- Each element of the arrays becomes a field of the record.
  - The field type is the element type.
  - The field name is the array name, or any other unique (within the record) name.
- The record type is the collection of field types.
  - The field types are ordered; the record type { int,string } is not the same as the record type { string,int }.
- Record field values are accessed using the dot operator.
  - With syntax record-value . field-name
Unions
- Suppose I want to deal with students and their cars.
  - Student and car records probably have common fields.
    - Name, residence, class, registered.
  - Duplicating those fields is both wasteful and dangerous.
    - Dangerous because changes have to be made in several places.
- Sharing the common parts of the two records can solve these problems.
- A union is a type of record that can space-efficiently share common fields among different records.
  - The different parts are called the variants.
    - All variants overlay themselves, taking up space equal to the largest of them.
  - There may also be a tag to distinguish the variants.
- In general, don't use unions.
  - In some languages they're unsafe, in others they're cumbersome.
    - Unsafe becasue they can subvert the type system.
    - Combersome because type-safe unions require handling all the variants all the time.
  - Objects and inheritance provide facilities to to much the same thing as unions.
  - Containment is another approach to implementing union-like data structures.

This page last modified on 16 September 2003.