CS 247

#include <iostream>
using namespace std;

int main() {
    Rational r, s;
    cout << "Enter rational number (a/b): ";
    cin >> r;
    cout << "Enter rational number (a/b): ";
    cin >> s;

    Rational t(r + s);
    cout << r + s << endl;
    cout << r * s << endl;
    cout << r == s << endl;
}

Rules for Function Overloading

Accessors (getters): Methods that return the value of a member field.
Mutators (setters) :Methods that allow for the setting of member fields.

These restrict the usage of member fields to only those we give access to through the public interface. They also allow usage of member fields only under our ADT’s terms / supervision.

Common Naming Conventions

Should it be a member?

Only if it has to be.

Classes can also be friends. This is often used when we have nested classes. Alternatively, if nested class is private, it could just be a struct with full public visibility.

class Stack {
public:
    Stack();
    ~Stack();
    void push(int n);
    int pop();
    int peek();

    class Node {
        friend class Stack;
    public:
        Node(int data, Node *next);
        Node(const Node& other);
        Node &operator=(const Node &other);
        ~Node();
    private:
        int data_;
        Node *next_;
    };

private:
    Node *top_;
};

Node can be private (and should be in this case) but there are some cases in which the we want the user to access the class but not the constructor (we can just make the constructor private).

Node::Node(int data, Node *next) : data_(data), next_(next) {}

// Built in copy-constructor copies all values (byte-wise) of built in types and for any object fields, calls copy-constructor. For our case, it would only be a shallow copy (next node would be shared).
Node::Node(const Node &other) : data_{data}, next_{other.next_ ? new Node(*other.next_) : nullptr} {}

Node& Node::operator=(const Node &other) {
    // Self-assignment check.
    if (this == &other) return *this;

    // We need to allocate the memory before just in case new throws an exception.
    Node *tmp = other.next_ ? new Node(*other.next_) : nullptr;

    data_ = other.data_;
    delete next;
    next_ = tmp;

    return *this;
}

Node::~Node() {
    // Calling delete on nullptr is safe
    delete next_;
}

Copy and Swap Idiom

class Node {
    ...
private:
    void swap(Node &n);
}
#include <utility>

void Node::swap(Node &other) {
    std::swap(data_, other.data_);
    std::swap(next_, other.next_);
}

Node& Node::operator=(const Node &other) {
    // Destructor for tmp will get called which does the clean-up for us.
    Node tmp{other};
    swap(tmp);
    return *this;
}

Lvalue References

Node plusOne(Node n) {
    for (Node *p = &n; p; p = p->next()) {
        p->dataIs(p->data() + 1);
    }
    return n;
}
int main() {
    Node n = new Node{0, new Node{1, new Node{2, nullptr}}};
    // m will have to be deep copied from plusOne(n).
    Node m = plusOne(n);
}

lvalue is anything with a memory address.
rvalues are temporary objects.

To create a reference to an rvalue, you use &&. Now, we have a new important constructor and assignment operator.

class Node {
    ...
    Node(Node &&other);
    Node &operator=(Node &&other);
};

Node::Node(Node &&other) : data_(other.data_), next_(other.next_) {
    // Need to set to nullptr so that the destructor doesn't destroy the data we stole.
    other.next_ = nullptr;
}

Node & Node::operator=(Node &&other) {
    swap(other);
    return *this;
}

C++ Gives You

  1. Default constructor (disappears as soon as any other constructor is written).
  2. Copy constructor (copies all fields).
  3. Destructor (does nothing).
  4. Copy assignment operator (copy assign all fields).
  5. Move constructor (identical to built in copy constructor, disappears if you write a copy constructor).
  6. Move assignment operator (same thing but with copy assignment operator).

When Are Defaults Insufficient?

Compilers can leave out copy / move constructors and call the basic constructor in the right memory location.

Entity vs. Value Objects

Does the object represent something in the real world or is it just an attribute that describes the state?

Entity Object

Examples:

Physical objects: airplane, runway, taxiway.
People: passengers, booking attendant.
Records: customer info, flight schedule, boarding pass.
Transactions: reservations, cancellations, reciepts.

