Key Concepts

• If you dynamically allocate memory, you need to write your own (this is not an exhaustive list in general, just what we have covered so far):
• destructor
• copy constructor
• assignment operator

main.cpp

#include <iostream>

class Class1
{
 public:
  Class1();                              // constructor
  ~Class1();                             // destructor
  Class1(const Class1& obj);             // copy constructor
  Class1& operator=(const Class1& rhs);  // assignment operator

  int geta() { return *a_; }
  int getb() { return b_; }
  void seta(int a) { *a_ = a; }
  void setb(int b) { b_ = b; }
 private:
  int* a_;
  int b_;
};

Class1::Class1() : b_(10) // member initializer list
{
  a_ = new int(5);
  std::cout << "Class1 constructor" << std::endl;
}

Class1::~Class1()
{
  delete a_;
  std::cout << "Class1 destructor" << std::endl;
}

Class1::Class1(const Class1& obj)
{
  // deep copy the contects of obj into this
  a_ = new int;
  *a_ = *obj.a_;
  b_ = obj.b_;
  std::cout << "Class1 copy-constructor" << std::endl;
}

Class1& Class1::operator=(const Class1& rhs)
{
  if(this == &rhs) //assignment to self
    return *this;
  // deep copy the contects of rhs into this
  a_ = new int;
  *a_ = *rhs.a_;
  b_ = rhs.b_;
  std::cout << "Class1 assignment operator called" << std::endl;
  return *this;
}

int main()
{
  // Part 1. Construction
  Class1 c1;
  std::cout << "c1 exists in main()" << std::endl;
  // Part 2. Destructor
  Class1* c1_ptr = new Class1;
  std::cout << "c1_ptr exists in main()" << std::endl;
  delete c1_ptr;
  // Part 3. Copy Constructors
  Class1 c2(c1);
  std::cout << "c2 exists in main()\n";
  // Part 4. Assignment Operator
  Class1 c3;
  c3 = c2;
  std::cout << "c3 exists in main()\n";
  // Note that destructors for c1, c2, c3 will called at the end of main()
}

Output:

Class1 constructor
c1 exists in main()
Class1 constructor
c1_ptr exists in main()
Class1 destructor
Class1 copy-constructor
c2 exists in main()
Class1 constructor
Class1 assignment operator called
c3 exists in main()
Class1 destructor
Class1 destructor
Class1 destructor

The following code stubs are for example's sake and need a full linked list to actually be useful. Given the nature of project 2, I can't give you a linked list class! But this should still be helpful. We will rely heavily on this supplemental material. Let's start with this basic definition of a node:

// Simple class, for the sake of the demo
// This should live inside of a linked list class
class Node
{
 public:
  Node() : m_prev(nullptr), m_next(nullptr) {}
  Node* m_prev;
  Node* m_next;
  int value;
}

Now suppose you wanted to remove the head item in the linked list. Consider the following:

// this function lives somewhere in the LinkedList class
// initial remove_head()
void remove_head()
{  // so much bad!
  Node* old_head = head;
  //might be dereferencing nullptr (Q 4,6)
  head = head->m_next;
  //might be dereferencing nullptr (Q 5,6)
  head->m_prev = nullptr; 
  delete old_head;
}

This has a lot of problems: 1) head might be null, 2) if we are removing the last element, we should update tail:

// safe remove head function
void remove_head()
{
  if (head != nullptr)
  {  // make sure head is safe to dereference
    Node* old_head = head;
    head = head->m_next;
    if (head == nullptr)
    {  // if head is at nullptr, tail should be too
      tail = nullptr;
    }
    else
    {  // safe to deference head in this case
       // set new head's previous to null
      head->m_prev = nullptr;
    }
    delete old_head;
  }
}

Here we introduce a circularly linked list (see supplemental) to make our implementation less error prone. Note that we don't need a tail in a circularly linked list, as that is simply head->previous:

// circularly linked list safe function
// Note: explicit tail is removed from this model
void remove_head()
{
  if (head != nullptr)
  {  // make sure head is safe to dereference
    Node* old_head = head;
    if (head->m_next == head)
    {  // removing the last element
      head = nullptr;
    }
    else
    {  // Things to do:
      //  1) update head
      //  2) update new head's previous
      //  3) update tail's next
      head = head->m_next;
      // copy old previous
      head->m_prev = old_head->m_prev;
      // update tail's next
      head->m_prev->m_next = head;
    }
    delete old_head;
  }
}

We'll introduce a dummy node to further reduce the error-proniness of our implementation (see supplemental). The resulting remove_head() function is:

// dummy included
// main advantage: there is *always* at least one element in the list!
//    This avoids a lot of the special cases we had to handle
void remove_head()
{
  Node* actual_head = head->m_next;
  if (actual_head != head)
  {  // don't want to delete the dummy head, empty list case if oldHead == head
    // Things to do:
    // 1) update dummy head's next to the new actual head
    // 2) update new actual head's previous to the dummy head
    head->m_next = actual_head->m_next;
    actual_head->m_next->m_prev = head;
    delete actual_head;
  }
}

Notice how much simplier our final implementation is compared to our initial correct version. The key takeaway: we can reduce the complexity of our implementation by removing edge cases from our data structure model.

Stacks

Stacks follow a First-In, Last-Out (FILO) policy. Stacks have three primary operations: push, pop, and top. Push adds an element to the stack. Pop removes and element from the stack. Top access the element at the top of the stack. Typical stack usage consists of at least one push, followed by top, then pop. You can obviously push after popping.

Here's the implementation we created in class, using the standard library's list class as our underlying data structure.

#include <list>
#include <iostream>
#include <stdexcept>

typedef int ItemType;

class Stack
{
 public:
  Stack();
  bool pop();
  ItemType top();
  void push(const ItemType& val);
  int size() { return list_.size(); }
 private:
  std::list<ItemType> list_;
};

Stack::Stack()
{
}

bool Stack::pop()
{
  if (list_.size() == 0)
    return false;

  list_.pop_front();
  return true;
}

ItemType Stack::top()
{
  if (list_.size() == 0)
    throw std::runtime_error("Trying to access empty stack");

  return list_.front();
}

void Stack::push(const ItemType& val)
{
  list_.push_front(val);
}

int main()
{
  Stack s;
  s.push(5);
  s.push(6);
  s.push(7);
  try
  {
    std::cout << s.top() << std::endl;
    s.pop();
    std::cout << s.top() << std::endl;
    s.pop();
    std::cout << s.top() << std::endl;
    s.pop();
  }
  catch (std::runtime_error e)
  {
    std::cout << e.what() << std::endl;
  }
}

Queues

Queues follow a First-In, First-Out (FIFO) policy. Queues have three primary operations: enqueue, dequeue, and front. Enqueue adds an element to the queue. Dequeue removes and element from the queue. Front access the element at the top of the queue.

Here's the implementation we created in class, using the standard library's list class as our underlying data structure. Notice that outside of renaming functions, we only changed one line of one function: where we insert elements into our linked list (at the beginning for a stack, now at the end).

#include <list>
#include &lt;iostream&gt;
#include &lt;stdexcept&gt;

typedef int ItemType;

class Queue
{
 public:
  Queue();
  bool dequeue();
  ItemType front();
  void enqueue(const ItemType& val);
  int size() { return list_.size(); }
 private:
  std::list<ItemType> list_;
};

Queue::Queue()
{
}

bool Queue::dequeue()
{
  if (list_.size() == 0)
    return false;

  list_.pop_front();
  return true;
}

ItemType Queue::front()
{
  if (list_.size() == 0)
    throw std::runtime_error("Trying to access empty stack");

  return list_.front();
}

void Queue::enqueue(const ItemType& val)
{
  list_.push_back(val);
}

int main()
{
  Queue s;
  s.enqueue(5);
  s.enqueue(6);
  s.enqueue(7);
  try
  {
    std::cout << s.front() << std::endl;
    s.dequeue();
    std::cout << s.front() << std::endl;
    s.dequeue();
    std::cout << s.front() << std::endl;
    s.dequeue();
  }
  catch (std::runtime_error e)
  {
    std::cout << e.what() << std::endl;
  }
}

Recursion

Recursion is an incredibly powerful and critical mechanism to control a function's repeated execution. Recursive functions call themselves and terminate upon a base case. The base case is a condition for the function to stop calling itself. Without it, a recursive function will call itself forever, eventually crashing your program due to stack overflow (or other nasty things). I unfortunately cannot post what we went over in class online since it was based on the homework solution, however, you should have received an email with the solutions. The basic idea I presented to help with debugging/examining recursive functions is the following: visually display the level of recursion using a depth parameter and a simple helper function. Here's the helper function:

void print_tabs(int level)
{
  // print tabs out to the level
  for (int i = 0; i < level; i++)
  {
    std::cout << "\t";
  }
  std::cout << "level: " << level;
}

To use it, you would add a parameter to represent the recursive level you are currently executing. Here's an example:

int indexOfLeast(const string a[], int n, int level)

In the recursive call to indexOfLeast(), you increment the current level. This way, calls to print_tabs() will print the number of tabs of the current recursive depth, providing a nice visualization. See the following example for indexOfLeast():

level: 0
	level: 1
		level: 2
			level: 3
			level: 3	returning: 0
		level: 2	k: 1	returning: 0
	level: 1	k: 1	returning: 1
level: 0	k: 2	returning: 2
2

Templates

Templates enable generic types for a given class or function. This is similar to the typedef ItemType int we used for our Stack and Queue class, but significantly more abstract and power. Templates allow for generic types of a given class for function. What does this mean? For templated functions, you don't have to worry about the types passed to the function - if the user passes two ints or two strings, the function will process the corresponding types the same way. This does place a requirement on the types passed; the types must support the operations the function performs (e.g. the operators used are defined for T). Here's our stack and queue class implemented using templates:

#include <list>
#include <iostream>
#include <stdexcept>

template<typename T>
class Stack
{
 public:
  Stack();
  bool pop();
  T top();
  void push(const T& val);
  int size() { return list_.size(); }
 private:
  std::list<T> list_;
};

template<typename T>
Stack<T>::Stack()
{
}

template<typename T>
bool Stack<T>::pop()
{
  if (list_.size() == 0)
    return false;

  list_.pop_front();
  return true;
}

template<typename T>
T Stack<T>::top()
{
  if (list_.size() == 0)
    throw std::runtime_error("Trying to access empty stack");

  return list_.front();
}

template<typename T>
void Stack<T>::push(const T& val)
{
  list_.push_front(val);
}

int main()
{
  Stack<int> s;
  s.push(5);
  s.push(6);
  s.push(7);
  try
  {
    std::cout << s.top() << std::endl;
    s.pop();
    std::cout << s.top() << std::endl;
    s.pop();
    std::cout << s.top() << std::endl;
    s.pop();
  }
  catch (std::runtime_error e)
  {
    std::cout << e.what() << std::endl;
  }
}

#include <list>
#include <iostream>
#include <stdexcept>

template <typename T>
class Queue
{
 public:
  Queue();
  bool dequeue();
  T front();
  void enqueue(const T& val);
  int size() { return list_.size(); }
 private:
  std::list<T> list_;
};

template <typename T>
Queue<T>::Queue()
{
}

template <typename T>
bool Queue<T>::dequeue()
{
  if (list_.size() == 0)
    return false;

  list_.pop_front();
  return true;
}

template <typename T>
T Queue<T>::front()
{
  if (list_.size() == 0)
    throw std::runtime_error("Trying to access empty stack");

  return list_.front();
}

template <typename T>
void Queue<T>::enqueue(const T& val)
{
  list_.push_back(val);
}

int main()
{
  Queue<int> s;
  s.enqueue(5);
  s.enqueue(6);
  s.enqueue(7);
  try
  {
    std::cout << s.front() << std::endl;
    s.dequeue();
    std::cout << s.front() << std::endl;
    s.dequeue();
    std::cout << s.front() << std::endl;
    s.dequeue();
  }
  catch (std::runtime_error e)
  {
    std::cout << e.what() << std::endl;
  }
} 

Inheritance and Polymorphism

We didn't cover this in discussion due to the lecture that took place instead, but here are the fundamentals. Inheritance lets you define type-hierarchy relationships. The classic example is that a Truck is-a Vehicle, and similarly a Car is-a Vehicle. However, Trucks and Cars have different enough properties that they should be represented with different classes. Trucks and Cars also have a lot in common; they both move, turn, honk, etc. So it makes sense to have a base class that represents those common properties (Vehicle), and derived classes that build on the base class (Truck and Car). In this model, the Truck and Car class would inherit from the Vehicle class.

In our vehicle example, suppose we wanted to store a list of all trucks and cars. We can accomplish this by have a list of pointers to each Vehicle. If we want the execute the derived class behavior with this list of Vehicles, we need to tell the Vehicle pointer it might actually be a derived class. We accomplish this using the

virtual

keyword on the Vehicle (base class) functions we want to be polymorphic. The virtual keyword basically means 'if I am actually a pointer to a derived class, prefer to run their version of the function, if it exists.' Here's a trivial example that encompasses inheritance, polymorphism, and order of construction when using inheritance:

#include <iostream>

class A
{
 public:
  A() { std::cout << "A "; };
  ~A() { std::cout << "~A "; };
};

class B
{
 public:
  B() { std::cout << "B "; };
  ~B() { std::cout << "~B "; };
  void hello() { std::cout << "\nB says hello \n"; };
  virtual void goodbye() { std::cout << "B says goodbye \n"; };
 private:
  A a;
};

class D
{
 public:
  D() { std::cout << "D "; };
  ~D() { std::cout << "~D "; };
};

class C : public B
{
 public:
  C() { std::cout << "C "; };
  ~C() { std::cout << "~C "; };
  void hello() { std::cout << "\nC says hello \n"; };
  void goodbye() { std::cout << "C says goodbye \n"; };
 private:
  D d;
};

int main()
{
  C c;
  B* b = &c;
  b->hello();
  b->goodbye();
}

Sorting

We'll use the following helper functions for these sorting algorithms:

void print_arr(int arr[], int n, int start = 0)
{
  for (int j = start; j < n; j++)
  {
    std::cout << arr[j] << " ";
  }
  std::cout << std::endl;
}

void print_iteration(int arr[], int i, int n, int start = 0)
{
  std::cout << "Iteration " << i << "\t";
  print_arr(arr, n, start);
}

// swap items i and j
void swap(int arr[], int i, int j)
{
  int temp;
  temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
            

Selection Sort

• Divide the list into two parts: sorted and unsorted (unsorted begins empty)
• Find the smallest element in the unsorted list, place it at the end of the sorted list
• Continue until the unsorted list is empty

The complexity of selection sort is O(n^2).

void selection_sort(int arr[], int n)
{
  std::cout << "Running selection sort on array: ";
  print_arr(arr, n);
  int i_min, temp;

  for (int i = 0; i < n - 1; i++)
  {
    print_iteration(arr, i, n);
    // assume first element is the min
    i_min = i;

    for (int j = i + 1; j < n; j++)
    {
      // update i_min if we find an element smaller
      if (arr[j] < arr[i_min])
        i_min = j;
    }

    // if i_min no longer equals i than a smaller value was found
    // this means we need to swap
    if (i_min != i)
    {
      swap(arr, i, i_min);
    }
  }
  std::cout << "Final selection sort array: ";
  print_arr(arr, n);
}

Insertion Sort

• Divide the list into two parts: sorted and unsorted (sorted begins empty)
• Arbitrarily pick an element in the unsorted list (usually the first)
• Scan the sorted list for where to insert the element, insert where appropriate
• Continue until the unsorted list is empty

The complexity of insertion sort is O(n^2).

void insertion_sort(int arr[], int n)
{
  std::cout << "Running insertion sort on array: ";
  print_arr(arr, n);
  // iterate over the entire array
  for (int i = 0; i < n; i++)
  {
    print_iteration(arr, i, n);
    // scan the sorted list for the position to insert the i-th element
    for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--)
    {
      swap(arr, j - 1, j);
    }
  }
  std::cout << "Final insertion sort array: ";
  print_arr(arr, n);
}          
            

Bubble Sort

• Starting at the beginning of the list, compare adjacent elements. If the adjacent elements are unsorted, swap them
• Repeat passing over the entire list until you make a pass over the list without making a swap

The complexity of bubble sort is O(n^2).

void bubble_sort(int arr[], int n)
{
  std::cout << "Running bubble sort on array: ";
  print_arr(arr, n);
  bool swapped;
  // make at least one pass over the list
  int i = 0;
  do
  {
    print_iteration(arr, i, n);
    swapped = false;

    for (int j = 1; j < n; j++)
    {
      // if this pair is out of order
      if (arr[j - 1] > arr[j])
      {
        swap(arr, j - 1, j);
        swapped = true;
      }
    }
    i++;
  } while (swapped);  // continue loop until we never swap

  std::cout << "Final bubble sort array: ";
  print_arr(arr, n);
}

Merge Sort

• Divides an unsorted list into n sublists (each sublist has one element and by definition is sorted)
• Merge sublists to produce sorted sublists
• Continue merging until there is one sublist remaining (the entire, sorted list)

The complexity of merge sort is O(nlogn).

void merge(int arr[], int working[], int start, int mid, int end);
void merge_sort_aux(int arr[], int working[], int start, int end, int depth);

void merge_sort(int arr[], int n)
{
  std::cout << "Running merge sort on array: ";
  print_arr(arr, n);
  int* working = new int[n];

  // run merge sort on entire array
  merge_sort_aux(arr, working, 0, n - 1, 0);

  delete[] working;
  std::cout << "Final merge sort array: ";
  print_arr(arr, n);
}

void merge_sort_aux(int arr[], int working[], int start, int end, int depth)
{
  int mid;
  if (start < end)
  {
    // find mipoint, use it to recursively split
    mid = (start + end) / 2;
    merge_sort_aux(arr, working, start, mid, depth + 1);
    merge_sort_aux(arr, working, mid + 1, end, depth + 1);
    // after splitting, merge the two sublists
    merge(arr, working, start, mid, end);
    std::cout << "Depth: " << depth << "\t";
    print_arr(working, end, start);
  }
}

void merge(int arr[], int working[], int start, int mid, int end)
{
  int h, i, j, k;
  h = start;    // position in left sublist
  i = start;    // position in working list
  j = mid + 1;  // position in right sublist

  while (h <= mid && j <= end)
  {
    if (arr[h] <= arr[j])
    {  // copy from the left sublist
      working[i] = arr[h];
      h++;
    }
    else
    {  // copy right the right sublist
      working[i] = arr[j];
      j++;
    }
    i++;
  }
  if (h > mid)
  {  // we have more contents in the right sublist to copy
    for (k = j; k <= end; k++)
    {
      working[i] = arr[k];
      i++;
    }
  }
  else
  {  // we have more contents in the left sublist to copy
    for (k = h; k <= mid; k++)
    {
      working[i] = arr[k];
      i++;
    }
  }

  // copy result into original array
  for (k = start; k <= end; k++)
  {
    arr[k] = working[k];
  }
}

Quicksort

• Pick an element in the array (pivot)
• Partition the array such that all elements less than the pivot are before the pivot and all elements greater are after the pivot
• Recursively run this partition on the elements less than the pivot and on the elements greater than the pivot (base case: array size of 0)

The complexity of quicksort is O(nlogn) on average, O(n^2) worst case. We did an implementation for Homework 3.