CS 330 Lecture 27 – Inheritance and polymorphism
Agenda
- constructors and destructors
- a destructor’s job: release dynamically-allocated members
- a linked list in C++
- a Stack using inheritance in C++
- implementation inheritance vs. interface inheritance
- the enlightened stance: favor composition, shallow hierarchies, interfaces
- how polymorphism works
TODO
- Why extends is evil: http://www.javaworld.com/javaworld/jw-08-2003/jw-0801-toolbox.html?page=1
- What OOP isn’t: http://hacksoflife.blogspot.com/2010/12/what-oop-isnt.html
Program This
Given the List<T> implementation discussed in class, write one of the a) prepend method or b) the append method.
Code
List.h
#ifndef LIST_H
#define LIST_H
#include <cstdlib>
template<class T> class List {
public:
List();
~List();
void append(T item);
void prepend(T item);
void apply(void (*f)(T& item));
int size() const;
struct Node {
T item;
Node *next;
Node *prev;
};
protected:
void remove(Node *node);
Node *head;
Node *tail;
int nelements;
};
/* ------------------------------------------------------------------------- */
template<class T>
List<T>::List() :
nelements(0) {
head = new Node;
tail = new Node;
head->next = tail;
head->prev = NULL;
tail->next = NULL;
tail->prev = head;
}
/* ------------------------------------------------------------------------- */
template<class T>
List<T>::~List() {
std::cout << "is in dtor" << std::endl;
Node *curr = head;
while (curr->next) {
curr = curr->next;
delete curr->prev;
}
delete curr;
}
/* ------------------------------------------------------------------------- */
template<class T>
void List<T>::append(T item) {
Node *new_node = new Node;
new_node->next = tail;
new_node->prev = tail->prev;
tail->prev = new_node;
new_node->prev->next = new_node;
new_node->item = item;
++nelements;
}
/* ------------------------------------------------------------------------- */
template<class T>
void List<T>::prepend(T item) {
Node *new_node = new Node;
new_node->next = head->next;
new_node->prev = head;
head->next = new_node;
new_node->next->prev = new_node;
new_node->item = item;
++nelements;
}
/* ------------------------------------------------------------------------- */
template<class T>
void List<T>::remove(Node *node) {
node->prev->next = node->next;
node->next->prev = node->prev;
delete node;
--nelements;
}
/* ------------------------------------------------------------------------- */
template<class T>
int List<T>::size() const {
return nelements;
}
/* ------------------------------------------------------------------------- */
template<class T>
void List<T>::apply(void (*f)(T& item)) {
Node *curr = head->next;
while (curr != tail) {
f(curr->item);
curr = curr->next;
}
}
/* ------------------------------------------------------------------------- */
#endif
Stack.h
#ifndef STACK_H
#define STACK_H
#include "List.h"
template<typename T> class Stack : public List<T> {
public:
void push(T item);
T pop();
private:
};
/* ------------------------------------------------------------------------- */
template<typename T>
void Stack<T>::push(T item) {
append(item);
}
/* ------------------------------------------------------------------------- */
template<typename T>
T Stack<T>::pop() {
if (List<T>::size() == 0) {
throw "stack empty, sorry";
}
// TODO: this errs
List<T>::Node *last_node = this->tail->prev;
T last_item = last_node->item;
this->tail->prev = last_node->prev;
this->tail->prev->next = this->tail;
delete last_node;
return last_item;
}
/* ------------------------------------------------------------------------- */
#endif
lister.cpp
#include <iostream>
#include "List.h"
#include "Stack.h"
void print(int& item) {
std::cout << "item: " << item << std::endl;
}
int main() {
List<int> nums;
nums.append(10);
nums.append(20);
nums.append(30);
nums.apply(print);
Stack<double> percents;
percents.push(5.0);
List<double>::Node *last_node;
}
Haiku
Grades would be easy.
But you all have vtables.
You are dynamic.
But you all have vtables.
You are dynamic.