CS247 Lecture 1

Abstract Data Type Allow us to hide complex details behind an interface. A client only needs to understand the interface to use a class, they are free to ignore the underlying implementation.

Examples:

• BST - client will call insert/delete/search - don’t need to worry about tree balancing.
• Dictionary - can simply insert/lookup values - no worries about internals,hash function being used, etc.

Ideally, use the compiler to enforce certain properties of the ADT. Example: Linked List ADT: One property we may wish to have is that all nodes are on the heap

Detecting issues at compiler-time ensure that users of our software never encounter this particular suite of run-time bugs. We wish to prevent tampering and forgery of our ADTs.

Forgery:

• creating invalid instances of an ADT. Tampering:
• Modifying a valid instance of an ADT to become invalid in an unexpected way.

Example: Rational ADT

#include <iostream>
using namespace
 
int main(){
	cout << "Enter a Rational #" << endl;
	Rational r,p,q; // Default ctor
	// Define what it means to read a rationa from cin
	cin >> r >> q;
	// Define what it means to add two rationals
	p = 1 + r;
	// Define what it means to print Rationals
	cout << a/r << endl;
	// Define copy ctor for Rationals
	Rational x{q};
}
 
// Defining the Rational class:
class Rational{
	int num, denom;
public:
	Rational(): num{0}, denom{1}{}
explicit Rational(int num): num{num}, denom{1}{}
	Rational(int num, int denom): num{num}, denom{denom}{}
};

What is Prevents implicit conversions. the explicit keywork?

• Used for single parameter constructors
• Prevents implicit conversions For example:

void f(Rational num) {
	...
}

Without the explicit keyword, this will compile f(247). However without the explicit keyword, this won’t work. You will need to write:

	f(Rational{247}); // With explicit, we must instead write this

Another example:

• Using explicit can be helpful to catch mistakes:

class Node{
	Node* next;
	int data;
public:
	Node(int data): data{data}, next{nullptr}{}
}
 
q(Node n){
	...
	q(4); // can't catch error
};

Another example: This works because std::String has a single-parameter ctor which takes in a char* and is non-explicit:

void f(std::string s){
	...
	f("hello world");
}

Does the Rational ADT need to be a class?

• Not necessarily
• ADTs are abstract - not tied to one particular implementation
• Could use a struct
• Classes are nicer:
  • Construction/destruction is guaranteed (on the stack)
  • Can enforce legal value ranges via access specifiers (public/private/protected)
• With a c struct: someone can easily set denom = 0. Not possible with our class: denom is private, we could add logic to our ctor to reject denom = 0.

This is an example of an Invariant: We gave Rational a default ctor - ctor that can be called with no arguments. Should all ADTs have a default ctor? Not necessarily - only if it makes sense.

Consider a Student ADT with name, id, birthday fields - no sensible defaults.

If you do not write any ctors at all, you get a compiler provided default ctor: (can be called with no arguments)

• Leaves primitive fields unitialized (garbage vales)
• Default constructs object fields. If you write any ctor yourself, the compiler provided ctor is not supplied.

Do we need 3 ctors?

• No - we can use default parameters to better code styles

Class Rational{
	int num, denom;
public:
	Rational(int num = 0, int denom = 1): num{num}, denom{denom}{}
}

Default parameters must be trailing Consider:

class Foo{
	int x, int y, int z;
public:
	Foo(string x = 0, int y)...
	Foo(int z);
};

If we were to call Foo{5} - which stor are we trying to call here? z = 5, or x = 0 and y = 5?

Ambiguous - won’t compile - default parameters must be trailing. Additionally - default parrameters only appear in the declaration, not the definition.

We;ve use the MIL - member initialization list to set our fields: What’s the difference between:

Rational(int num int denom): num{num}, denom{denom}{}
vs
Rational(int num, int denom){
	this->num = num;
	this->denom = denom;
}

In general, using the MIL is considered better. To understand why - think about object construction. Happens in 4 steps:

1. Space is allocated (stack or heap)
2. Call the superclass ctor
3. Initizalize fiels via MIL
4. Run the ctor body

Next: CS247 Lecture 2