Value Object

Example: Consider a video blackgack game. Which of the following should be implemented as entity or value objects?

The distinction between entity and value objects is important because it defines how we use the object, and in turn, how we write the class.

Design of Entity ADTs

An operation on an entity object should represent a real life event.

Prohibiting Copy Constructor

class X {
public:
    X(const & x) = delete;
    X & operator=(const & x) = delete;
};

Design of Value ADTs

Mutable vs. Immutable

Entity objects are usually mutable. Their attributes can change via mutators.

Value based objects should be immutable. Instead, variables of the ADT are assigned to different objects (reassignment). All field types should be primitive or immutable types.

Writing Immutable ADTs

Static Members

Singleton Design (Anti) Pattern

class Egg {
    static Egg e; // Singleton Object.

    int i;
    Egg(int ii) : i(ii) {} // Private Constructor.

public:
    static Egg & instance() {
        return e;
    }

    int val() const {
        return i;
    }

    Egg(const & Egg) = delete;
    Egg & operator=(const Egg &) = delete;
};

Egg Egg::e(42); // How you initialize the singleton egg.

Compilation and Linking

If we need to change the size of a class because we need a new variable, all clients must recompile.

pImpl Idiom (Pointer to Implementation)

// XWindow Impl.cc
#include <xll/xlib.h>

struct XWindowImpl {
    Display *d;
    Window w;
    int s;
    GC gc;
    unsigned long colours[10];
}
// XWindow.h

class XWindow {
    XWindowImpl * pImpl;
public:
    // Same as before.
}
// XWindow.cc

XWindow::XWindow(...) : pImpl(new XWindowImpl(...)) {}

// All other members, usages of d, w, s, ... become pImpl->d ...

Namespaces and Directives

Defining your own namespace may be used for subdividing global namespace into named space. Within a namespace, you can refer to other members by their local names.

Module: A software component that encapsulates some design decision.

Interface

Abstraction public description of some module.

Benefits of Modularity

Interface Specification

Defines what the unit requires, in the way of services of assumptions for it to work correctly.

CS 247 Interface Specification

// sumVector.h
#include <vector>
int sumVector(const std::vector<int> & vect);
// Preconditions: vect is a valid vector whose content's sum does not overflow.
// Requires ...
// Modifies ...
// Ensures ...
// Returns ...

int sumVector(const std::vector<int> & vect) {
    int sum = 0;
    for (size_t i = 0; i < vect.size(); ++i) {
        sum += vect[i];
    }
    return sum;
}
class IntStack {
    // Specification Fields:
    // stack
    // top = top element of stack
public:
    IntStack();
    // Ensures: Initializes stack to an empty stack.

    ~IntStack();
    // Modifies: stack.
    // Ensures: stack no longer exists, memory is all freed.

    void push(int elem);
    // Modifies: stack, top.
    // Ensures: stack is appended with elem, top = elem.

    int top();
    // Requires: stack is non-empty.
    // Returns: top.

    void pop();
    // Modifies: stack, top.
    // Ensures: If stack@pre is empty, then stack is empty.
    //          Otherwise, stack = stack@pre with elem removed.
    //          top = remaining top of nothing if stack is empty.
};

Stack and top are Abstract Specification Data Members. They don’t define the actual structure / fields of our class but rather a way to describe the client’s view of the objects state that we can write expressions over.

An interface specification describes the behaviour of some software unit (function or class). An implementation satisfies a specification if it conforms to the described behaviour.

The specificand set of a spec is the set of all conforming implementations. A strong specification is more tolerant on inputs, and more demanding on outputs. A weak specification is more demanding on inputs, and more tolerant on outputs.

Spec A is stronger than B (A \ge B) if and only if.

  1. B’s preconditions are equal to or stronger than A’s.
    • Requires A \le Requires B.
  2. A’s postconditions are stronger or equal to B’s.
    • Requires B \ge (Ensures A \cap Returns A) \ge (Ensures B \cap Returns B).
  3. A modifies the same or more objects than B.
  4. A throws the same or fewer exceptions than B.

Preconditions

Handling Exceptions

#include <stdexcept>

try {
    cout << v.at(100000) << endl;
} catch (out_of_range) {
    cerr << "Range Error." << endl;
}
void f() {
    // out_of_range is a class. out_of_range("f") is a constructor call.
    throw out_of_range("f");
}

void g() {
    f();
}

void h() {
    g();
}

int main() {
    // The exception is propogated if it is not in a try or if there is no matching catch.
    try {
        h();
    } catch (out_of_range ex) {
        cout << ex.what() << endl;
        ...
        throw; // throw s; may cause issues if inheritance in exceptions.
    } catch (...) {
        /// catch (...) will catch everything.
    }
}

You can throw anything. You can catch by reference to avoid slicing the object but the static type thrown is what determines what gets caught.

class BaseExn {};
class DerivedExn : public BaseExn {};

void f() {
    DerivedExn d;
    BaseExn &b = d;
    throw b;
}

void h() {
    DerivedExn d;
    throw d;
}

int main() {
    ...
    try {
        h();
    } catch (BaseExn &h) {
        // This handler will run.
        ...
    } catch (DerivedExn &d) {
        ...
    }
    ...
    try {
        f();
    } catch (DerivedExn &d) {
        ...
    } catch (BaseExn &h) {
        // This handler will run.
        ...
    }
}

You should never throw an exception in a destructor because exceptions will unwind the stack which will call the destructors for all stack allocated objects. This can cause multiple unhandled exceptions.

Exception Safety

void f() {
    MyClass *p = new MyClass;
    MyClass mc;
    g();
    delete P;
}

No leaks in the code, but what if g throws? During stack unwinding, mc is popped off the stack and its destructor runs, freeing any resources associated with it. p is a pointer, when it is popped off the stack, no fancy destructor is called, the object it points to is leaked.

Our only guarantee is that stack allocated data will be popped off (objects will have their destructors run).

C++ Idiom: Resource acquisition is intialization. (RAII). Every resource should be wrapped in a stack allocated object upon acquisition, whose destructor will free it.

#include <memory>
// unique_ptr<T> destructor will delete the pointer.
// std::make_unique<T>();
void f() {
    auto p = std::make_unique<MyClass>();
    MyClass mc;
    g();
}

Unique pointers are unique so copying is disabled. Moving is allowed. We also have shared pointers for when we want to copy.

void f() {
    auto p1 = std::make_shared<MyClass>();
    ...
    if (...) {
        auto p2 = p1;
    } // p2 is popped off, but it does not free the memory.
}

This can be implemented by having a pointer to a counter (reference count). We can increment when copying and decrement when the object no longer points at the same thing. If the reference count drops to 0, the destructor frees the memory.

MyClass *p = new MyClass;
shared_ptr<MyClass> sp1(p);
if (...) {
    shared_ptr<MyClass> sp2(p);
    ...
} // sp2 goes out of scope and the destructor frees p.
sp1->myFn(); // SegFault.
void fun_fib(int n) {
    if (n == 0) throw 0;
    if (n == 1) throw 1;

    try {
        fun_fib(n - 1);
    } catch (int a) {
        try {
            fun_fib(n - 2);
        } catch (int b) {
            throw (a + b);
        }
    }
}

This is very slow. Orders of magnitude slower than the recursive solution.

In addition to unique and shared pointers, we also have weak_ptrs.

Weak pointers are typically used to break cycles in shared pointers.

There are three levels of exception safety (no safety is not included) for a function f.

  1. Basic Guarantee: Should f terminate due to an exception, the program will be left in a valid but unspecified state.
  2. Strong Guarantee: Should f terminate due to an exception, the program state will be as if f were never called.
  3. No-Throw Guarantee: f will never throw an exception and always complete its task.
class A {...};
class B {...};

class C {
    A a;
    B b;

public:
    void f() {
        a.method1(); // Provides strong guarantee.
        b.method2(); // Provides strong guarantee.
    }
};

Does C::f provide a strong guarantee? No because a.method1() could succeed and make changes but b.method2() could crash (we would not undo changes).

class C {
    A a;
    B b;

public:
    void f() {
        A temp_a = a;
        B temp_b = b;
        temp_a.method1();
        temp_b.method2();
        // Copy assignments cannot throw.
        a = temp_a;
        b = temp_b;
    }
}

How do we create our objects so copying can’t throw?

How can we write swaps for objects so that they do not throw?

class CImpl {
    A a;
    B b;
    friend class C;
};

class C {
    unique_ptr<CImpl> pImpl;
public:
    void f() {
        auto temp = make_unique<CImpl>(*pImpl);
        temp->a.method1();
        temp->b.method2();
        std::swap(pImpl, temp); // No-throw guarantee.
    }
};

If a function offers the no-throw guarantee, you should mark it as such with “noexcept” keyword. At the very least, move operators should be noexcept. This allow the compiler to make optimizations (e.g. vector::emplace_back).

Why is Encapsulation Important? To hold class invariants.

When deciding the implementation of a class, we do not necessarily know what is better. We want to be able to swap out representations easily / painlessly. We want out specification and ADT to have Representation Independence, chnages to the representation do not affect how the ADT is used.

We define some representation invariants R to help us reason about our class and write good code. Defines what is a legal / valid state for our representation invariants. Similarily, we come up with an Abstraction Function A which maps from valid states of representation, to our ADTs possible values.

class Set {
    int *elements_;
    size_t capacity_;
    size_t size_;

public:
    Set();
    ~Set();
    void insert(int d);
    void remove(int d);
    bool member(int d);
};
  1. No duplicate elements. \forall i, j \in \{0 \to size\_ - 1\}, i \neq j \Rightarrow elements\_[i] \neq elements\_[j].
  2. All elements in our set are stored in indices \{0 \to size\_ - 1\} of elements_.

Methods Need To Preserve Invariants

  1. Verify that the constructor establishes invariants.
  2. For each method, assume it holds true, prove / verify method does not violate invariant at end.
  3. If encapsulation is not broken, representation invariants hold true.

Representation Example

class Node {
    int data_;
    Node *next_ = nullptr;

public:
    Node(int d, Node *next = nullptr) : data_(d), next_(next) {}
    ~Node() {
        delete next_;
    }

    Node *next() {
        return next_;
    }
};

int main() {
    Node my_list = Node(1, new Node(2, new Node(3)));
    Node my_list_2 = Node(0, &my_list);
}

We need R.

Iterator Pattern

We want to be able to iterate over our collection efficiently without exposing the representation.

class List {
    struct Node;

    Node *list;

    Iterator begin() {
        return Iterator(list);
    }

    Iterator end() {
        return Iterator(nullptr);
    }

public:
    class Iterator {
        friend class List;

        explicit Iterator(Node *p) : p(p) {}

        Node *p;

    public:
        Iterator &operator++() {
            p = p->next();
            return *this;
        }

        bool operator!=(const Iterator &other) {
            return p != other.p;
        }

        bool operator==(const Iterator &other) {
            return p == other.p;
        }

        int &operator*() {
            return p->data;
        }
    }
};

Documenting Representation Invariants

Determining Representation Invariants

  1. Look for invalid values for your representation.
  2. Think about what assumptions you make or want to make while writing your code.

Checking Representation Invariants

class MyClass {
    bool check_rep();

public:
    ...
    void foo() {
        #ifdef MYDEBUG_
        check_rep();
        #endif
    }
};

g++-5 -std=c++14 -DMYDEBUG_ -c MyClass.cc

Abstraction Function

The abstraction function is not guaranteed to be injective, but it is guaranteed to be surjective. Therefore, it may not have an inverse function.

Example: Rational r

AF(r) = \frac{r.numerator\_}{r.denominator\_}
AF(r) = \{elements\_[i] | 0 \le i \le r.size\_\}

There is no concrete language for talking about our abstract values.

Example: A set S over the integers in range 0, ..., 255.

Bit vector stored in a char c, integer i is in set if and only iff c & (1 << i). AF(r) = \{\forall i \in [0, 255] | c \& (1 << i) \}

Models (UML)

An abstraction of something.

Legend

Note: We do not use “in”. We also do not want to be too specific with types because UML are designed to be language agnostic.

Associations

An association represents a relationship between two classes, share a physical or conceptual link.

Consider marks a student has in a course. To which class should we attribtue marks? Marks should be associated with a pair of (student, course).

Relationships

Composition Relationship

A specialization of association, where one class owns an object(s) of another class.

If A owns B, then typically …

Modelled in UML as a solid diamond on the owner connected to the owned.

Aggregation Relationship

A specialization of association, where one class has objects(s) of a class.

If A has B then …

Modelled in UML as a hollow diamond on the owner connected to the owned.

Generalization / Specialization Relationship

One class is another class.

Modelled in UML as a hollow triangle pointing to the base class.

UML Object Model

UML Sequence Diagram

Design Patterns

Observer Pattern

We want to abstract away change.

Example: Publisher is spreadsheet cells and observers are our generated graphs.

  1. Subject’s state is updated.
  2. Subject::notifyObservers is called, it calls notify() on all its observers.
  3. Each observer does their update, which likely involves calling concreteSubject::getState to query the state and react accordingly.

Example: Horse Races. The subject publishes the winning horse, the observers are individual betters who will declare victory if their horse wins.

class Subject {
    vector<Observer *> observers_;

public:
    void attach(Observer *ob) {
        observers_.emplace_back(ob);
    }
    void detach(Observer *ob);
    void notifyObservers() {
        for (auto &p : observers_) {
            p->notify();
        }
    }
    virtual ~Subject() = 0;
    Subject::Subject() {}
};

class Observer {
public:
    virtual void notify() = 0;
    virtual ~Observer();
};

class Horserace : public Subject {
    ifstream in_;
    string last_winner_;

public:
    Horserace(string source) : in{source} {}
    ~Horserace() {}
    bool runRace() {
        return in_ >> last_winner_;
    }
    string getState() const {
        return last_winner_;
    }
};

class Bettor : public Observer {
    Horserace *subject_;
    string name_, horse_;

public:
    Bettor(...) {
        subject_->attach(this);
    }
    void notify() {
        string winner = subject_->getState();
        cout << (winner == horse_ ? "Win!" : "Lose.") << endl;
    }
};

Decorator Pattern

Suppose you want to enhance an object (e.g. adding functionality or features).

Example: Windowing System. We start with a basic window, and then add a toolbar, scrollbar, and a menu. We want the user to be able to choose these at runtime.

Example: Pizza.

class Pizza {
public:
    virtual float price() const = 0;
    virtual string description() const = 0;
    virtual ~Pizza();
};

class CrustAndSauce : public Pizza {
public:
    float price() const override {
        return 5.99;
    }
    string description() const override {
        return "Pizza";
    }
};

class Decorator : public Pizza {
protected:
    Pizza *component_;

public:
    Decorator(Pizza *p) : component_(p) {}
    virtual ~Decorator() {
        // Depends on whether we have aggregation or composition.
        delete component_;
    }
};

class StuffedCrust : public Decorator {
public:
    StuffedCrust(Pizza *p) : Decorator(p) {}
    float price() const override {
        // Better to have pass-through methods.
        return component_->price() + 2.69;
    }
    string description() const override {
        return component_->description() + " with Stuffed Crust"
    }
};

class Topping : public Decorator {
private:
    string topping_;
public:
    Topping(Pizza *p, string topping) : Decorator(p), topping_(topping) {}
    float price() const override {
        return component_->price() + 0.75;
    }
    string description() const override {
        return component_->description() + " with " + topping_;
    }
};

int main() {
    Pizza *p = new CrustAndSauce;
    p = new Topping(p, "Cheese");
    p = new Topping(p, "Pineapple");
    std::cout << p->description() << std::endl;
    // Pizza with Cheese with Pineapple.
}

Factory Method Pattern

Exampe: We want to write a video game with two kinds of enemies: turtles and bullets. The system randomly sends turtles and bullets, but bullets become more frequent in later levels.

We never know exactly which enemy is going to come next, we (client) can’t call the constructors directly. Moreover, we dont want to hardcode the policy that decides what comes next, it should be customizable. Instead we add a factory method in Level that creates enemies.

