ve280-final-review

ve280-final.md

#Ve280 Final Review

Subtype and Inherit

Subtype (abstract)

the children S inherits the base type T (supertype), written as S<:T.

• Add one or more operations. For MaxIntSet <: IntSet, we add a new method MaxIntSet::max().
• Strengthen the postcondition of one or more operations. We can just print something (do something more than origin).
• Weaken the precondition of one or more operations. For SafeMaxIntSet <: MaxIntSet, it is okay to SafeMaxIntSet::insert() and it will throw an exception. For MaxIntSet::insert(), it is not allowed.

Can use subtype instead of an original argument.

C++ Inherit

• Create subtype by C++ inheriting
• Subclass cannot always be subtype. In this situation, call it by father's pointer will fail. Solution: virtual function to override it.

class bar : public foo {};
bar b;
foo &fr = b; // legal
foo *fp = &b; // legal

foo f;
bar &br = f; // illegal
bar &bp = *f; // illegal

It is legal because fp->method is legal for the subtype.

• Next idea. Abstract base class and interface.
• For interface, only public methods.

class IntSetFull {};
class IntSet {
public:
	virtual void insert(int v) = 0;
    virtual void remove(int v) = 0;
    virtual bool query(int v) = 0;
    virtual int size() = 0;
};

class IntSetImpl : public IntSet {
	// implementation
};

static IntSetImpl impl;
IntSet *getIntSet() {
	return &impl;
}

• Without virtual, the derived class cannot override (call by pointer).
• General Idea
  • constructor not virtual
  • destructor virtual
• pure virtual virtual void func() = 0;
• there is a keyword override
• Slide14 - P51

Representation Invariants

• Based on some invariants first.
• For each method, return to following there invariants finally.

Operator Overload

• Assignment operator
  • IntSet &operator= (const IntSet &is);
  • return by reference because we want x = y = z.
• + operator
  • IntSet operator+ (const IntSet &is);
  • because the return value is a new value.

Dynamic Allocation

new and delete

• decide how big/how long
• new returns a pointer
• delete => memory leak
• for array
  • int *a = new int[n]
  • deleta[] a
• copy problem
  • only copy the pointer because the pointer is actully properties of the class. Data are on the heap.
  • Copy constructor to deep copy. IntSet(const IntSet &is). Without reference, it is endless loop because we need a copy to pass by value.
• for class with new property, usually need overload =, copy and destructor.

class IntSet {
public:
	IntSet() {};
    IntSet(const IntSet &is) {}; // copy
    IntSet &operator= (const IntSet &is) {};
    ~IntSet() {};
};

valgrind

apt-get install valgrind
valgrind --leak-check=full ./program <args>

Template

template <class T>
class List {

};

template <class T>
List<T> &List<T>::operator= (const List &l) {
	//
}

Exam

• single
  • function declare
  • concept
• practice
  • what's the error (unnec to fix)
• read program
  • write the output
• implement
  • pseudocode