Classes in C++

• Public members functions
• Private helper functions
• Private variables
• Constructors

class Cat : public Animal {
	public:
		Cat(): name_("jeff"), age_(0) {}
		Cat(string n, int a);
		
	private:
		string name_;
		int age_;
		
		void pet();
}

• Automatic default constructor
• Custom constructors (default and non-default)
• Copy constructor: make a new object based on a passed existing object.

Cube(const Cube & other) {
	//shallow copy example
	cube.color_ = other.color_;
	//deep copy example (with object where brick is a variable in Cube)
	brick_ = other.brick_;
	//deep copy example (with ptrs)
	brick_ = new Brick(*other.brick_);
	//deep copy references don't make sense
}

• Automatic copy constructor

  • generated if we do not define a copy constructor
  • copies every instance of the variable into the object
  • Custom copy constructor (see above)

• Big Three

  • Copy Constructor
  • Copy Assignment Operator

  Cube & Cube::operator=(const Cube & other){
    if (this != &other) { //If I’m not copying myself
      _destroy();
      _copy(other);
    }
    return *this;
  };
  

  • Destructor: make sure that you're using the right delete or delete[]

  void Cube::~Cube() {
  	delete lengthptr_;
  	delete[] properties_;
  }
  

Namespaces in C++

• Creating a class that is part of a namespace (eg: Cube is part of the cs225 namespace)
• Using a class from a namespace (eg: cs225::Cube)
• Purpose and usefulness of namespaces
  • Libraries in C++ are organized into namespaces. Therefore we cannot have two classes with the same name (in the same namespace).
  • using :: notation: cs225::Cube or std::cout
  • don't import everything from a namespace

#pragma once
namespace cs225 {
  class Cube {
    public:
      double getVolume();
      double getSurfaceArea();
      void setLength(double length);
    private:
      double length_;  
  };

Variables

• Four properties: name, type, location (in memory), and value
• Primitive vs. user-defined
  • Primitive
    • Integer int
    • Character char
    • Boolean bool
    • Floating Point float
    • Double Floating Point double
    • Valueless or Void nullptr
  • Derived
    • Function
    • Array
    • Pointer
    • Reference
  • User Defined: we use classes to define new data types.

Memory

• Indirection in C++:

  • Reference variables

    • Alias to existing variable
    • must be initialized on creation and what it refers to cannot be changed
    • doesn't create it's own memory

    Cube s1; // A variable of type Cube
    Cube & r1 = s1; // A reference variable of type Cube
    Cube * p1; // A pointer that points to a Cube
    

  • Pointers

    • pointers are variables with their own memory
    • stores the memory address of the contents they’re “pointing to”.
    • resolves address to read data

  • Differences and trade-offs between types of function calls

    • By Pointer (as a parameter): modifies og object, fast, but not safe
    • By Reference (as a parameter): fast, there is always a valid object passed, modifies og object, nothing is copied when the function is called but also not safe

  • Indirection operators:

    • &v = address of operator: used to declare a reference.
    • *v = dereference operator, adds the new adress and removes the current address.
    • v→ assume that v is a pointer, dereference and call the original variable.

  <aside> 💡 IMPORTANT STUFF:

  Sticks to LHS = reference or ptr, Sticks to RHS: indirection operators.

  LHS: List & l= List Reference

  List * l= List Pointer

  RHS: &l = memory address of L (one step away from the data)

  *l returns data at memory address

  </aside>

  How to approach Pointer and References questions:

  • make a table with type, name, address and value
  • add all the variables and walk thru program logic

• Stack memory: each function invocation gets a stack frame. frame is returned (marked as free) when the function returns. when the memory is marked as freed, it can be overwritten.

  

• Heap memory: add stuff to the heap by using the new keyword. using new

  • allocates memory on the heap
  • always calls the constructor on memory
  • returns the address (lasts until the program exits or we call delete)

Functions: Calling and Returning

• Pass by value, by reference, and by pointer

Runtimes

• O Is worst case, $\Omega$ is best, $\theta$ is amortized (avg)

Array List

• Operation insertAtFront, including running time, resize strategies, and proofs
  • Runtime O(1) Amortized
  • Resize Strat: copy all the elements and make the array one element bigger, copy all the elements and make the array 2x size.
  • Proof: Method 1 takes O(n) time since you have to copy n elements every time you add to the list. Method 2 has O(1) amortized runtime since you only occasionally have to copy all the elements of the list over to a new list to add a new element.
• Operation insertAtIndex, including running time, on both a sorted and unsorted list
  • Runtime O(n)
• Operation removeAtIndex, including running time, on both a sorted and unsorted list
  • Runtime O(n)
• Operation insertAfterElement, including running time, on both a sorted and unsorted list
  • Runtime O(n) — needs to copy everything after the element
• Operation removeAfterElement, including running time, on both a sorted and unsorted list
  • Runtime O(n)
• Operation findIndex, including running time, on both a sorted and unsorted list
  • Runtime O(log n)— sorted, O(n)—unsorted
• Operation findData, including running time, on both a sorted and unsorted list
  • Runtime O(1) Ammortized

Linked List

• Operation insertAtFront, including running time and insertion strategies

  • Runtime: O(1)
  • Strategies:

  template <typename T>
  void List<T>::insertAtFront(T & t, unsigned index) {
       ListNode * node = new ListNode(t);
       node->next = head_;
       head_ = node; 
  }
  

• Operation insertAtIndex, including running time, on both a sorted and unsorted list

  • Runtime: O(1), O(n) (for an unindexed linked list)
  • Strategies:

  template <typename T> 
  void List<T>::insert(const T & t, unsigned index) {
    ListNode *& node = _index(index);
    ListNode * newNode = new ListNode(t);
    newNode -> next = node;
    node = newNode;
  }
  

  

• Operation removeAtIndex, including running time, on both a sorted and unsorted list make sure that you DELETE the node

  • Runtime: O(1), O(n) (for an unindexed linked list)
  • Strategies:

  template <typename T>
  T & List<T>::remove(unsigned index) {
    ListNode *& node = _index(index);
    ListNode * temp  = node;
    T & data = node -> data;
    node = node -> next;
    delete temp;
    return data;
  }
  

• Operation insertAfterElement, including running time, on both a sorted and unsorted list

• Operation removeAfterElement, including running time, on both a sorted and unsorted list

• Operation findIndex, including running time, on both a sorted and unsorted list

• Operation findData, including running time, on both a sorted and unsorted list

Iterators: used to read data from DS in a uniform way.

Trees

Mathematical foundations: