Abstract data type. Classes

Abstract data types. Classes

Abstract data types.

An abstract data type (ADT) describes an interface of a type, abstracting away the implementation details of this type.

ADT provides an inteface to interact with the data type, so that the user does not have to know, and does not have to worry about the particular details of the implementation of the data type.

Preferably, the implementation details should not be hidden from the user, so they don’t access them intentionally, or unintentionally.

Example: Set of integers `IntSet`

Interface:

empty(s) makes the set s empty
add(s,v) inserts element v
remove(s,v) removes v from the set
member(s, v) returns true if v belongs to s, otherwise false

Here is an implementation using simple struct:

#include <iostream>
using namespace std;

struct IntSet {
  static const int N = 1024;
  int arr[N];
  int card;
};

// empties the set
void empty(IntSet &s);
// returns true if v is in the set, otherwise returns fls
bool member(IntSet &s, int v);
// adds element v to the set (returns true if succeeded)
void add(IntSet &s, int v);
// removes v from the set (retruns true if succeeded)
void remove(IntSet &s, int v);


int main () {
  IntSet s;
  empty(s);

  add(s, 10);
  add(s, 20);
  add(s, 15);
  add(s, 5);
  add(s, 5);
  add(s, 15);
  add(s, 7);
  remove(s, 15);

  for(int i = 0; i < 25; i++) {
    cout << i << " ";
    
    if (member(s, i)) cout << "yes";

    cout << endl;
  }
}


void empty(IntSet &s) {
  s.card = 0;
}

bool member(IntSet &s, int v) {
  for (int i = 0; i < s.card; i++) {
    if ( s.arr[i] == v ) return true;
  }
  return false;
}

void add(IntSet &s, int v) {
  if ( ! member(s,v) ) {
    s.arr[s.card] = v;
    s.card ++;
  }
}

void remove(IntSet &s, int v) {
  for (int i = 0; i < s.card; i++) {
    if ( s.arr[i] == v ) {
      // found v in arr
      for (int j = i; j < s.card; j++) {
        s.arr[j] = s.arr[j+1];
      }
      s.card --;
      break;
    }
  }
}

Unfortunately, this implementation does not protect the members of the structure, such as card and arr from being edited directly, for example like this:

  IntSet s;
  empty(s);

  s.arr[0] = 14523;
  s.card++;

We would like to protect those member variables from being used directly, making the user rely exclusively on the interface functions.

In C++, the idiomatic way to resolve this issue is to use classes.

Classes

Struct = collection member variables.

Class = member variables + member functions + access modifiers.

A 2D vector implemented as a structure

#include <iostream>
#include <cmath>
using namespace std;

struct Vec {
  double x;
  double y;
};

double length(Vec v);

int main() {
  Vec v = {10.5, -7.0};

  cout << "length = " << length(v) << endl;

  cout << "x = " << v.x << endl;

  cout << "y = " << v.y << endl;
}

double length(Vec v) {
  return sqrt(v.x*v.x + v.y*v.y);
}

length = 12.6194
x = 10.5
y = -7

A 2D vector implemented as a class

#include <iostream>
#include <cmath>
using namespace std;

class VecClass {
private:
  double x;
  double y;

public:
  double length();
  void set(double x, double y);
  double get_x();
  double get_y();
};

int main() {
  VecClass v;
  v.set(10.5, -7.0);

  cout << "length = " << v.length() << endl;

  cout << "x = " << v.get_x() << endl;

  cout << "y = " << v.get_y() << endl;
}


double VecClass::length() {
  return sqrt(x*x + y*y);
}

void VecClass::set(double xv, double yv) {
  x = xv;
  y = yv;
}

double VecClass::get_x() {
  return x;
}

double VecClass::get_y() {
  return y;
}

length = 12.6194
x = 10.5
y = -7

Set of integers `IntSet` implemented as a class

#include <iostream>
using namespace std;

class IntSet {
private:
  static const int N = 1024; // max cardinality
  int card; // cardinality
  int arr[N];

public:
  void empty();
  bool member(int v);
  void add(int v);
  void remove(int v);
  int get_card();
};

int main () {
  IntSet s;
  s.empty();

  s.add(10);
  s.add(20);
  s.add(15);
  s.add(5);
  s.add(5);
  s.add(15);
  s.add(7);
  s.remove(15);
  
  for(int i = 0; i < 25; i++) {
    cout << i << " ";
    
    if (s.member(i)) cout << "yes";

    cout << endl;
  }
}

void IntSet::empty() {
  card = 0;
}

bool IntSet::member(int v) {
  for (int i = 0; i < card; i++) {
    if ( arr[i] == v ) return true;
  }
  return false;
}

void IntSet::add(int v) {
  if ( ! member(v) ) {
    arr[card] = v;
    card ++;
  }
}

void IntSet::remove(int v) {
  for (int i = 0; i < card; i++) {
    if ( arr[i] == v ) {
      // found v in arr
      for (int j = i; j < card; j++) {
        arr[j] = arr[j+1];
      }
      card --;
      break;
    }
  }
}

int IntSet::get_card() {
  return card;
}

Abstract data types. Classes