class Level {
    ...
public:
    // Factory method.
    virtual Enemy *createEnemy() = 0;
    ...
};

class NormalLevel : public Level {
    ...
public:
    Enemy *createEnemy() override {
        // Create enemies, mostly Turtles.
    }
    ...
};

class Castle : public Level {
    ...
public:
    Enemy *createEnemy() override {
        // Create enemies, mostly Bullets.
    }
    ...
};

Template Method Pattern

Pattern is used when we want subclasses to override some aspects of a superclass method behaviour but not all.

Example: Red-shelled Turtles and Green-shelled Turtles.

class Turtle {
public:
    void draw() {
        drawHead();
        drawShell();
        drawFeet();
    }

private:
    void drawHead() {
        ...
    }
    void drawFeet() {
        ...
    }
    virtual void drawShell() = 0;
};

Subclasses cannot change the way a turtle is drawn, nor can they change how feet or head are drawn, but they can change how shell is drawn.

Non-Virtual Interface (NVI) Idiom

The NVI idiom extends the template method by wrapping every virtual method with a non-virtual method.

Hard to separate these 2 ideas if they’re wrapped up in one function declaration.

The NVI idiom says that all public methods should be non-virtual.

All public methods should be non-virtual. All virtual methods should be private, or at the very least protected, with the exception of the destructor.

Bad Example

class DigitalMedia {
public:
    // We cannot have control over play without changing all derived classes.
    virtual void play() = 0;
    virtual ~DigitalMedia();
};

Translated to NVI

class DigitalMedia {
    virtual void doPlay() = 0;
public:
    void play() {
        doPlay();
    }
    virtual ~DigitalMedia();
};

Now if we want to exert extra control over play, we just put the behaviour we want in the superclass play method. We can add more hooks by calling more virtual methods.

Adapter Pattern

Solves the problem of interface mismatch between two modules.

Example: STL Stacks are implemented as an adapter of a container class (usually a deque).

  1. Object Adapater.
  2. Class Adapter.

Facade Pattern

Strategy Pattern

We want to vary an algorithm (strategy) at runtime.

We encapsulate the algorithm itself. We define an algorithm as a component object of our class that uses. We will have an ABC for algorithm and use inheritance to specialize.

Visitor Pattern

For implementing double dispatch.

class Enemy {
public:
    virtual void beStruckBy(Weapon &w) = 0;
};

class Turtle : public Enemy {
public:
    void beStruckBy(Weapon &w) override {
        // Turtle object type.
        w.strike(*this);
    }
};

class Bullet : public Enemy {
public:
    void beStruckBy(Weapon &w) override {
        // Bullet object type.
        w.strike(*this);
    }
};
class Weapon {
public:
    virtual void strike(Turtle &t) = 0;
    virtual void strike(Bullet &b) = 0;
};

class Stick : public Weapon {
public:
    void strike(Turtle &t) override;
    void strike(Bullet &b) override;
};

class Rock : public Weapon {
public:
    void strike(Turtle &t) override;
    void strike(Bullet &b) override;
};
int main() {
    Enemy *e = EnemyFactory();
    Weapon *w = WeaponFactory();
    e->beStruckBy(*w);
    // Turtle::beStruckBy gets called (virtual dispatch).
    // This calls Weapon::strike(Turtle &) (overload).
    // Which is actually calling Stick::strike(Turtle &) (virtual override).
}
class MyClass {
    virtual void accept(MyClassVisitor &v) {
        v.visit(*this);
    }
};

class MyClassVisitor {
    virtual void visit(MyClassA &) = 0;
    virtual void visit(MyClassB &) = 0;
};

Composite Pattern

// From SE Dropbox Paper notes.
HeroicTeam t{...};

Iterator &HeroTeamIter::operator++ {
    if (h) { 
        h = nullptr;
        return *this;
    } else {
        if (*curIter == (*it)->end()) {
            ++it;
        } else {
            ++curIter;
        }
    }
    return *this;
}

bool HeroTeamIter::operator!=(const Iterator & o) {
    return h == o.h && it == o.it && curIteer == o.curIter;
}
// From SE Dropbox Paper notes.
bool HeroTeamIter::operator!=(const Iterator &other) {
    try {
        const HeroTeamIter &o = dynamic_cast<const HeroTeamIter&>(other);
        return !(field1 == o.field1 && ...);
    } catch (...) {
        return false;
    }
}

Measures of Design Quality

Coupling

The degree to which distinct modules interact and rely / depend on each other.

Severity of Coupling

  1. (Low) Modules communicate via function calls with basic parameters / results.
  2. Modules pass arrays / structs back and forth.
  3. Modules affect each other’s control flow.
  4. Modules share global data.
  5. (High) Modules share / have access to each other’s implementations (friends).

High Coupling

Cohesion

How closely elements of a module are related to each other.

Levels of Cohesion

  1. (Low) Arbitrary grouping of unrelated elements. Example: utility.
  2. Element share a common theme, otherwise unrelated.
  3. Elements manipulate the state over the lifetime of an entity.
  4. (High) Elements cooperate to perform exactly one task.

Low Cohesion

Goal: Low coupling and high cohesion.

Decoupling the Interface (MVC)

class ChessBoard {
    ...
    cout << "Your Move" << ...
};
class ChessBoard {
    ostream &out;
    ...
    out << "Your Move" << ...
};

Model-View-Controller

Model

Controller

OO Design Principles

Open Closed Principle

A module should be open to extension, but closed to modification. Program to an interface and not to an implementation.

The idea is that your client code should depend only on ABC’s that can be extended, not on concrete classes (e.g. the target interface in Adapter Pattern rather than Client using Adapter directly).

Suggestion: All base classes should be ABC’s. This implies that you should never inherit from a concrete class.

Inheritance or Composition?

When defining a new class that includes attributes or behaviour from an existing class, do we inherit or compose?

Liskov Substitutability Principle (LSP)

A derived class must be substitutable for its base class.

Example: A BoundedStack is a specialized type of Stack that cannot grow past a certain size. Is a BoundedStack substitutable for a Stack? Assume BoundedStack has a limit of 255 elements.

Stack *s;
for (size_t i = 0; i < 1000; ++i) {
    s->push(i);
}

No, a BoundedStack is not substitutable for a Stack. Instead, BoundedStack should be composed with a Stack.

Note: On overriding in c++.

Law of Demeter

A class should only talk to its neighbours.

Advantages

Disadvantages

Examples:

void A::m1(SomeObj b) {
    b.m2() // Ok. Params.
    this->otherObj.m3(); // Ok. A's data members.
    b.gen().m4(); // Not ok.
    AnotherObj obj{};
    obj.m5(); // Ok. Object constructed by A's methods.
}

Refactoring

Changing existing code to “clean it up”.

Why Refactor?

When Refactor?

When Not To Refactor?

What to Refactor?

Duplicated Code

Long Method

Large Class

Long Parameter List

Divergent Changes

Shotgun Surgery

Opposite of divergent change.

Primitive Obsession

Feature Envy

Lazy Class

Automated Testing

Casting

Casting should be avoided, and in particular, c-style casting should be avoided. If you must cast, use c++-style.

Casting in C

Node n;
int *ip = (int*) &n;

Casting in C++

  1. static_cast is for “sensible-casts” between types where conversion has well-defined behaviour.

  2. reinterpret_cast is for unsafe, implementation dependent “weird” conversions. Nearly all uses result in undefined behaviour.

  3. const_cast is for converting between const and non-const. It is the only c++ cast that can “cast away” constness.

  4. dynamic_cast asks “is it safe to cast”.

Virtual Methods Review

class vec {
    int x, y;
public:
    int something();
};

class vec2 {
    int x, y;
public:
    virtual int something();
};

int main() {
    vec v1;
    vec2 v2;
    cout << sizeof(v1) << " " << sizeof(v2);
    // 8 16.
}

First, 8 bytes is for the two ints x,y. The extra 8 bytes in v2 are for a pointer.

For each class that has virtual methods the compiler creates a table. It is a table of function pointers, they point to the implementations of the classes virtual methods. We call this the vtable.

The compiler stores a pointer to the class’ vtable in all objects of that type (at the start). When you call a virtual method, the compiler follows that pointer to the vtable, jumps to the location pointed to be the function pointer in that table.

Deadly Diamond of Death

Class B, C inherit from A. Class D inherits from B, C.

When D calls a function from A, overwritten in B and C, which function gets called? This can be solved with virtual inheritance in c++.

Templates

template<typename T>
T m(const T &x, const T &y) {
    return x < y ? x : y;
}

Note: No need to specify types when calling templated methods (when those types are deducible). Must always specify for classes.

int main() {
    int x = 1, y = 2;
    cout << m(x, y); // Compiler deduces type.
    short s = 5;
    cout << m(s, 20); // Cannot deduce type.
    cout << m(s, x); // Cannot deduce type.
    cout << m<short>(s, 20); // Works. Compiler knows to use implicit conversion.
}

Variadic Templates

template<typename T, typename... Ts>
// <First Argument, Parameter Pack>
void print(const T& arg const Ts& ...args) {
    print(arg);
    print(args...);
}

template<typename T>
void print(const T& arg) {
    cout << arg;
}

Class Templates

STL

Containers

Useful Algorithms

Design Principles

Polymorphic Types in Containers

vector<Figure> // No, Figure is ABC.
vector<Figure&> // No, can't store references in arrays.
vector<Figure*> // Yes.
vector<unique_ptr<Figure>> // Yes.
vector<shared_ptr<Figure>> // Yes.
Container Type Details Examples
Sequence Have strict ordering based on programmer’s placement. Vector, deque, list, array
Associative Elements are referenced by keys rather than indices. Strict ordering based on the comparator. Set, map, multiset, multimap
Unordered Associative As above, but with no guarantee on ordering. Unordered_map, unordered_set, …

Sequence Containers

Associative Containers

Function Objects

class X {
public:
    int operator()(int x, int y) {
        return x - y + 5;
    }
};

Iterator Invalidation

Any sort of reference to the contents of an STL container can become invalidated with certain operations.

vector<int> v;
for (size_t i = 0; i < 10; ++i) {
    v.emplace_back(i);
}

auto it = v.begin() + 5;
int &ref = v.at(4);
int *ptr = &v.at(3);

cout << *it << " " << ref << " " << *ptr << endl;

// v will have to resize.
for (size_t i = 0; i < 10000; ++i) {
    v.emplace_back(i);
}

// Undefined behaviour.
cout << *it << " " << ref << " " << *ptr << endl;

Iterator Types

Forward Iterator

Input Iterator

operator++
operator!=
// On right-hand side of assignment or rvalue contents.
operator*

Output Iterator

operator++
operator!=
// On left-hand side of statements.
operator*

Bidirectional Iterator

operator--

Random Access Iterator

operator+=
operator-=
operator+
operator-
operator[]
operator<
...
template<typename InIter, typename T>
InIter find(InIter first, InIter last, const T &val) {
    // Returns an InIter to the first occurance of val in the range [first, last), or last if val not found.
}
template<typename InIter, typename OutIter>
OutIter copy(InIter first, InIter last, OutIter dest) {
    // Copies items from [first, last) to the location starting at dest.
    // Container associated with dest must have enough space!
}
template<typename InIter, typename OutIter, typename Func>
OutIter transform(InIter first, InIter last, OutIter result, Func f) {
    while (first != last) {
        *result = f(*first);
        ++first;
        ++result;
    }
}

int add1(int n) {
    return n + 1;
}

vector<int> v{2, 3, 5, 7, 11};
vector<int> w(v.size());

transform(v.begin(), v.end(), w.begin(), add1);
template<typename RandomIt>
void sort(RandomIt first, RandomIt last) {
    // Sorts the elements in range [first, last).
}

template<typename RandomIt, typename Comp>
void sort(RandomIt first, RandomIt last, Comp comp) {
    // Sorts container [first, last) using comp.
}

Currying

Partially calling a function and getting a function back with parameters substituted.