Below are my notes from CS 32 during the Winter 2014 quarter at UCLA. I hope that current CS 32 students find them useful. I also highly recommend the notes and practice problems by Andrew Forney, one of the best CS TAs at UCLA.

Donations are welcome via Venomo or Square Cash, and help support me in offering ongoing mentorship.

To read the notes offline:

Open a pull request if you find any errors, and I’ll gladly correct them.

Happy studying!



CS 32 Notes

  • Lecture 1: 6 January 2014
    • A Little About Carey
    • Thoughts on Teaching
    • Time for CS
    • Algorithms
      • Algorithm Comparison
      • Data Structures
      • Data Structure + Algorithms
      • Abstract Data Type
      • Object-Oriented Programming
      • C++ Review
        • C++ structs
        • C++ Classes
    • Lecture 2: 8 January 2014
      • C++ Classes Review
        • Constructors
        • Default Parameters
        • Overloading Constructors
        • Initializer Lists
        • When Constuctors are Called
        • Destructors
      • Class Composition
      • Initializer List
        • Construction Order
        • Destruction Order
      • Advanced Class Composition
      • #include Directives
        • #include Guards
        • Include Etiquette
          • When to #include
        • Self-Referential Headers
    • Lecture 3: 10 January 2014
      • Pointers Review
      • Passing Arrays to Functions
      • Copy Constructors
    • Lecture 4: 13 January 2014
      • Pointers Review
        • Dynamic Variables
        • Dynamic Class Members
      • Namespaces
        • Creating a Namespace
        • Using-directives
        • Using-declaration
        • Qualifying Namespaces
      • Copy Construction
        • Syntax
        • Deep Copying
        • The Importance of CC's
    • Lecure 4: 14 January 2014
      • Operator Overloading
        • Basics
        • Syntax for Overloading a Binary Operator
          • Tip: Constructors Returning Objects
        • Returning by const Value
      • Overloading the Negation Operator ( - )
      • Overloading Operators as Member Functions
      • Overloading the Function Call Operator ( () )
      • Overloading the Assignment Operator ( = )
        • Syntax
        • With Dynamic Memory
        • Multiple Assignments
        • Anti-Aliasing of Instances
          • Story Time
        • Swapping Objects
        • Avoiding Code Duplication
      • The Big Three
      • Toss
    • Supplementary from Forney Notes #1: 17 January 2014
      • Initializer Lists
      • C++ Compilation Process
        • Preprocessing
        • Compilation
        • Linking
    • Lectures 5 & 6: 17 January 2014 & 22 January 2014
      • Review: The Big Three
      • Linked Lists
        • The Problem
        • A House Analogy
        • A Train Analogy
        • Initialization
        • Insertion
          • At the Top
          • At the End
          • In the Middle
        • Deletion
        • Processing
        • Destruction
        • Tail Pointers
      • Doubly-Linked Lists
      • Linked Lists Cheat Sheet
      • Linked Lists vs. Arrays
    • Discussion #1 with Forney: 24 January 2014
  • ~
    • Lecture 7: 26 January 2014
      • Inheritance
      • ShieldedRobot & Student Analogies
        • Terminology
        • Syntax
      • Virtual Member Functions

        - Inheritance Function Call Rules

        • Inheritance and Construction
        • Inheritance and Member Visibility
          • Protected Members
        • Recap
    • Lecture 8: 29 January 2014
      • Polymorphism
        • Shape Example
        • Inheritance vs. Polymorphism
        • The Importance of Virtual
        • Superclass and subclass Pointers
        • Virtual Destructors
        • Vtables
        • Summary
      • Pure Virtual Functions
      • Abstract Base Classes
      • Challenge: Diary Class
    • Challenge:
      • Secret Diary Challenge
      • Scrambled Diary Challenge
    • Lecture 9: Stacks & Queues
    • Lectures 10 & 11: 3 February 2014 & 5 February 2014
      • Recursion
        • Thinking Paradigm Behind Recursion
          • "Lazy Person's Sort"
        • The Two Rules of Recursion
        • Tracing Through Recursion
        • Wielding Recursion
        • Static Variables
      • Recursion on Arrays
        • Challenge
      • Recursion on a Linked List
      • Be Careful with Recursion
      • Binary Search
      • Recursion Binary Search
      • Solving Mazes with Recursion
    • Lecture 12: 10 February 2014
      • Review: Recursion
      • Generic Programming
      • Custom Comparison Operators
      • Templates
        • Template Implementation Details
        • Multi-Type Templates
        • Generic Classes
      • Inline Methods
      • STL
        • Vector
        • Summary of
        • Summary of
          • List Iteration
          • Const Iterators
        • Summary of
        • Summary of
          • Iterator Gotchas
        • STL Algorithms
          • find()
          • find_if()
          • sort()
        • Compound STL Data Structures
      • From Office Hours
    • What happened this day? : 12 February 2014
    • Lecture 13: 19 February 2014
      • Compound STL Data Structures, finished
      • Big-O Notation
      • Computing Big-O
        • Big-O Examples
      • The STL and Big-O
    • Lecture 14: 24 February 2014
      • STL's Big-O continued
      • Sorting
        • Rules
      • Selection Sort
      • Stable vs. Unstable Sorting
      • Insertion Sort
      • Bubble Sort
      • Shell Sort
        • h-shorting
        • Shellsort
    • Lecture 15: 26 February 2014
      • Quicksort
      • Mergesort
      • Trees
      • Binary Trees
      • Binary Tree Traversals
        • Pre-order Traversal
        • In-Order Traversal
        • Post-Order Travesal
        • Level-Order Traversal
        • Big-O of Traversals
    • Lecture 16: 3 March 2014
      • Evaluating Expressions
      • Binary Search Trees
        • Searching a BST
        • Inserting a New Value into a BST
        • Finding the Min & Max Values in a BST
        • Printing out a BST Alphabetically
        • Destructing a BST
      • Deletion in a BST
      • Office Hours
    • Lecture 17: 6 March 2014
      • Huffman Encoding
        • Count Frequency
        • Build a Huffman Tree
        • Compression
        • Save the Archive
        • Decoding
      • Balanced Binary Search Trees
        • AVL Trees
          • Insertion
      • The Modulus Operator
      • Hash Tables
      • Hash Collisions
      • Closed Hash Table with Linear Probing
        • Deletion
      • Open Hash Table
      • Hash Table Efficiency
    • Lecture 18: 10 March 2014
      • Sizing a Hashtable
      • Hashing Non-Numbers
      • Hash Table vs. BSTs
      • Tables
        • Hash-Based Indices
      • and
      • Priority Queue
      • Heaps
        • Maxheap
          • Extracting the Biggest Item
          • Adding a Node to the Maxheap
          • Array-Based Implementation
            • Extraction with an array-based Heap
    • Lecture 19: 12 March 2014
      • Last Day of Class
      • Adding Node to an Array-based Maxheap
      • Big-O of Heap Insertion
      • Heapsort
      • Introduction to Graphs
        • Adjacency Matrix
      • Adjacency List
      • List vs. Matrix
      • Graph Traversals
        • Depth-first Traversals
      • Breadth-first Traversals

Lecture 1: 6 January 2014

A Little About Carey

// No PhD in anything. Adjunct professor. // Don't call unless arranged ahead of time.

// Email TA first, and combine questions into // one email for Carey

// He goes to work after this class. Awesome! // He volunteers to teach.

// Prize tickets for a raffle at the end // of class.

// Ice cream at last class if we beat Smallberg's // section at the midterms

// No in-person appointments outside of OH // because of his job.

// He says okay a lot

// Picked a number between 1-60. Carey figured it: 34 // He just flashed numbers in boxes and did it!

Carey is an alumn of '95. He was a departmental scholar, graduating in 5.5 years with BS and MS.

// Made the people who came in late say something // embarrassing about themselves.

// He finished a novel, but is looking for an agent

Check the website often for homework, as well as the PowerPoints. Click on Lecture 1 link.

What we'll learn:

  • Advanced C++
  • Data structures
  • Major algorithms
  • Larger programs

We'll know most of what we need for industry. The technical interview questions will draw from material covered in CS32 material.

Midterm 1: Wed, Janurary 29th

Midterm 2: Wed, Feburary 19th

Final: March 15th, 11:30 am - 2:30 pm

Project 1 will determine if we're ready for CS 32. A lot of work: 20-60 hours/week.

As before, all projects must compile under Visual C++ and clang/gcc.

Thoughts on Teaching

Carey believes understanding is far more important than trying to blast through all the material.

Ask questions!

Save advanced questions for office hours or break, especially for showing off.

Time for CS

Fiboannci sequence, where first two numbers are 0 and 1 and successive numbers are sum of previous two numbers.

0, 1, 1, 2, 3, 5, 8, 13, ...

bool isFib(int array[])
{
    for (int d = 3; d < 20; d++)
    {
        if (array[d] == (array[d-1] + array[d-2]))
        {

A girl named McKenna got it.

Solution:

bool isFib(int arr[])
{
    int j; 

    if (arr[0] != || arr[1] != 1)
        return false; 

    for (j = 2; j < 20; j++)
    {
        if (arry[j] != arr[j-1] + arr[j-2])
            return false;
    }

    return true; 
}               

On our exams, we'll have problems harder than this with less time.

Algorithms

Algorithms are a set of instructions/steps to solve a particular problem.

They receive input data, and produce an output result.

They can be classified by how long they take to run on a particular input and the quality of their results, e.g. the results of a path-finding algorithm, e.g. N cities would take N! steps for a perfect solution to the traveling salesman problem. Instead, we do approximations.

We want to be able to compare algorithmic efficiency and quality.

Our isFib() was of perfect quality, but would take N interations/steps.

How many steps for a N amount of input? N steps? N! steps?

Bad algorithms can kill a program. They make the difference!

Algorithm Comparison

Example: Our program must guess the word a user guessed.

Possible algorithms:

1: Randomly pick words from the dictionary and ask the user if that word is correct.

If there are N words in our dictionary, our algorithm would find it in N guesses. Why not N/2? Because we might guess words twice!

// He pulled out a massive dictionary from his backpack!

2: Search linearly from top to bottom and ask user.

repeatedly:
    j = 0; 
    Ask if word j is the wordj++;

// He keeps selecting

This one will take N/2 steps because words will in the first half or last half of the dictionary. The distribution based on loation would center around the center. This one is twice as fast as the original.

3: Binary search.

SearchArea = the entire dictionary

while (guess not correct)
{
    Pick middle word w in SearchArea
    Ask user
    If done, yay!

    Else, ask "Word comes before or after w?"
    {
        If before
            SearchArea = first half of current SearchArea
        If after
            SearchArea = second half of current SearchArea
    }
}

How long would this take? log2(N).

In the worst case, we keep dividing search area in half until it contains just a single word.

Ex: N = 16 words, how many times to halve till we have just one word left? 4 steps, which is log2(16), as it's 2^(?) = N.

Even for N = 131,072 in 17 steps, log2(N), the number of times we can divide N by 2 until we reach a value of 1.

N = 1 billion? log2(1 billion) = 30.

Compare them! N vs N/2 vs log2(N) steps! This is the power of a good algorithm vs. a bad one. Example, if we had to search through a names database.

Data Structures

// Carey offered a bumped-up grade if we win one // of the top three spots in the Code Day hackathon.

A data structure is the data that'ss operated on an algorithm to solve a problem.

Sometimes, an algorithm can operated just on the data passed into it. The data structure alone is the input data.

Other times, we'll need to create a secondary data structure for solving a problem.

Example: a data structure that lists friendships.

If we went relationship-by-relationship in an unordered list, it would take forever.

A different way to do it, we assign user a number, and alphabetize by user name. Again, we could use binary search, which would take log2(N) steps.

Once we have both users' numbers, we use them and a 2D array to represent relationships.

0   1   2

1   *

2       *

We would typically want it to be symmetric, meaning both people are reflected as being friends with each other.

To check if a friendship exists, we get look up numbers, check (A,B) or (B,A), and see if they're buddies.

HOWEVER, the number of friendships are less than the number of people. Building a 1 bill by 1 bill array would be ludicrous.

Data Structure + Algorithms

Data structures and algoirthms can become very complex, and leave another programmer completely confused.

So every time we create some, we also create simple functions that hide the messy details, e.g. bool areFriends(string user1, string user2), becomeFriends() and breakUp()

This is known as an inteface. They allow us to use and interact with very complex things simply and easily.

The algorithms and data structures are designed together, then create an interface.

Abstract Data Type

Data structures + algorithms + interface = ADT, an abstract data type, used for a particular problem.

In an ADT, the data structures and algorithms are private/secret (the details are irrelevant to the user or other programs).

To solve big problems, we build sub-solutions and put them together.

In C++, classes can be an ADT.

class Name
{
    public: 
        // Interface

    private: 
        // Secret algorithms

        // Secret data structures
}

We build our program from collections of classes.

If every part of our programs knew how every other part worked, then they would be very complex to write, never mind change.

We can change implementation while leaving interface alone.

Example: switching out engines in a car, but we can still drive the same way.

Example: the uniform interface of power outlets; the source of the power doesn't affect us

// Hehe, he's got an air cannon for waking up sleepers

This is the power of abstraction, closely related to encapsulation.

We literally break down big problems into little ones.

Object-Oriented Programming

OOP is based on the ADT concept.

In OOP, programs are constructed from multiple, self-contained classes, interacting only through public interfaces.

C++ Review

C++ structs

We use structs when we want to group related pieces of data into a single variable.

This is defining a whole new type of variable/data.

Syntax:

struct Name
{
    // Members/fields
};

Don't forget the semicolon!

struct declarations are normally found in header files (.h); in source files (.cpp), we can #include "header.h" to use the definition we just wrote.

Keep in mind that all scalar variables have a random, garbage value when uninitialized.

// Haha, the PPT makes fun of David Smallberg, // in this case declaring that Carey's GPA > David's

C++ Classes

Classes and structures in C++ are almost identical (difference was the reversal of private/public by default), but by convention, classes have member functions in addition to member variables.

Lingo: ClassName r, s

r and s are "objects" or "instances" or "variables".

Even the primitive data types can have "instances".

In a class, the data are "member variables" and the functions are called "member functions" or "methods".

Variables defined inside a function are known as "local variables" and used for temporary needs.

Lecture 2: 8 January 2014

// We have MLK and President's day off, which is // why we have another lecture

C++ Classes Review

By convention, data members are always private.

Also, by default, in classes, everything is private. But in structs, everything is public by default. Otherwise, structs and classes are identical in C++.

Public members are accessible by anything anywhere else in the program, but private members are accessible only by members of the class.

"Just remember like how you only touch your own privates."

Heh, then we'll discuss the use of friend.

Encapsulation means we'll hide the details and present only a clean, public interface.

Every class is a self-contained problem-solving unit, an ADT. The rest of the program does not (and should not) know how it works.

In software dev, we'll start with simple versions of classes, and improve them with time, even as the rest of the program doesn't have to change.

Constructors

Constructors automatically initialize new variables.

Syntax for declaration:

ClassName
{
    // Constructor
    ClassName(parameters);
    ...
};

So now when we construct new objects, those arguments must be passed to the constructor (unless we have a default public constructor that doesn't take any parameters).

Syntax for definition:

ClassName::ClassName(parameters)
{
    m_member = parameter1;
    ...
}

There is no return type for a constructor.

The return statement can be used in a constructor, but it just terminates the function. It cannot return a value; it's used to end the constructor early.

Example:

ClassName::ClassName(parameters)
{
    ...
    if (condition)
        return; // End early

    // Don't execute the remaining code below
    ...
}

Also, like other member functions, constructors can be defined inside or outside of the class.

Default Parameters

In the parameter listing, default parameters can be given:

CSNerd(int PCs, bool usesMac = true)
{
    ...
}

This allows:

CSNerd Ned(5); 

// One argument passed; other one uses default

But:

CSNerd Alan;

Will still give an error.

Also, default parameters must be right-justified. No left-side or middle parameters may be default. All can be default. If something is default, everything to the right of it must also be default (or that parameter needs to be moved to the right).

What if we have two defaults and we pass one argument? It'll go to the left-most parameter, even if both parameters accept the same data type.

We pass arguments in the order of the parameters!

Overloading Constructors

We can have multiple constructors, as long as they differ in the number of or type of parameters.

Otherwise, we have ambiguity.

Question: Will the error happen at compile-time or when we actually try to construct an object with ambiguous arguments?

If no constructors are no defined, a default constructor is implicitly defined that does not nothing at all:

"I do nothing at all. I'm like a USC student!!!!!!"

Keep in mind, this means that member variables are left uninitialized.

If we want an array of a class type, we must have a default public constructor that takes no arguments! Alternatively, we can have a constructor that has default arguments for everything. C++ just needs some constructor that doesn't require arguments.

When we define that array, the constructor will run to construct objects for every element in that array.

Initializer Lists

WE can do intialize members with the constructor, OR we can do an initializer list

CSNerd(int PCs, bool usesMac)
    : m_numPCs(PCs), m_macUser(usesMac)
    // No semicolon after the list
{
    // Any other constructor stuff
}

Syntax:

ClassName(parameters)
    : member(value), member (parameter)

The initializer list is with the constructor body definition; don't leave it in the header while putting the body in the source file; that'd be weird.

If we really wanted to, we can mix the two initialization techniques together.

Also, the curly braces are still needed, but they don't need to contain anything.

class CSProf
{
    public: 
        CSProf(const string& name, int age = 39)
            : m_name(name), m_age(age)
        {
            // EMPTY
        }

    private:
        string m_name; 
        int m_age;
}; 

OR:

CSProf(string name, int age = 39)
{
    m_name = name; 
    m_age = age;
}

OR:

CSProf(string name, int age = 39)
    : m_name(name)
{
    m_age = age; 
}

OR:

CSProf(string name, int age = 39)
    : m_age(age)
{
    m_name = name; 
}

Also, these should const string&, for efficiency and to maintain error-checking since we don't need to change the passed string.

Also, all of these can be done outside of the class too:

Default parameters go in the declaration/prototype

class CSProf
{
    CSProf(const string& name, const int age = 39);
    ...
};

CSProf::CSProf(const string& name, const int age)
{
    m_name = name; 
    m_age  = age;
}

The PBCR isn't needed for primitives unless we want to avoid changing variables being passed into the constructor.

When Constuctors are Called

We do not call a constructor when we only create a pointer to an object.

When we do call the constructor:

  • new command
  • New object
  • Array

Destructors

There may be only one destructor in a class.

It de-initializes a class variable once it goes away, i.e. passes out of scope. This will happen automatically.

Syntax:

// In-line, in-class definition
~ClassName()
{
    ...
}

OR:

ClassName::~ClassName()
{
    ...
}

NO return-types or parameters allowed.

// Haha, he embedded the Simpsons theme // song in his PowerPoint

When we don't have a destructor, we never free up needed resources.

Destructors can call member functions.

When are destructors needed?

  • System resources are allocated (e.g. with new)

  • We open a disk file (we need to close it)

  • We open a network connection (we need to disconnect)

There is no way to way to manually call the destructor.

When are destructors called?

  • When local variables pass out of scope (a code block ends)

  • delete is called on dynamically-allocated variables (don't forget the delete!)

Class Composition

This is when a class contains one more other classes as member variables.

Example: class Car contains a variable of type GasTank.

This can embed deeply.

A class may not have a member of its own type, but it may have a pointer to a one of its type.

The outer class may call the public functions of its inner class member, and use them anywhere in the outer class, including in its constructor and destructor.

Initializer List

Before, we've seen constructors be used to intialize a newly-created instance of a class.

They worked like this:

ClassName::ClassName(_type1 arg1, _type2 arg2)
{
    _type1 m_var1 = arg1;
    _type2 m_var2 = arg2;

    ...
}

Another way to do this is with an initializer list:

ClassName::ClassName(_type1 arg1, _type2 arg2)
    : m_var1(arg1), m_var2(arg2)
{
    // A body is required, even if empty
}

These initializer lists will allow us to handle class composition and inheritance. They also allow us to have const and reference member variables, which must be initialized on the same line that they are declared. Trying to do assignment via a regular constructor body is too late.

Example of what won't work:

#include <iostream>
#include <string>
#include <math.h>

using namespace std;

class Test
{
    public: 
        Test(int i)
        {
            m_test1 = 1;
            m_test2 = i;
        }

    private:
        const int m_test1;
        int& m_test2;
};


int main() 
{
    Test t(10);
}

Clang fires back an error that "the constructor for Test must explicitly initialize the member variable m_test2"

For m_test1, it notes that a read-only variable is not assignable, indicating the const property is in effect before we attempted to initialize; it's "initialized" with junk data instead.

This can be fixed with:

#include <iostream>
#include <string>
#include <math.h>

using namespace std;

class Test
{
public:
    Test(int i) : m_test1(1), m_test2(i)
    {
    }

private:
    const int m_test1;
    int& m_test2;
};


int main()
{
    Test t(10);
}

Construction Order

But what happens with the constructors for the classes?

Example, we construct a Nerd object, which contains a Stomach object. Which constrcuctor runs first?

Hint: If the outer class' constructor uses the inner class-type object, the object of the inner class type must be constructed first.

Construction order: inner classes --> outer outer

Another example: Valve --> Heart --> TinMan

Also, note that any members that of a class-type (e.g. strings) will also be constructed first.

Destruction Order

A Nerd destructor may use the Stomach object, so we can't afford to destruct it when it's still needed.

So destruction order goes outer --> inner

Note that destructors will automatically run as long as the variables are automatic ones.

Advanced Class Composition

What happens if we have a member for an outer class, and this member is of a class type that requires parameters for its constructor?

Then, to make this work, we have to pass parameter to the inner class constructor.

Even if Nerd's constructor passes values to its Stomach member variable, that won't be done in time. It has to be done with an initializer list. This list can take arguments given to the outer constructor and pass it to inner constructor, e.g.

CSNerd(int farts)
    : belly(farts)

I don't think C++11's support for default values in the class declaration will work either. We'd have to do an explicit constructor call?

What if we have default arguments? Then the full initializer list not required, but we may still have it.

#include Directives

For headers that are not pre-included as part of the Standard Library, like ones that we create, we need to:

#include "HeaderName.h"

Compare this to the syntax for pre-included headers:

#include <header>

Note the "" and the .h (which is omitted for library headers, except for a few deprecated ones like string.h).

#include Guards

There's actually a problem with the above Watch class example: what if we tried to #include Watch.h multiple times? The answer is an error. C++ does not allow us to redefine something; one of its rules is the One Definition Rule.

Remember that we can avoid this with things declared in different scopes or namespaces (which we'll see shortly).

Avoiding this manually would be tricky. Header files can call upon another; this layering can be very deep indeed.

The solution? Guard our headers.

If we do something like this:

#ifndef HEADER_H
#define HEADER_H

// Class declaration

#endif

Then the compiler will check if HEADER_H has been defined on a list of "code already seen". If it is, it will skip to the next #endif, smartly placed after the end of the class definition.

Otherwise, we #define ("Yes, compiler, this class has now been seen and declared.") and declare the class. The #endif would be ignored in that case.

The #define can "define" any non-keyword, though convention is to use the header name in all caps, with an underscore in place of the dot.

#ifdef // also exists and does the obvious

These macros, as they're known, can be used outside of header files as well.

Additional ones:

#if         // IF
#elif       // ELSE IF
#else       // ELSE
#line       // Used as #line <number> "New file name"

// Any error that follows this #line directive
// will have a line number that uses the specified number
// as a starting point and the containing
// file name as specified by the directive

#error      // Followed by an error message, no quotes
            // Hint: use it in combo with control flow

#pragma     // Specifies compiler options; compiler-specific
            // Ignored if the specific #pragma statement is
            // not supported by that compiler, though stricter
            // warning flags will note the ignoring

There are also predefined macros like:

__LINE__
__FILE__
__DATE__
__TIME__
__cplusplus // Gives an integer indicating the C++ standard
            // that the compiler conforms to; 201103 indicates
            // C++11

__STD__HOSTED__ // 1 if the local C++ implementation includes all
                // standard header files; 0 otherwise

All of these statements with a # preceding them are directives for the preprocessor which will follow these directives before compilation. Note that they are not followed by a semicolon and that they can only reside one line; they are considered ended by the first newline character following them.

To have directives stretch across more than one line:

#directive\
second line of directive

For details: http://www.cplusplus.com/doc/tutorial/preprocessor/

Returning to our watch example:

// Watch.h

#ifndef WATCH_H
#define WATCH_H


typedef unsigned short ushort;

class Watch
{
    public: 

        // Self-explanatory functions

        void setHour(ushort hour);
        void setMinute(ushort minute);
        void replaceBattery();

    private:
        // This implementation has no need for
        // negative numbers

        ushort m_hr; 
        ushort m_min;
        ushort m_perc_batt;

}; // Don't forget the semicolon!

#endif

Note that #include guards are not needed for implementation files; they implement, not declare (though they might #include other headers--which should already be guarded!).

Even with #include guards, headers should not be included unless necessary.

Include Etiquette

Never include a source file (.cpp) in another source or header file (.h). All sorts of stupid linker errors will result otherwise.

Never put using namespace in a header file.

This is known as namespace pollution: any file that includes that header is forced to use that namespace, which can lead to all sorts of errors. Instead, any such statements should be in the implementing source file instead.

Always include header files whenever they are directly needed. Never assume that one header file will include another one. Better safe than sorry, especially since include guards should be implemented for all headers.

When to #include

We don't actually always need to #include.

When we do need to #include:

  • We create an object of that class type

  • We use such an object in any way:

    • We call its methods
    • We return the object itself from a function
    • etc.

When we do not need to #include:

  • When we have a class-type object as a

    • Parameter for a function
    • Return-type for a function
  • When we point or refer to a class-type object

We can still #include, but we do not need to (and indeed, should not, so as to avoid infinite including-type problems, which we'll see in a moment).

Instead, simply declare the class' existence (before it's needed, a forward-declaration):

class UsedClass;

This also speeds up the compilation process, as header files can be quite large.

NB: If we only declare the class' existence but do not include it, and then try to do something that requires the full class definition, then we will get syntax errors.

Self-Referential Headers

If two classes both refer to each other, and both try to include each other's headers, we'll get a compile error.

Why? Because the two files will keep including each other!

Example: A.h includes B.h and B.h includes A.h

Then:

A includes B which includes A which includes B which includes A...

Avoid this via the fact that at least ONE of the two should not need to include the full class!

NB: Class declarations cannot have full inline definitions for any functions that use another class in a way that requires their full definition.

Those function definitions will have to go in the implementing source file instead.

Lecture 3: 10 January 2014

Pointers Review

Note that an array name by itself acts like a pointer (printing it out would give the memory address of the first element) but it is NOT a pointer itself, which is a variable (with memory allocated for itself) that holds the memory address of another variable.

A pointer to an array can be used just as if it were the array itself.

Don't forget that pointers + some number means to move forward in memory by the size of the data type that the pointer is meant to point to.

We do not move forward by bytes but instead by doubles or ints, etc. Eg, move forward two ints and it might go from 9240 to

Set-up:

int nums[3] = {...};

int *ptr = nums;

Equivalent:

ptr[2];
*(ptr + 2);

The pointer arithmetic:

ptr[j] --> *(ptr + j);

This is adding a pointer and an index, but we cannot add pointers together.

Pointer subtraction is defined, with the result being how many integers are between them (if both point into the same array), NOT the number of bytes between them.

Also, commutativity:

j[ptr] --> *(j + ptr);

What happens if we

cout << nums + 1;

nums is an address, so + 1 would print out the address 1 int away.

Passing Arrays to Functions

When we pass arrays, we just pass the address of the start of the array, not the whole entire array itself.

That's why we can have these as equivalent:

void function(int array[]);
void function(int* array);

This means we can do something like:

function(&array[j]);

This means that anything meant to act on an array can be made to act on a later subset of the array instead.

Note, however, that the function will not know the array's size unless we pass in another argument meant to represent that.

-1 is also usable as a subscript value. It'll move backward that many types in memory.

Note that the passed array must have base type matching the expected parameter.

Copy Constructors

We have a problem with the way we're currently designing classes.

Whenever they dynamically allocate memory, open files, open Internet connections, etc., a certain amount of those resources are allocated to the object of that class type.

The problem is if we have a function that takes one of those objects by value, or if we make a new object based on an old one.

By default, C++ implicitly defines a default copy constructor (just like how it defines default constructors and destructors) that does a shallow copy.

The new object's members are copies of the old one's. However, this extends to pointers pointing to anything dynamically allocated, meaning the new object will think the old's dynamic members are its own.

So we need a copy constructor that does what we intend: make a copy, but one that has its own stuff.

Syntax:

// This is still a constructor, so no return-type

// const as we don't need to change the old one
// PBR for efficiency, as objects can have many
// members

//  UPDATE (14 September 2015): 
// According to http://www.cplusplus.com/articles/y8hv0pDG/
// the copy constructor must have one of these signatures:
//      MyClass( const MyClass& other );
//      MyClass( MyClass& other );
//      MyClass( volatile const MyClass& other );
//      MyClass( volatile MyClass& other );
//
// Otherwise, if we have this: MyClass(MyClass other), 
// we're calling the copy constructor as part of the copy constructor!
// Infinite loop! Note that while the pointer versions of these
// could work, they are not considered valid CC's by the standard

ClassName(const ClassName& old)
{
    // 1. Allocate new resources for the new object
    // 2. Copy over the appropriate values from old to new
}

Lecture 4: 13 January 2014

Carey is out sick! Every previous year, he has somehow pulled through and made it to class.

Instead, Smallberg will be teaching today --for 6 straight hours, haha. He's picking up where we left off last lecture.

Pointers Review

Pointers pointing to structs or class-type objects work too. Use * to get to the object via the pointer, the . operator to access its fields/members.

Or do it all in one go with ->

ptr = &Nerd;

(*ptr).numZits;

ptr->numZits;

Smallberg commenting on Carey's use of void for functions that don't take any parameters, a holdover from C that is avoided in C++, haha.

If we have a function that takes a pointer to something, do the call with an address-of:

functionCall(&argument);

This can be avoided by defining the function as taking the parameter by reference.

Dynamic Variables

Traditional, local variables are like rooms in a house. But then we run out of space with so many visiting relatives, and we call up a hotel, which reserves some rooms, much like dynamic memory. The overflow relatives will be placed there instead.

Don't forget to free up the allocated space. Tell the hotel that your relatives went home!

What happens if that relative forgets something in the room? Will that object still be there? Maybe, maybe not. Someone else may have taken the room.

Dynamic memory that is released, and we follow the pointer to it may give the original value, or something totally different altogether.

Don't dereference dangling pointers!

With the new command, we can have dynamic arrays:

cin >> size; 

int *array = new int[size]; 

Make sure the pointer type and array base type match!

array[0] = num1; 
array[1] = num2; 

*(array + #) = ...;

...

delete [] array;

Use delete [] for anything allocated as an array. Use delete for anything allocated as a single item.

Remember: do not delete automatic variables

Do not delete anything twice!

(Unless it's a nullptr; deleting a nullptr is harmless).

There's no need to delete anything that was not dynamically allocated.

Delete means that we're done with memory at some location; the amount of memory used (starting at that location) is handled by the OS's memory allocator.

Just remember that the pointer is left alone (its memory address still points to storage is now deallocated). Change it to null and have functions check for null (before using their pointer parameters) as a safety measure.

Remember that declaring a pointer to an object does not create that object unless we actually do the new command!

Don't mix-up the two versions of delete. Just check how the item to be deleted was allocated (it may not even need delete, as with automatic variables).

If we use the wrong delete, it is undefined behavior, and able to cause a crash.

What if new calls for too much memory? e.g. we want 32 billion bytes of memory (4 billion doubles).

The runtime will throw an exception--and our code can try to catch it somewhere, but if we don't: the program will crash.

Dynamic Class Members

A handy way to customize objects is to have their constructors take arguments that are fed (in some form) to an internal implementation that dynamically allocates stuff to that specified size.

This means we'll only use as much memory as needed (and not have to waste memory trying to plan for the maximum amount likely needed).

Just note that constructor arguments are in the scope of the constructor definition ONLY. To use those arguments in other member functions, store them as data members. Otherwise, they'll go out of scope once the constructor is done running.

Don't forget to add a destructor as well.

Because delete should not be called on something that is uninitialized (that pointer will lead to who knows where), be sure to initialize member pointers to nullptr (e.g. with Pets that may have a favorite Toy).

There are some technical issues with NULL, and so C++11 introduced nullptr. As long as the compiler supports nullptr, we should use it.

Also, remember the big three of memory management: if we need a destructor, then we probably need a copy constructor and overloaded assignment operator as well.

Yes, we can dynamically allocate and deallocate structs and classes.

That is a two-part process.

First, memory is allocated, then second, the object's constructor is called to create it.

Deletion would mean the reverse: the destructor is called to clean up any internal dynamic member variables, then the memory is declared as available to the OS.

A destructor can be used to do something right before a class instance is about to disappear.

Namespaces

In C++, all code is always in a namespace.

Across different namespaces, the same names/identifiers might be attached to totally different things.

Consider how we might a friend named Bob and a boss named Bob. Among our friends, who do not know our boss, it's very unlikely that they'll think we're talking about our boss when we say "Bob".

On the other hand, our coworkers would think in the opposite manner.

The meaning of the name depends on context.

With C++, we strictly control what and how everything is defined in a particular context, as well as control what contexts exist and when they're used.

Previously, we used using namespace std. This meant that all the names defined for the C++ standard library were being used. Whenever we said cout, we meant the one found in , not some other version that we designed ourselves.

If we did not use an explicit namespace, then our code resided in the global namespace.


We can use multiple namespaces, but we can never use more than one at a time.


Creating a Namespace

To place some code into a new namespace, place it into a namespace grouping.

namespace cool 
{
    ...
}

The names in that code now reside in the namespace cool.

To make these names available to other code, use a using-directive (using namespace) or a using-declaration (using cool::)

Note that we can have any number of namespace groupings for a namespace, even across multiple files, and all those names will still be in the same namespace.

Using-directives

To use a different namespace:

We can have a using-directive:

using namespace <space>

This makes all of the names in that namespace available, and, crucially, it does not allow any other use of those names.

Its scope is from the directive's declaration to the end of a block of code, or, if it was declared in the global namespace, till the end of the file.

It is highly recommended that we use a list of using-declarations rather than using-directives, especially at the global level.

Any using-directives should be limited in scope to specific blocks.

Using-declaration

Sometimes, we only want specific names from a namespace, or we have two namespaces that use some of the same names.

To cleanly intermix the two (that is, not use the same names from different namespaces at once), we can use a using-declaration:

using <space>::

Its scope is from the declaration's appearance to the end of a block of code, or, if it appeared in the global namespace, till the end of the file.

Now, we make only specific names available and can switch between namespaces as needed for overlapping names.

Qualifying Namespaces

Having a using-directive or using-declaration isn't strictly necessary.

For example, many of the functions found in the std namespace will have parameters like this:

void function(std::type parameterName);

This means that we're using the name from the std namespace.

Having a using namespace std or using std:: would just mean we could omit the std::, but then we could not define that name.

Thus, everywhere we've seen cout, where it's used as found in , we could have written std::cout.

We’re also able to use this qualification technique even when another parameter has the same name:

void function(std::name parameter, name parameter);

The first will use the name found in std, the second the name found in the global namespace (or in the namespace given by a preceding using-declaration or using-directive).

Copy Construction

What happens when we code something like:

Circle b(...); 

Circle a = b; 

This means that we created an object b of class type Circle.

Then, we created another object a, also of type Circle, which is meant to have the values of B.

This is construction that is based off an existing class-type object.

We will be copying it.

The problem is when we have dynamic members. The memory addresses stored in the member pointers (pointing to those dynamic objects) will be copied verbatim.

Syntax

ClassName(const ClassName& existing)
{
    m_member = existing.member;
    ...

// In general:

    // 1. Allocate memory for the new instance
    // 2. Copy values from existing to new instances
}

So here's a cool thing. We're accessing the member variables of another object. How? A class has access to all its members!

We can talk about private class members within that class. A copy constructor is a member function that can access private class members. There is no additional rule that we can only access the object we're currently operating on. This is precisely so that we can do stuff like copy constructors.

This allows to have calls like:

// Similar to any other constructor call
ClassName b(a);

Equivalent to:

// I actually think assignment operator
// with this. It's a good challenge to 
// identify when = is used, and when
// the copy constructor is called

ClassName b = a; 

This means "initialize b based on a".

This is the old syntax we've seen as an (awkward) alternative: int a(16);

Normally, we use this parantheses syntax for initializer lists instead (which requires them).

Remember that compilers are checking what was passed to functions and looks for what's needed among the pool of defined ones.

A copy constructor is a member function used to create a new variable from an existing one

Note:

ClassName(const ClassName& existing)

We will almost always PBCR. We don't want to change something we're simply copy (unless we have a data member that counts how many times something has been copied, for example) and we want to pass objects by reference for memory efficiency reasons.

The funny thing is if we PBV, which would involve calling the copy constructor for itself? Recursion!

Note that a default one will be provided which copies member variables from the old instance to the new instance. However, this implicit default could be inefficient, doing a shallow copy that copies everything, even if it doesn't need to be copied (e.g. an array with unused elements).

To be more precise, we copy the value of every member variable from the existing instance to the new instance.

// Haha, Smallberg loves seeing the animated robot's head spin

Deep Copying

The problem is when we have class type that involves dynamically allocated stuff.

Then, a shallow copy would copy over the contents of pointers to objects; meaning two objects shared the same dynamic variables!

Thus, if a destructor with delete statements is called on one of them and the other one tries to use that dynamic variable, we'd be following a dangling pointer!

There's all sorts of logical errors that could spring up too: objects that aren't initialized correctly, etc.

To solve this, we need a deep copy, where we copy the what is being pointed to, rather than the pointers themselves. This means that we'll be setting up a new object with new pointers to newly allocated dynamic variables, and then giving those variables values identical to the ones of the old object.

Again, any time a class allocates things in memory dynamically or accesses system resources (e.g. opening a file), it must have a copy constructor implemented!

This copy constructor then will have to create a a new object that has the same amount of dynamic memory allocated and then copies over values into those dynamic variables.

The Importance of CC's

Copy constructors are used *anytime we make a new copy of an existing class instance. We do that when we PBV to functions!

If we say "copy" while describing the operation of something, we're probably calling the copy constructor as part of the process. We call a function that takes its parameters by value:

  1. PBV function is called.
  2. Copy constructor is called.
  3. CC creates temporary class instance that is a copy of the argument
  4. The function acts upon this temporary copy

What happens when we have dynamic data members?

We might have a PBV function that takes a class instance, which calls the CC. The function then acts upon that copy.

The problem: we pass out of scope, and that copy goes out of scope. A destructor is called. The dynamic members are deallocated.

However, the existing instance used as a basis for that copy is also modified. Why? Because the shallow copy had the member pointers pointing to the same locations in memory; both instances thought a particular section of memory belonged to them. This resulted from the dumb copy of pointer to pointer. Both stored the same memory address.

This alone is a problem.

However, that destructor run means that the existing instance is left in an invalid state with a dangling pointer to dyanmic members that it thinks still exist.

Once we have dynamic variables, we must write our own destructor and copy constructor. This is also true for if we open system resources (files, network connections, etc.).

Always ask

  1. Do I need a destructor?
  2. Do I need a copy constructor?
  3. Do I need overloaded operators (especially for assignment)?

"A copy constructor should create an object that looks like the original object, but is independent of it."

We want clones of a person; we don't want the original person and their clones sharing internal organs!

Thus far, we have not needed CC's, because it hadn't made sense (or wasn't necessary) to create a new Zombie, Player, Arena, etc. based off of an existing one.

Instead, when we did need something like that, e.g. with strings, the Standard Library took care of that for us. Dynamic members of library types had their own copy constructors called! This means that once we properly design and implement classes, even if they use dyanmic storage, we can stop worrying about it.

Also, if we return a class-type object from a function that has a non-reference return-type, then the copy constructor is called for that return statement. We'd be returning something that's getting destructed otherwise.

Lecure 4: 14 January 2014

// Smallberg is subbing for Carey again // The original slated sub also got sick // I do not envy such long teaching hours

// Carey must be really sick

// A lot of the following notes are from // Winter Break, when I had lots of time // to study ahead in-depth.

Operator Overloading

Time to make operators work with our class types!

Note that operators can be overloaded in a class, outside of it, or as a friend

Today's serial killer was Ed Gain, inspiration for Hannibal Lector, Norman Bates, and Leatherface in Texas Chainsaw Massacre. He was most definitely not a programming language inventor.

Basics

Operators like +, -, *, /, etc. are really just functions with a different syntax.

Their arguments (often called operands in this context) might fall on either side of them instead of being passed in enclosed in a pair of parantheses.

Just like with functions, we can overload operators, which allows us to tweak their behavior to accommodate the class types that we define. We get control over what it means to "add" two objects of type Country together, as an example.

Most (but not all) operators can be overloaded (and some that can, should not be).

At least one operand to an overloaded operator must be of a class type!


Don't overload , or || or &&

The associativity of the first and the short-circuiting of the latter two will disappear otherwise.

Also, only existing operators can be overloaded; we cannot create new ones.


Syntax for Overloading a Binary Operator

The general syntax is this (for a binary operator):

const ClassName operator +(const ClassName& one, const ClassName& two); 

The operands may be PBV or PBR and not necessarily const. The returned value may be of any type, including void.

The const constraint on the returned type will be explained in a bit.

Note that this particular method of overloading means that the operator will not have access to the private members of the class, and so will rely on its public interface to accomplish its job.

Again, this is a non-member function operator overload.

It is possible to overload operators as member functions, which we'll also see.

Overloading operators should allow them to function in the way we expect, i.e. similar to how the built-in operators function with primitive types. Thus, an overloaded == operator should return a bool, which allows its use in if statements. For example:

if (USA == UK)
{
    cerr << "The Doctor is interfering with the timeline!\n";
}
Tip: Constructors Returning Objects

Constructors can sometimes be thought of as returning an object. That is, that they are replaced in the code by the object they create.

Unless, we assign them to something, these objects are not tied to any named variable, and so are called anonymous objects. They are full objects though, and can even be used as calling objects (i.e., invoke their public member functions).

This is very useful for operator overloading, as we might perform internal calculations for adding two objects together and then input those internal results into the constructor to be returned:

// Calculations

return ClassName(finalResult1, finalResult2); 

This is far cleaner than:

ClassName temp;

// Calculations

temp = ClassName(finalResult1, finalResult2); 

return temp;

In fact, this might lead to issues if the class uses dynamic allocation and we didn't overload the assignment operator correctly (a copy constructor would not be used, as temp was already created and initialized when we called the assignment operator).

Returning by const Value

The reason we often to elect to make the value returned by an operator const is this: automatic error checking by preventing inadvertent changes to a returned object.

Consider this:

m3 = (m1 + m2);

(m1 + m2) is a variable of a class type, but m3 is an object of the same clss type.

It's possible to do something like (m1 + m2).input(), which invokes a member function that changes member variables. If the operator + returns a const value though, this will generate an error.

The default assignment operator will do a shallow copy: it copies the values of member variables from one object to another.

This is also why we're returning by value here: we're copying the anonoymous object created by the addition operation into m3.

If we returned by reference, we'd have a reference to something that might be passing out of scope very soon (e.g. as with the local variables of an operator overload definition).

Think about it this way also: are we generating a value or modifying an existing one?

Ex: 1 + 2 = 3.

3 is a new value (which can be stored [copied] into an existing or new variable) but the assigment operator (which we'll see later) is used to modify an existing one.

Ex:

fullAmount = baseAmount + 25; 

If the + operator returned by constant reference, baseAmount would be changed, even though we likely intended "fullAmount is equal to baseAmount + 25", which does NOT imply changing baseAmount; rather, we just needs value temporarily for a calculation.

So, for the most part, return by const value.

= assignment is an exception, as it explicitly calls for changing an existing object.

Note that if an operator returns a primitive type, returning it as a const is pointless, though legal. This is why the code examples for overloading == omitted the const before the bool return-type.

Overloading the Negation Operator ( - )

When used all by itself, the - is the negation operator, not the subtraction operator.

It is a unary operator that takes only one operand.

Consider a class Account that stores the amount of money in a bank account.

Then, we can overload the negation operator to support Account-class objects:

class Account
{
    public:
        ...
        Amount(double money);

        // Short definitions can be inline
        double amount() const
        {
            return m_amt;
        }
        ...

    private:
        ...
        double m_amt;
}


// Declaration of negation operator overload
const Account& operator -(const Account& old);

int main()
{
    ...
}

// Negation operator overload implementation
const Account& operator -(const Account& old)
{
    return Account( -old.amount() )
}

Since this overload happens outside of the class, we need to use public member functions to implement the overload. In this case, we also use the default behavior of the negation operator with a primitive type.

This is the power of abstraction: we can build and build on top of previous work without worrying about how it works--so long as it works, haha.

Overloading Operators as Member Functions

Operators can be overloaded as class member functions too; this will grant them access to all private members--not just those of the calling object, but of any defined class object too (e.g. the second operand is also a class object).

With binary operators, there's a syntactic quirk: there is only one parameter, as the calling object serves as the first operand.

+, -, , /, = , etc. are all binary operators, but the the calling object is the first operand; the operator literally *is a member function!

Ex: account1 + account2

Here, account1, the calling object to the member function operator + is the first operator, and account2 is the second operand.

Note that if we're not changing the calling object (which is likely if we're returning a const value), then the whole member function should be a const member function.

Ex:

class Account
{
    public:
        ...
        const Account operator +(const Account& other) const;
        ...

    private:
        ...
};

    // The following implementation could be
    // in a separate file [indeed, where it should be]

// Here, the calling Account is "self" in a sense
// The other is called "other"

Don't get confused by the syntax:

Our return-type is a constant Account-type object.

We're overloading the +operator in the scope of the Account class only.

We implicity consider the calling object to be the first operand to this binary operator.

We pass the second operand (which also happens to be of a class type) by reference for efficiency.

This member function operator overload promises not to modify its calling object, denoted by the const at the end of its declaration and the first line of its definition.

// Addition
const Account Account::operator +(const Account& other) const; 
{
    double total = 0;

        // m_amt of the calling object
    total += m_amt;

        // As a non-member, this would have required
        // public accessor function
    total += other.m_amt; 

        // Create and return an anonymous object
    return Account(total);
}

Overloading operators as member functions is highly advocated, as it follows the spirit of OOP--and avoids the messiness of having a bunch of operator overload declarations and definitions in the source file for main().

Imagine seeing all those for many different classes!

Here's another operator overload implemented as a member function:

// Subtraction
const Account Account::operator -(const Account& other)
{
    double total = m_amt - other.m_amt;

    return Account(total);
}

Overloading the Function Call Operator ( () )

The FCO, a.k.a, the function application operator (FAO), can also be overloaded (which must be done as member function).

This will allow us to create objects that can act like functions, known as function-objects:

class Multiplier 
{
    public:
        Multiplier(int m): multiplier(m) 
        { /* EMPTY */ }

        // Mulitiplier
        int operator()(int x) 
        { return multiplier * x; }
    private:
        int multiplier;
};

int main()
{
    // Create the multiplier (which has a base value)
    Multiplier base_mult(5);

    // Use the multiplier; prints out "20"
    cout << base_mult(4) << endl;
}

Here, a Multiplier class is created. Its objects can be passed something to multiply by. This could, of course, be extended to far more complex cases. What differentiates this from a normal function then? Why not create a function int base_mult(int number)?

Because function-objects can save state.

For example, base_mult might multiply by 1 more each time that it is invoked, thanks to some internal counter that's implemented as a private data member. This is far better and cleaner than using static class variables or--compiler forbid--global variables.

Overloading the Assignment Operator ( = )

The assignment operator = is a special overload that is integral to more complex classes.

Say we have a object that already exists (i.e. declared and initialized) and we want to set it to the value of another object that also already exists.

In that case, we won't be using the copy constructor but the assignment operator (=) instead.

Why is this? The copy constructor is a constructor: it builds new class instances based on existing ones.

It's actually quite clever, taking an existing one as an argument and then building a new one that is an independent clone of the old one.

Still, changing an existing instance based on another existing one is a useful operation, e.g.:

int g = 0; 
int f; 

f = g;

Defining our own assignment operator is a necessity when we have a class that dynamically allocates anything in memory.

See, like with the copy constructor, C++ defines a default assignment operator for us if we don't have one explicitly defined. It'll do a shallow copy, which is ineffective or even dangerous for anything that uses the heap or system resources.

Instead, we'll overload the operator as a member function, which will allow us to handle all the private variables that wouldn't be accessible to an operator overload outside of the class.

Overloading outside of the class means we would have to implement everything with public member functions only.

Friends are an exception.

An example of where an overloaded = is needed:

Circ foo(1, 2, 3);
Circ bar(4, 5, 6);

bar = foo; 

Primitive types have this functionality built-in. The old values are stomped over by the new ones.

Our new, programmer-defined types have to have their own operations defined. We could have it do anything, e.g. assign the old instances' values to the new. But we could launch a nuclear strike afterward too if we wanted to. This would totally defy the typical expectations of other developers though.

Syntax

Here's how to do so:

ClassName& operator=(const ClassName &source)
{
    member1 = source.member1;
    member2 = source.member2;

    return (*this);
}

Note:

  1. The keyword operator which indicates that we're redefining how an operator behaves.

  2. We return a reference to an object of the class type.

  3. The passed source object is passed by constant reference.

  4. We return a reference to the changed destination object.

The assignment operator can be seen as a sort of .setEqualTo() member function for an object, which is why it accepts only one operand here.

Why? The calling object is treated as the first operand.

We could use the new operator as bar.operator=(foo), but this would render the overloading operation pointless. Instead, we get the natural syntax we're used to: bar = foo

Note: the use of = alone does not trigger the overloaded operator. It's if it's an existing and an existing, rather than a construction and an initialization, which would be done with the copy constructor.

void f(Blah b) { ... }

Blah b1; // Constructor

Blah b2(b1); // CC

Blah b3 = b1; // CC

b3 = b1; // Overloaded assignment

f(b3); // CC

With Dynamic Memory

When we have dynamic memory allocation with a class, we'll need an overloaded assignment operator.

Here's what it'll have to do:

  1. Free all dynamic memory currently used by the target/destination object/instance. (We can't afford to have a memory leak)

What if the destination instances uses MORE memory than what the source instance does!

We can't just copy over values, because then we'd forget about the memory we never deallocated; our tracking variables (if their values were copied over from the source instance) wouldn't include them.

So we'd have a MEMORY LEAK.

Thus, DEALLOCATE existing memory before continuing.

Also, the destination instance's original values are irrelevant, since we're gonna replace them.

Why was this not a problem with copy construction? Because we were creating a brand new object, which meant there was no memory previously allocated for it. There's no memory to leak there, though both new and old will end up in invalid states if they accidentally share the same memory.

In the PowerPoint, it should read that b is destructed before a. It happens in reverse order of creation.

  1. Allocate new memory (we need a new pointer to a new section of memory, so as to not overlap with the source instance; this is why we deallocated our old memory)

  2. Explicitly copy the contents of the source instance to the destination/target instance.

Steps 2 & 3 are basically what we did with the copy constructor.

  1. Return a reference to the target instance.

Example continued:

ClassName& operator =(const ClassName &source)
{
    member1 = source.member1;
    member2 = source.member2;

    delete member3;

    member3 = new _type;

    *member3 = source->member3; 

    return (*this);
}

QUESTION:

Why should an overloaded assignment operator free any dynamic memory currently used by a target class instance before allocating new memory and then copying over the contents of the source instance?

ANSWERED: See above after #1


Can we explicitly call the destructor and the copy constructor? Possible, apparently, but very tricky, and would require a language feature we don't know yet.

Also, deleting the existing members then the calling the CC would compile, but create another object, a temporary one, which disappears immediately after the assignment operator overload definition.

We will get to a technique that allows us to pull this off. This allows us to avoid the duplication of already existing code.

Multiple Assignments

The reason we return (*this) is so that we can do something like the following:

// class Foo has already been declared
// and implemented elsewhere,
// and stores a single unsigned int

Foo first(3), second(4), third(6);

first = second = third;

Then first and second will have third's value of 6.

How does this work? The assignment operator in C++ has a right-to-left associativity, meaning we move right to left.

second is set to third's value.

The result of this is a modified second, which is returned from the (=) operator function, and used for setting the value of first.

So the expression looks like this as it progresses:

first = second = third;

first = second; // second has third's value(s)

first;

The return (*this) line is an example of a member function of a variable returning the whole variable!

Assignment is actually returning a value, the new value of the lvalue on the rightmost binary assignment:

x = n = k;

x = (n = k); // Parantheses not needed

x = (n) // n has k's value

It's relay of values from right to left.


N.B.: this is a pointer to the calling object; we dereference it in order to do anything with it.

We follow the this pointer to the calling object, and then return a reference to it.

We could return a copy, but this is wasteful. Pass on the modified paper rather than a copy of it.


Anti-Aliasing of Instances

There's one problem with our assignment operator as-is: what if it's invoked upon an object (that has dynamically-allocated memory in use) to set it equal to itself?

E.g. x = x

"If you don't want to do anything, just write an empty statement, semicolon."

But we do assign objects to themselves; this happens when we have a function that takes arguments and we pass the same objects to it.

It may happen accidentally when stuff nests deeply.

This is known as aliasing, when two different references/pointers lead to the same thing, which can cause unintended issues.

We'll have a problem. As is, it will deallocate, then re-allocate, then copy over uninitialized junk data over itself. We'll have lost our original data, which can lead to all sorts of unintended consequences.

The solution is simple: check for self-assignment:

(Our code is valid for when the operator is called on two different objects)

"The one thing that distinguishes one object from another is if they're in the same place in memory."

Analogy: Where are persons A and B? They're in the same place in space-time? Same person. Different places? Different persons.

ClassName& operator=(ClassName &source)
{
    if (this == &source) 
        // Source is passed by reference; 
        // we need to compare addresses 
    {
        return (*this); // No changes made
    } 
    ...
}

Why return right away? Assignment's goal is to make the lvalue a clone of the rvalue. If they're the same instance, this is already true. Just return the instance.

The following is NOT a correct check:

ClassName& operator=(ClassName &source)
{
    if (*this == source)
    {
        ...
    }
}

Why? Because what if the source instance just happens to have the same value(s) as the target instance, but is a separate, distinct instance? This doesn't actually check if source and target are the same instance; it's actually checking if they're equivalent instances.

The first check does, as it's comparing memory addresses, not values.

This also lets us avoid worrying about overloading the == operator as well (and we'd have to do manual checking member by member within the overloading definition for ==, we might never realize our mistake unless we had a class with pointer members and we compared addresses instead of values [perhaps by mistake] and realized that that was it exactly what we needed).

Instead, here we simply compare memory addresses; different objects should be not at the same place in memory, unless things have gotten really screwed up.

Aliasing comes up in many places. Any time we have a function that takes references or pointers to objects of the same type, we need to check if they're pointing to the same instance, which is something that can come up unintentionally deep in some algorithm.

Example:

void transfer(Account& from, Account& to, double amt)
{
    from.debit(amt):
    to.credit(amt);
}

transfer(arr[i], arr[j], 2000);

What if i and j are equal? We must account for any situation where we might be acting upon the same object. This one would have no net effect: it loses 2000, then loses 2000. BUT, a change in requirements later on may change our implementation and if we forget about this harmless aliasing issue, then it can turn harmful.

{
    ...
    if (amt >= 10000)
        fileForm(...);

Filing unnecessary forms has consequences. What happens if we transfer money from an account to itself then we filed a form for no reason, bringing down the legal consequences.

So, check for aliasing:

{
    ...
    if (&from == &to)
        return;
    ...
}

This is something that should be handled at design time, after we've designed the functions' interfaces in specs. We need to determine what we should do in some case, e.g. with aliasing.

Story Time

This happened with an AI researcher where his dissertation was a program that discovered mathematical theorems. He gave it guiding principles (look for stuff that occurs rarely or frequently) and and got it to try to prove theorems, and had it identify interesting things.

The program discovered that numbers have factors, then examined those and eventually prime numbers.

He got hired by a project commissioned by the Navy, where they set up a game to discover interesting tactics.

In the simulation, one thing that occured would be to fire one missile from one ship to another ship.

So the program found a situation where firing a missile on itself was useful: if the enemy ship fired on itself (at the same time that we fired on it), it would sink faster! The function didn't account for the aliasing contingency.


QUESTION:

Does this overloaded assignment operator work even when we have nested classes that all use dynamic memory?

Possible self-answer:

Yes, if it correctly handles the class data member value transfers correctly.


Swapping Objects

As we learned before, we can't just directly exchange variables (a = b; b = a). We'll lose one variable's values otherwise.

Instead, we need a temporary clone to allow us to transfer values. It's like Hanoi Towers!

This is trivial once we have our copy constructors and assignment operators. This is slow though, with all sorts of allocation and deallocation happening.

What if we just swapped the data members and pointers (to objects) instead? We can do that! (Again, we'll need the 3-step temporary copy value transfer method).

This swap() function would have to be a member function of the class in order to work, but this would be blazing fast!

The temporary variables should be automatic variables.

Things get complicated once we have classes within classes though...

Avoiding Code Duplication

Wait, this is how we can avoid having to do all that work with code that basically duplicates the destructor and copy constructor!

THIS IS WHAT I THOUGHT ABOUT BEFORE BUT COULDN'T FIGURE OUT HOW TO IMPLEMENT!

ClassName& ClassName::operator=(const ClassName& source)
{
    if (this != &source)
    {
        ClassName temp(source); // We use the CC

            // Remember the goal of assignment
            // Swap variables using a temporary value

            // The below is equivalent to this.swap(temp)
            // Remember that class methods implicitly point
            // the `this` pointere to the calling object instance

        swap(temp); // Where calling object is destination
    }
            // Temp is destructed; its scope was inside that
            // `if` conditional block
            // We avoiding duplicating the destructor

    return *this;
}

This is so much simpler! What Smallberg just showed us is the copy-and-swap style in modern C++ (late 90s onward).

Just make swap() work well!

Also, we don't have to check for self-assignment, the code would still work, as we'd be copying to a temporary, swapping values, and the original would just get its original values back. This is fucking awesome!

Summary of the two approaches:

Traditional assignment operator implementation:

  1. Deallocate all dynamically allocated memory currently used by the calling instance.

  2. Allocate enough memory to hold the source's contents.

  3. Copy over the memory contents of the source instance to our newly allocated memory

  4. Return a reference to the calling instance

Copy-and-swap approach:

  1. Create a temporary copy of the source instance using the copy constructor.

  2. Swap the temporary copy's values with our calling instance's value. This entails swapping variable values, including pointers to objects, etc.

  3. Return a reference to the calling instance. The temporary copy went out of scope and was destructed automatically. We avoid code duplication and unnecessary overhead.

The Big Three

The book notes that

"The copy constructor, the = assignment operator, 
and the destructor are called the big three because 
experts say that if you need any of them, you need all three."
(p. 464)

Why would we need all three? If we have a destructor, then we likely have something allocated dynamically, which means that new copies made from old, existing variables will have to be properly initialized with a copy constructor, and existing variables being set to the value of another existing variable will require an overloaded assignment operator (=).

Toss

Supplementary from Forney Notes #1: 17 January 2014

Initializer Lists

Say we have class:

class Test
{
    public: 

        Test(int number, string name)
        {
            m_member1 = number;
            m_member2 = name;
        }

        int getMember();
        bool isEmpty();

    private:

        int m_member1;
        string m_member2;
};

Normally, when we construct a new instance of the class, say Test t1, then the data members of the class are declared before any code in our defined constructor is executed.

This can be seen as:

int main()
{
    ...
    int m_member1;
    string m_member1;

    m_member1 = number;
    m_member2 = name;
}

That is, a normal constructor that assigns passed arguments' values to data members is like declaring the members and then assigning them.

To get the equivalent of initialization at instantiation, we need an initializer list. This will pre-empt any default constructors for data members of other class-types as well.

We need this for when other classes don't have a default constructor and need arguments passed to them, or we want to customize our new object at creation. This also improves performance, as we're avoiding the extra step that comes from declaring then assigning. Instead, we do it all in one step.

Syntax:

ClassName(_parameters)
    : member1(parameter1), member2(parameter2), ...
{
    // CONSTRUCTOR BODY
}

OR:

// Initialization list style
  Survivor::Survivor ():
      m_name("Rick Grimes"),
      m_infected(false),
      m_health(100),
      m_gun(Weapon("Beretta", 30)) 
      {}

Note:

  • No semicolon after initializer list
  • Initializer lists will initialize members in the order in which they are listed in the class definition, regardless of their order in the initialization list
  • Curly braces must still follow for the constructor definition, even if it is an empty {}
  • Initializer lists are the only way to initialize constant data members

So the rule of thumb is this: use an initializer list whenever possible, and it is especially preferable for non-primitive types.

C++ Compilation Process

Compiling a C++ program is actually a multi-step process:

  1. Preprocessing

  2. Compilation [Optimization thrown in here as well]

  3. Linking

And we end up with an executable file.

Preprocessing

Preprocessing deals with preprocessor directives like #include and #define. The # indicates a preprocessor directive.

#include replaces the file name with the file contents (or at least the identifiers for later resolution).

#define works before compilation, and replaces a defined identifier in code with whatever literal we associated with it.

#define LOUD_STRING "YELLING"
#define COOL_INT 42

int main ()
{
    cout << LOUD_STRING << endl;
    cout << COOL_INT << endl;
}

What's the difference between const and #define? The former obeys scope rules; the latter will be applied globally, even across files (how else would include guards work?). Note then that #define should NOT be used for any sort of variable that needs to be changed throughout the course of a program.

Note also the preprocessed nature of #define means that we won't take up memory needed for another variable, which usually shouldn't be something we need to worry about.

Compilation

Now, compilation occurs (which really encompasses the use of an assembler as well, where we go from C++ source code to assembly code to machine code [binary]).

Each source code file is transformed into an object file of machine code.

Linking

The linker follows, checking that for every declaration, we have a definition. We should never hit anything in code and go "Wait, what's that?". All the appropriate dependencies will then be grouped together and made into an executable file.

Lectures 5 & 6: 17 January 2014 & 22 January 2014

Review: The Big Three

[At Smallberg's lecture, which replaced a standard Friday discussion]

Up until now, we've dealt with language issues, e.g. when default 'structors and operators need to be replaced with our own custom definitions.

Review:

class Blah
{
    public: 

        Blah(const Blah& other);
            // No other constructors declared
        ...
};

Questions:

  1. Is there anything interesting about this class?

Answer: It's impossible to create a Blah object. Here, we can only create a Blah as a copy of another Blah. It's chicken and the egg, but with no resolution. It's an infinite regression toward nothing.

Can't we do Blah b2(b1)? NO.

"This class is useless!--not this class, CS 32."

Rules:

  • A default constructor is provided only when we do not declare any constructors for a class (including copy constructors).

  • A default copy constructor is provided only when we do not declare a copy constructor.

  • A default destructor is provided only when we do not declare a destructor (which would call the destructors of other classes for any data members of those class types). It does nothing for primitive types, however, e.g. a pointer to a dynamically allocated Zombie pointer.

  • If we do not declare an assignment operator for a class, the compiler will provide one for us.

This sounds like Miranda Rights for classes, haha. "If you cannot afford a lawyer, one will be provided for you."

Anytime a class of ours contains a low-level resource handle (e.g. a pointer to something dynamically allocated), we're gonna need the Big Three: destructor, copy constructor, assignment operator.

On the other hand, if our class is built out of other class types that are already encapsulated and self-cleaning, then we don't need to worry about our class's 'structors and operators.

Linked Lists

The Problem

It's time for our first major data structure!

Let's say we have a collection of objects, and we wanna do stuff with it.

What are our options for doing so?

Originally, our only option for grouping together like things was a fixed-sized array.

Smallberg just proposed an array that layed out its elements throughout its indices. Say we had a group of names represented as std::string's.

We quickly find that inserting, deleting, sorting, etc. objects is very annoying.

Someone finally answered "Put them all at one end of the array.". Someone else also suggested having a counter for the number of the names. Now, that counter is also the index of the next available element. We don't have to search for an available slot before adding an item. Searching is also not bad: we can stop once we know that we've reached the end of the array.

Here's the annoying one: deleting an item. We could replace it with the empty string, but that would throw off the counter. Deleting is made easy, but complicates other common collection-related operations. This also assumes that an empty string is not important for representing something. It'd be like excluding 3 from the set of all real numbers for no real reason.

So instead, we want to make sure that the array is always containing stuff we care about in the early part of it. We can shift everything over, which is needed if order matters. If order does not matter, than we can just take the last item and replace the deleted one with that, then decrement the counter. If the deleted item was at the end, we can just decrement the counter.

Note though that finding an item takes time, and preserving order is annoying. And of course, the major downside is that we're limited in size.

What if we did know the max size needed?

A House Analogy

Einstein expects a large shipment of animals but will rent houses one at a time, keeping track only of the last-rented house, and in each house, he'll note on the fridge where the next rented house is. The last note will say "end of list".

This is necessary because he doesn't know in advance how many he'll need.

His algo:

  1. Rent a new empty house
  2. Put his animal in the empty house
  3. Note where the next house in the list is
  4. Update his chalk board to know where his last-rented house is

Do it with a struct to represent houses:

struct House
{
    string name; // animal we're holding
    House *next; // address of next house
};

Outside of the struct, we'll have a special last-rented pointer to know where the last house is.

The last house identifies as the last one in the list via nullptr for its fridge note to the next house: there is no next house.

A Train Analogy

[The following are notes written before, during, and after Lecture 6]

Picture a train. Its cars are linked together. Each car knows what the next car is.

If we start with knowledge of what the first car is, and mark the last car (the caboose) as such (some sort of marker to let us know that we've reached the end of the train), then we can just start at the beginning and go from car to car until we hit the caboose.

This knowledge of the first pointer is known as the head pointer. Each train car can be a class or struct-type object, containing its data members as well as a pointer to the next car. This next pointer is how we know where to go, well, next!

In code, this will look something like this:

// Items in a linked list are called nodes

// The container for our nodes and their data
struct Car
{
    std::string m_name;
    Car* m_next; 

    // Note: a class cannot have a data member
    // of its own type; that'd be weirdly recursive
};

This is not a pointer to itself, but a reference to another Car.

This is a self-referential data-type.

To make things easy, the linked list itself will be held in a class. Here's the sort of stuff we can do with it:

Also, the node struct is easily defined in another header file elsewhere or done as a private member of the containing class.

#include <string>

// A container for our linked list
class Train 
{
    public: 

        // Create a new linked list Train
        Train();

        // Dive-bomb the current Train
        ~Train()

        // Add nodes/Cars to the Train
        void addCarFront(const std::string& name);
        void addCarMiddle(const std::string& name);
        void addCarRead(const std::string& name);

            // Each of these addNode() functions
            // will have different implementations
            // in order to work correctly!

        // Delete an individual Car, based
        // on its characteristics or its 
        // position in the Train
        void deleteCar(const std::string& name);
        void deleteCar(const int& slotNumber):

        // Find the position of a node
        int findCar(const std::string& name) const;

        // Process the list
        // This could mean doing stuff
        // with node data, ordering nodes
        // (e.g. alphabetizing), etc.
        void print carsList() const;


    private:

        int m_numCars;
        Car* m_headCar; // The head pointer
};

To know when we've hit the last node in a linked list, the last node will have a next pointer that points to nullptr. This means that it's not meant to go anywhere next, and so we know that we've reached the end of the linked list.

Note that EVERY linked list must have at least a head pointer (if we reversed head and tail, then we could really call the "tail" the new head).

We won't know where to start with the linked list otherwise. We have to have able to start at the head and follow next pointers to the next node till we've reached the end.

See, that's the only thing linking everything together: the pointers. The addNode() methods are just dynamically allocating new nodes in memory. We don't have an array of nodes (that'd be dumb; we'd be dealing with the limitations of arrays then, something we probably wanted to avoid by using a linked list).

Initialization

Initialization of a linked list is a necessity. The last thing we want to do is accidentally follow a head pointer to what we believe is the start of a linked list only to discover (perhaps very belatedly) that it was a dangling pointer.

This happens with the containing class' constructor.

Train()
{
    m_head = nullptr; 
}

When the head pointer is set to the nullptr, we know that the linked list is empty. A list is empty at creation, so have the constructor set the head pointer to nullptr.

Insertion

Cool, now let's add some nodes!

Note that we can add nodes to the top, middle, or bototm.

Adding to the top is easiest and fastest when compared to the other two. Always try to choose the simplest one that best suits our goal. Work smart, not hard.

At the Top

Adding to the top has two possible cases.

  1. The linked list already has nodes in it.
  2. The linked list is empty.

Reminder of the node struct:

struct Car
{
    std::string m_name; 
    Car* m_next;
};

To add a new node:

void addCarFront(const std::string& name)
{
    // Create a new Car
    Car* latest = new Car; 

    // Customize the Car
    latest->m_name = name; 

    // Link new top node to what
    // was previously the top node,
    // which is given by the head pointer

    latest->m_next = m_head; 
        // m_head is part of Train

    // Update the head pointer to point
    // to the new top of the list
    m_head = latest; 
}

This will work even if the list is empty!

Without comments:

void addCarFront(const std::string& name)
{
    Car *latest = new Car; 
    latest->m_name = name; 

    latest->m_next = m_head; 
    m_head = latest; 
}

The general algo:

  1. Allocate memory
  2. Initialize the node
  3. Link the node to the former start of the lsit
  4. Re-aim the head pointer at the new node
At the End

If we're adding nodes to the end of a list, we must again consider if it is empty or filled (perhaps partially).

void addCarRear(const std::string& name)
{

In the empty case, things are easy: we can just consider it to be adding to the top of an empty linked list! There is no beginning or end, so make the Beginning:

    if (m_head == nullptr)
        addCarFront(name);

If the list already has nodes, then we need to:

  1. Follow the links to the current last node
  2. Allocate a new node using new
  3. Add data to the new node
  4. Set the next pointer in the new node to nullptr
  5. Update the former last node to point to the new last node

The hard part is following those links, something called list traversal.

We're gonna use a loop to go from node to node:

Car* temp; 
temp = m_head; 
// Point to 1st node, thanks to head pointer; start at top of list

while (temp->next != nullptr) // Go till we hit the current last node
{
    temp = temp->next; 
    // This changes temp to point to the next node
    // We CANNOT use temp++ (we're not in an array)
    // This means temp will now point to the next node
};

The advantage of linked lists means we can jump around in memory, thanks to pointers. If we had kept a counter of the number of nodes, we could use a for-loop. This current loop could be used to count the number of items in the list.

An alternative loop syntax (as shown by Smallberg in video lecture):

for (Car *temp = m_head; temp->next != nullptr; temp = temp->next)
{
    ...
}

However, this is not useful for this function, as the temp variable will go out of scope and disappear. Instead, the first syntax is better here. The second one is best for, say, a print() function.

We could resolve this by declaring temp before the for-loop.

Once we hit the last node:

Car *latest = new Car; 

latest->name = name;
latest->next = nullptr; // This is the new latest node!

temp->next = latest; 
// Access the next pointer of the old last node 
// Have it point to our new last node

Full version of adding a node to the end:

void addCarRear(const std::string& name)
{
    // If list is empty, just treat it as adding to the front
    if (m_head == nullptr)
        addCarFront(name);

    // Otherwise, traverse list to last node
    Car *temp = m_head; // Start at top of linked list

    // Keep going till next pointer shows nullptr;
    // This marks the last node as the end
    while(temp->next != nullptr)
    {
        temp = temp->next; // Follow next pointer to next node
    }

    // Found last item if here in the code
    // Create new node
    Car *latest = new Car;

    // Customize latest Car and mark it as being the end
    latest->name = name;
    latest->next = nullptr;

    // Link old last node to new last node
    temp->next = latest;
}

Without comments:

void addCarRear(const std::string& name)
{
    if (m_head == nullptr)
        addCarFront(name);

    Car *temp = m_head; // Start at top of linked list

    while(temp->next != nullptr)
    {
        temp = temp->next; // Follow next pointer to next node
    }

    Car *latest = new Car;

    latest->name = name;
    latest->next = nullptr;

    temp->next = latest;
}

Story from Kim!

She was apparently a Hollywood actress before deciding on a CS career. She's been on several TV shows, haha.

In the Middle

Inserting in the middle comes up when we have an ordered link list, e.g. an alphabetized one and insertions need to happen at the right spots.

The basic algorithm in pseudocode is this:

void addCarMiddle(std::string& name)
{
    if (list == empty)
    {
        addCarFront(name);
    }
    else if (new node belongs at top of list)
    {
        // This happens if the new item is smaller than
        // earlier in the alphabet, etc.
        addCarFront(name);
    }
    else if (new node belongs somewhere in the list)
    {
        // Traverse list till we find node just ABOVE
        // the proper spot

        // Create the node

        // Link the node into position right AFTER the
        // the node ABOVE its proper position
    }
}

In actual code:

void addCarMiddle(const std::string& name)
{
    // List is empty: new node belongs at top
    if (m_head == nullptr)
    {
        addCarFront(name);
    }
    else if ( // Item belongs at top of list )
    {
        addCarFront(name);
    }
    // Item belongs somewhere in list
    else
    {
        // Traverse list to find node above insertion point
        // Start with head pointer to top of list

        Car *above = m_head;

        // Keep going; last possible place we can go to
        // is last node; if we go there, the new item
        // belongs at the end; use addCarRear() for that

        while (above->next != nullptr)
        {
            // Code to see if we've found the node
            // just above where our new node should be

            above = above->next; // Move down a node
        }

        // Allocate and customize new node

        Car *latest = new Car; 
        latest->name = name;

        // Link new node to the one below and the one above

        // Link to node after new node (the old next node)
        // This MUST be done first, or we lose track
        // of the rest of the list

        latest->next = above->next; 

        // Link to above node

        above->next = latest;
    }
}

Without comments:

void addCarMiddle(const std::string& name)
{
    if (m_head == nullptr)
    {
        addCarFront(name);
    }
    else if ( // Item belongs at top of list )
    {
        addCarFront(name);
    }

    else
    {
        Car *above = m_head;
        while (above->next != nullptr)
        {
            above = above->next;
        }

        Car *latest = new Car; 
        latest->name = name;

        latest->next = above->next; 
        above->next = latest;
    }
}

The same example, but with code for alphabetical comparison of names (this is assuming the list has been alphabetized consistently):

void addCarMiddle(const std::string& name)
{
    // List is empty: new node belongs at top
    if (m_head == nullptr)
    {
        addCarFront(name);
    }
    // Item belongs at top of list
    // The head pointer gives us the current top item

    else if (name < m_head->name)
    {
        addCarFront(name);
    }
    // Item belongs somewhere in list
    else 
    {
        // Traverse list to find node above insertion point
        // Start with head pointer to top of list

        Car *above = m_head;

        // Keep going; last possible place we can go to
        // is last node; if we go there, the new item
        // belongs at the end; use addCarRear() for that
        // The code below also works 

        while (above->next != nullptr)
        {
            // Code to see if we've found the node
            // just above where our new node should be

            // It's possible to string together next->'s
            // but this is terribly confusing and possibly
            // dangerous, as we're not checking that
            // the pointer is not nullptr

            if (name >= above->name && name <= above->next->name)
                break;

            // The first check may not be necessary if the
            // list was maintained correctly; this depends
            // on implementation and application. Think it through.

            // Otherwise, keep traversing
            above = above->next; // Move down a node
        }

        // Allocate and customize new node
        Car *latest = new Car; 
        latest->name = name;

        // Link new node to the one below and the one above

        // Link to node after new node (the old next node)
        latest->next = above->next; 

        // Link to above node
        above->next = latest;
    }
}

The same code, but adding via slot number (with the first slot being 0):

// New parameter for slot number
void addCarMiddle(const std::string& name, int slotNum)
{
    // List is empty: new node belongs at top
    if (m_head == nullptr)
    {
        addCarFront(name);
    }
    // Item belongs at top of list
    else if (slotNum == 0)
    {
        addCarFront(name);
    }
    // Item belongs somewhere in list
    else 
    {
        // Traverse list to find node above insertion point
        // Start with head pointer to top of list
        Car *above = m_head;

        // Keep going; last possible place we can go to
        // is last node; if we go there, the new item
        // belongs at the end; use addCarRear() for that

        while (above->next != nullptr)
        {
            // Code to see if we've found the node
            // just above where our new node should be

            // Prefix decrement to have it take effect immediately
            // This gets us to a node right above index slotNum

            // Have we gone forward that many times yet? 
            // We could convert all this to consider #1 to 
            // be the first slot number of the list
            // Then, we'd check if --slotNum == 1

            // Note that a prefix decrement is NEEDED
            // (for this implementation); otherwise, we
            // compare slotNum's original value of 2 against
            // 0, not what we intended

            if (--slotNum == 0) 
                break;

            // Otherwise, keep traversing
            above = above->next; // Move down a node
        }

        // Allocate and customize new node
        Car *latest = new Car; 
        latest->name = name;

        // Link new node to the one below and the one above

        // Link to node after new node (the old next node)
        latest->next = above->next; 

        // Link above node to latest node
        above->next = latest;
    }
}

This is like the meeting place for Order of the Phoenix in the Harry Potter universe! We squeeze in a new house between the two existing houses.

Deletion

As with insertion, we have to consider if we're deleting a node at the top or one somewhere else in the list.

Our code will handle both cases, but checking for the easier case first means efficiency.

Note that a return statement that returns nothing is usable for a function of return-type void.

void deleteCar(const std::string& doomed)
{
    // First: check if the list is empty
    // There's nothing to delete if so

    if (m_head == nullptr)
        return; 

    // Next, see if the first node 
    // is the one to be deleted

    // Ridiculously long cat screeching as it dies

    if (m_head->name == doomed)
    {
        // Start the deletion process
        // by assigning a temp pointer to the
        // doomed node; don't wanna forget its
        // location

        Car* killMe = m_head; 

        // Have m_head point to the new top node,
        // the one right after the doomed one
        // This way, we don't lose track
        // of the rest of the list

        m_head = killMe->next;

        // This could be m_head->next too
        // as m_head == killMe right now

        // This doesn't work if the doomed
        // node is NOT at the top of the list
        // though; then, we need to link
        // the above node to the node after
        // the doomed one

        // It's like building a bridge over
        // a river that suddenly appears,
        // or creating a patch over a hole
        // in a tire or the road

        // Rain down death and destruction
        // upon the doomed node

        delete killMe; 

        // This will NOT work with delete m_head
        // Then we lose the rest of the list!

next is a common identifier for the next pointer. head and tail are also common.

Do NOT forget to reassign the head pointer BEFORE deleting the top node.

        // We needed the temporary pointer;
        // we'd have to delete m_head otherwise
        // and we'd lose track of the start of
        // the list
    }

Next case: the doomed node is an interior one

    // List traversal to find one just above it

    Car* above = m_head
    while (above->next != nullptr)
    {
        // Found node above the doomed one
        // Is the next node the one we want
        // to delete? 

        if (above->next->name == doomed)
            break;

        above = above->next;
    }

    // Did NOT find the item
    // above points to last node, 
    // whose next is nullptr

Do NOT forget to account for the case that the wanted item does not exist!

    if (above->next == nullptr)
        return;

    // Otherwise, delete, delete!
    // The next one after above is
    // the doomed node

    Car* killMe = above->next;

    // Link above node to node
    // after the doomed one

    above->next = killMe->next;

    // Also possible: above->next->next;

    // Delete the target node
    delete killMe;

    // The last four statements
    // work even for the last node
}

Unencumbered by comments:

void deleteCar(const std::string& doomed)
{
    if (m_head == nullptr)
        return; 

    if (m_head->name == doomed)
    {   
        Car* killMe = m_head; 
        m_head = killMe->next;
        delete killMe; 
    }

    Car* above = m_head
    while (above->next != nullptr)
    {   
        if (above->next->name == doomed)
            break;

        above = above->next;
    }

    if (above->next = nullptr)
        return;

    Car* killMe = above->next;
    above->next = killMe->next;
    delete killMe;
}

Processing

To do stuff with a linked list, we traverse through it and do whatever we'd like to do with it, e.g. print out its contents, compute an average, etc.

Syntax:

void printCarsList() const
{
    // Print every item
    // nullptr lets us know we're
    // at the last one

    Car* temp = m_head;
    while (temp->next != nullptr)
    {
        cout << temp->name << endl;

        // Don't forget to increment!
        temp = temp->next;
    }
}

Destruction

Now for that destructor!

Every node has something dynamically allocated, so delete needs to be rained down upon all of them.

We cannot just do this as part of a normal traversal though; we'd delete the temp each otherwise, and we'd lost the rest of the list.

Instead, we'll have two temporary pointers, just as we did with a deletion operation on a single item: one to point to the doomed node, one to point to the one right after it. We simply shift both along.

~Train()
{
    Car* temp = m_head;
    Car* nextOne;

    while (temp != nullptr)
    {
        nextOne = temp->next;
        delete temp;
        temp = nextOne;
    }
}

On the last run, nextOne will point to nullptr, the node temp points to will be deleted, and temp will be set to nullptr, thus meeting the loop-terminating condition.

Tail Pointers

We have a head pointer that points to the start of a linked list; why not have one that points to the end (tail) of one as well!

This will greatly speed up some of our operations.

Updating our previous code:

class Train
{
    ...

    private:

        Car* m_head;
        Car* m_tail;
};

void addCarRear(const std::string& name)
{
    if (m_head == nullptr)
        addCarFront(name);

addCarFront() will need to be updated to support adjusting the tail poitner as necessary.

    Car *temp = m_head; // Start at top of linked list

    while(temp->next != nullptr)
    {
        temp = temp->next; // Follow next pointer to next node
    }

    Car *latest = new Car;

    latest->name = name;
    latest->next = nullptr;

    // Link old last node to new last node
    m_tail->next = latest; 

    // Update tail pointer to point to new last node
    m_tail = latest; 
}

Doubly-Linked Lists

In a doubly-linked list, every node has next AND previous pointers.

struct Car
{
    Car* p_next;
    Car* p_prev;
}; 

The first node's previous must point to nullptr. The last node's next must point to nullptr.

Head and tail pointers are usable with a doubly-linked list. Moving up and down is now very easy.

Now, the implementations of all of our member functions for the containing class change. With each insertion, deletion, etc., we'll need to update:

  1. The new node's next and previous pointers.
  2. The preceding node's next pointer
  3. The following node's previous pointer

Linked Lists Cheat Sheet

Keep in mind: NEVER access a node until the pointer to it has been validated as a valid one. delete on a nullptr has no effect, but dereferencing it is undefined behavior.

if (ptr != nullptr)
    // Access node data

Advance ptr:

if (ptr != nullptr)
    ptr = ptr->next;

See if ptr points to the last node in a list:

if (ptr != nullptr && ptr->next == nullptr)
    // ptr points to last node

To get the next node's data:

if (ptr != nullptr && ptr->next != nullptr)
    // Access next node's data

To get head node data:

if (m_head != nullptr)
    // Access m_head->blah

To check if a list is empty:

if (m_head == nullptr)
    // List is empty

Note that we have two classes or structs: one for the nodes, one for the linked list. It's easier if a struct is used for the nodes, but these are kept in the private part of the containing class. Also, tail & head pointers can be supplemented with a counter for the number of objects in the linked list.

Linked Lists vs. Arrays

Accessing an item in an array is faster; we can immediately subscript straight to it.

Inserting or deleting an item is much easier with a linked list though.

However, they also take far more effort to code and are more likely to be buggy. Don't use a linked list unless it is necessary.

// Notes: Carey is finally back, but he risks // losing his voice for a whole another week if // he lectures too much today. He has a sub coming // in to take over the latter part of today.

// He had a really bad laryingitis infection // and has to use his phone's voice to communicate

// Kim, a former student of his, is here as sub // Her undergrad was in theater, but she's // getting a master's in CS, and is working // at Google starting this fall

Discussion #1 with Forney: 24 January 2014

Construction order for classes with members of other class types (class composition):

  1. Initializer list
  2. Default-construct all members
  3. Move into constructor body

From Forney's NoisyClass example:

Note that local variables in a loop-body go out of scope after each iteration.

C C

~

D D (D) - local variable destroyed as it's popped off the stack

Check that last node exists:

if (m_tail != nullptr)

Lecture 7: 26 January 2014

Inheritance

We are blasting forward, and fast!

Inheritance is the idea of forming new classes using ones that have already been defined.

ShieldedRobot & Student Analogies

Consider of a newly-sentient being of type Robot.

Side-lecture:

"Do you want to be a passive consumer or someone who creates stuff that makes the world a better place?"

Carey is having that midlife crisis now, haha.

"Otherwise, you'll have an empty life."

Now consider a very similar Robot that also has a shield, so we'd have a ShieldedRobot.

Note that its members are all very similar and we would waste time recreating all that.

The only difference here is the shield. Essentially, a ShieldedRobot is a Robot with some additional methods/data.

Another example: a Person and a Student. A Student is a Person--but with a GPA and an ID.

Never duplicate code. That introduces the possibility of more bugs, and also wastes time.

So we'll define a subclass (ShieldedRobot) and have it inherit (reuse) the functions and data of a superclass. (Robot)

Then, the subclass has the new methods/data, known as specialization.

class ShieldedRobot "is a kind of" Robot
{
    // Has all the Robot stuff
    // PLUS:

    /// Shield stuff
}

Terminology

  1. Define the superclass

  2. Define the subclass, based on the superclass, adding any new stuff as needed

A ShieldedRobot will have all the Robot methods and data too; C++ determines automatically which function to call. We can overload inside the subclass.

Anytime we have a relationship, "A is a type of B", inheritance may be warranted.

In contrast, a Name is part of a Person. So a Name would be a member of Person.

BUT, a Person is derived from Animal.

We can inherit many, many times: A CSNerd is a Person is a Mammal is an Animal.

So each specialization is a "Blah" with "additional".

The superclass is also called a base class. The subclass is also called a derived class.

A class can be a derived class of some other class, but also a base class for other classes. E.g., Mammal is a subclass of Animal but a superclass for Person, Monkey, etc. as well.

Syntax

class ShieldedRobot : public Robot

This says that a ShieldedRobot publicly acknowledges that it is a subclass of a Robot. There is such a thing as private inheritance, but is usually not needed; it basically makes it a member. Just use class composition instead.

This is public inheritance.

What if a subclass doesn't need a superclass' functionality? We'll have to design around that, e.g. render the askOutOnaDate() function of CSNerd an empty one. The Person does that, not the CSNerd.

Virtual Member Functions

A derived class can also override the existing functions from the base class.

Student: "Go Bruins!" NerdyStudent: "I love circuits!"

What if the derived class' function had a different function signature? Then it's not the same function, and this isn't overriding.

But if we are overriding, put the virtual keywords in front of both the base class and the derived class functions (the original and the replacement). It is technically only needed in the base class, but good style has it in front of both.

If a NerdyStudent has its own member variables, then it must have its own constructor, initializing only the stuff

If no override, the subclass will use the superclass' version of the function, e.g. the StudlyStudent will say "Go Bruins" too, but the virtual will be needed in Student if NerdyStudent still redefines the catchPhrase() function. Put the virtual at the highest level.

class DerivedClass : public SuperClass
{
    public:

        virtual bool catchPhrase();

}

What happens if virtual is placed in front of all the base class? It will slow down the program.

If the member functions are defined outside the class, only put virtual within the class definition. Putting it outside of the class decl's is not allowed,

void NerdyStudent::catchPhrase()
{
    cout << "I love circuits!" << endl;
}

If it's inlined inside the subclass, have virtual in the superclass and the subclass.

ONLY use virtual for functions that we want to override/redefine. It will only slow down the program otherwise, though that will NOT produce errors.

Again, virtual is TECHNICALLY ONLY needed in the subclass.

What if we had Robot -> ComedianRobot -> ReallyBadComedianRobot

Where would virtual be needed? Best pratice: in all 3, EVEN IF only ReallyBadComedianRobot redefined the catchPhrase() function.

Can we have inherit from two classes at once? YES!

class ComedianRobot : public Robot, public Comedian

Java can't do it, but C++ can, but it is generally frowned upon.

What if inherited from two classes, but both have redefined talk() functions? Which one is used? Office hours!

Inheritance Function Call Rules

Examples: Student and NerdyStudent.

The NerdyStudent has a virtual cheer() member funiton.

  1. IF you define a function in the base class and redefine in the derived class then the derived version of the function will hide the base clas version of the function.

  2. Any public functions defined in the base class, but not redefined in a derived class can be called normally by all parts of our program.

Note that virtual member functions may call the superclass' member functions too BUT:

  1. IF your code wants to call a function in the base class that's been redefined in the derived class, it must use a class:: prefix. Scope resolution.

Note:

void getExcitedAboutCS()
{

    cheer(); 

    // Call NerdyStudent's cheer()
    // If not there, look for a cheer() in Student
    // If not there, look for it in Person(), etc. 

    Student::cheer();
}

Calls the most derived version of the function that we can. Example: ReallyNerdyStudent would use NerdyStudent's cheer() if it didn't redefine it. If NerdyStudent doesn't have a cheer(), look in Person, etc. This is if we don't specify which class' version of the function to use.

Can go up multiple levels in one step: ClassName::function();

To call from main():

object.ClassName::function();

Again, can go up the hierarchy in one step.

We can have something like:

void talk()
{
    // Modified speech

    Person::talk(); // Do stuff from the base class too
}

This a common pattern: have base class do some work, have the derived class do some work.

E.g.,

Harry Potter story:

7th book was ordered, but delivered to work. He had to wait till Monday rather than Saturday. He runs to the mailroom.

"Do you have a package for me?"

"No."

Same thing Tuesday. And Wednesday. Finally, on Thursday.

"It's for my niece."

Someone else:

"And that proves he's a Nerd, not just a Person." Lol, that was Smallberg!

Boom, toasted Pop Tart time.

"I need a volunteer. Yes, you--if it starts smoking, tell me."

Inheritance and Construction

Again, ShieldedRobot and Robot.

Rules:

Classes are constructed from superclasses to subclasses. This makes sense! (Per Jaclyn) We're building what we need first first, then we build the rest.

They are destructed from subclasses to superclasses.

Imagine a Robot has a Battery member variable and the ShieldedRobot has a ShieldGenerator.

The order of construction:

Build Robot's members (i.e. Battery and the primitives) Build Robot Build ShieldRobot's members (i.e. ShieldGenerator) Build ShieldRobot

BaseClass's members, BaseClass, Subclass' members, subclass

Destruction is reversed, from sub to super:

ShieldedRobot, ShieldGenerator, Robot, Battery (as we learned with class composition).

So it's the same as before, just accounting for the inheritance as well. Same as before for if something is derived from two classes at once too.

In general:

base class members -> base class -> subclass members -> subclass

What about with constructors that require parameters?

Let's have Duck, derived from Animal.

How do we initialize the Animal? With an initializer list in Duck!

Rule: If a superclass requires parameters during construction, then you must add an initializer list to the subclass constructor.

Syntax:

Duck() : Animal(2) // Arbitrarily: all Ducks weigh 2 lbs
{
    ...
}

Before Duck is constructed, Animal will be constructed first. It MUST happen here, in the initializer list. It CANNOT happen anywhere else.

In the first need for initializer list, with class composition, the containing class has the initializer list. Here, the subclass has the initializer list.

Does the order matter in the initializer list? No, but some compilers may give warnings/errors in some warning modes. Also, remember that members are initialized

Can an Animal initialize from a parameter passed to Duck?

Yes!

Animal(int weight, int coolness);
...
Duck(int weight, int coolness) : Animal(weight, coolness)

Paramters to Duck -> Build Animal members -> Build Animal -> Build Duck members -> Build Duck

Oh, look a customized duck that has Animal characteristics!

Remember, the base class is always constructed before the derived class. If Animal were derived from Organism and that needed constructor parameters? Animal would need an initializer list too.

In general: a class intializes its superclass. In memory: an object of a class will have all of its members plus the superclasses.

We can even customize parameters with expressions like weight - GLOBAL_CONSTANT, etc.

In general: a subclass' constructor initializes ONLY the subclass' members, but initializes its superclass, if needed. Thus, going down the inheritance hierarchy, our objects can become more and more detailed.

Again, destruction order within a class: container destructor, member destructors

Could we derive from ? We could, but little point to it.

Before we run constructor/destructor, all the member variables must be present! The 'structors may need them!

Inheritance and Member Visibility

So, we have Robot and ShieldedRobot. Can a ShieldedRobot member function access a Robot's private data?

NO! Because private data members are accessible ONLY to the member functions of the same class. Derived classes may NOT access the base class' private members.

Call base class' public functions instead.

What if ShieldedRobot had its own coordinate member data? No problem. But a main() version call of setX() would call the base class's version of setX(), and do nothing with the subclass' setX(), unless we said object.SubClass::setX()

IF there's no parametrized constructor, you must use public member functions.

Once more: Derived classes may NOT access the private members of their base classes.

All private members of the base class are hidden from the derived class, and may only be accessed via the public interface of the base class.

"Proof": All animals have a spleen (private member). Can we touch our spleens?

Protected Members

If we want our derived class to access private member functions of the base class, use the protected access specifier:

class Robot
{
    ...

    protected:
        void chargeBattery();
}

What about data members under protected? "Extremely bad style"; we're violating encapsulation! Then, we'd have to worry about changing a lot of different stuff.

Now anything derived from the Robot class can access chargeBattery(). E.g., main() cannot call the protected member function; only the subclasses can.

Overriding protected member functions is perfectly possible as well. s

Rules:

Public in base class B:

  • Any function in class B can access it

  • Any function in classes derived from B can access it

  • All classes/functions unrelated to B may access it

Private:

  • Any function in B can access it

  • No functions in classes derived can access it

  • NO classes/functions unrelated to B can access it

Protected:

  • Any function in class B can access it

  • Any function in classes derived from B may access it

  • NO classes/functions unrelated to B can access it

What if one instance of a derived instance is set equal to another? By default, the copy constructor and the assignment operator copies base data, then the derived data. This is a shallow copy.

BUT if the base or derived classes have dynamically allocated member data, then both super and subclasses need a redefined copy constructor and assignment operator.

Look to the PowerPoint. Subclass CC calls the superclass CC first. Subclass [=] calls the superclass [=] first.

Recap

We reuse code in a base class and derive new classes that are specialized with new behaviors and data. E.g., Bat Mobile derived from Car.

Overriding redefines an existing behavior from the base class with a new behavior in the derived class.

From office hours:

What if have classes A & B, and B's foo() calls A's foo, but then we insert a new class in-between A & B which also has foo()?

And in B, we said: A::foo()? Is there a way to make it go up one level automatically? Not as far as we know right here.

But be careful:

virtual void foo()
{
    cout << "..." << endl;
    foo(); // RECURSION!
}

"What's a dummy node? "

In the linked list class, have a member dummyNode of the node struct type. The dummy node's value is irrelevant and unimportant.

Then, have the dummyNode's next point point to the first actual node (the head pointer).

Why do this? With insertion, we'd have to have special code just for inserting at the very top. With a dummy node, we're always inserting between nodes; at the top, it's inserting between the dummy node and the previous top node.

With a dummy node, we use its next pointer as the head pointer; we don't need a head pointer.

How to know when we've hit the end of a circular list? If the node's next pointer points to the head pointer.

ONLY modify result after we've done all rule-following. Double-check all the different cases of the possible parameter combinations.

"What does inline mean?"

An inline function is one whose body is defined in the class declaration. The inline keyword in front of the function would be here:

This is only at the function definition (outside the class declaration), NOT at its declaration, but this IN THE HEADER FILE.

inline _return_type ClassName::function() const

This keyword would mean that the function calls arereplaced by the function's actual code. This is optional as to whether or not it actually happens, and compiler-dependent.

Normally, a program would jump from function to function.

class Foo
{
    public:

        void bar() { ... } // Automatically inline

};

Else, do:

class Foo
{
    public: 

        void bar();
};

inline void Foo::bar()
{
    ...
}

Inline makes compile-time longer but run-time shorter.

Smallberg writes all the specs for homework and projects, except for Projects 3 and 4, which Carey writes.

Lecture 8: 29 January 2014

// Candy for Chinese New Year!

Story: Carey was 5 years into career with Symantec. He was sent up to Saratoga to meet with a customer, someone who had purchased a lot of Symantec software. He there to schmooze the person over dinner. There's two guys; one is a VP, one is a director, from an insurance company. The whole evening he called Bill "Bob". The guy next to him finally went "His name is Bill, not Bob."

Carey: "Bill, Bob, whatever." Ended up apologizing a lot and not getting fired.

Midterm review lecture up. The 5 people who showed up to office hours this morning all got $20.

Polymorphism

This is not specific to C++, but shared across all OOP languages.

Consider a function that takes an object of some class-type. Can it also accept objects of sub-classes derived from that base class?

Yes! But this cannot go the other way around; e.g. cannot give Person to function expecting Student.

If a function accepts a pointer or reference to a class-type, then we can also pass any objects of subclass-types!

Why? Because, a sub-class is IS the super-class; anything a Person can do, a Student can do--and more!

The function will not know that that it's actuallly working on an object of a derived class type. It just treats the object as being of the expected parameter type.

We could determine if the passed argument is of a derived class type. Saved for office hours.

Any time we use a base pointer or reference to access a derived object, this is called polymorphism.

Shape Example

Consider a Shape base class.

It'll have a member function named getArea(), made a virtual member function for overriding in classes Square and Circle.

Square's getArea() calculates differently from Circle's, a consequence of geometry.

A problem? If we write a price calculator for each different shape; that's code duplication!

Instead, do it all in one function:

void printPrice(const Shape& s, const double price)

C++ will figure out which getArea() to call. It figures out the correct virtual function to call, if it's been redefined. It will always use the most derived version. This is all true even though the printPrice() function has no idea that it may be acting on a derived object.

You cannot use any functions that are not in the base class and also virtual. It'll even use the base class version, if it's the right one.

If we pass by vlue, we'll encounter slicing.

In the base class, have all of the common things that all the subclasses have in common.

Is there any way to do different things based on the type of object passed in? Yes.

Inheritance vs. Polymorphism

Inheritance: we derive one or more classes from a base/super class. They all inherit a common set of functions and may redfine their own specializaed functions.

Polymorphism: We may use a base pointer or reference to access any variable of a derived class type. The same function call autamtically casuses different actions to occur, depending on what type of variable is being pointed to/referenced. The referred-to, pointed-to object automatically behaves in an appropriate manner, without writing special code for every single different type.

With polymorphism, we can design and implement systems that are easily extensible.

The Importance of Virtual

The virtual keyword figures out what class is being referenced and calls the right function. The virtual keyword is a necessity.

Inside of the function using the base class type, functions specific to derived classes are invisible to it!

When we forget virtual, C++ no longer looks for the appropriate version of the function; instead, it just uses the version found in the base class type. This is an insidious logic error! In Java, everything is virtual by default.

  1. So, anytime we redefine a function, use virtual in the base class and the derived classes. The functions are virtual from the base class with the virtual keyword onward. Just put virtual in the derived classes to be clear.

  2. ALWAYS use the virtual keyword in destructors in base and and derived classes. IF there is ANY chance that a class may be use as a base class, have virtual in its destructor declaration!

  3. No such thing as a virtual constructor. (That's not needed).

Superclass and subclass Pointers

Can we point a base class pointer to a an object of a derived class type? YES, because a derived object IS of a base class type.

In general, we can point a superclass pointer at a subclassed variable.

Just note that the superclass pointer cannot access any members specific to a subclass.

C++ will dynamically use the right virtual function.

"upcast" means that we point a superclass pointer at a derived class object.

Always make the destructor in the base class virtual. Every derived class' destructor is then automatically virtual.

Whether we use a superclass pointer or subclass pointer depends on what we need to with that object.

Story time: underprivileged kids from inner city visit Symantec.

5 standing around Carey in a circle. He completely repeated all around, completely forgetting a face in just seconds!

Wait, what about the array of different Shapes? Doesn't an array require that the memory be contiguous and the elements be of the same size? Not here, because it's an array of pointers!

QUESTION: Can we point a subclassed pointer to a superclass variable? NO!

While all Squares are a Shape, a Shape is not a square. The relationship is one-way.

We may never point a derived class pointer/reference to a base class variable.

Most-Derived

What is the rule for determining the "right" function? C++ will select the most-derived virtual function, even if that function is called from a non-virtual function.

Virtual Destructors

IF we intend to derive a class from a base class, that base class MUST have a virtual destructor.

DO NOT FORGET!

If we forget a virtual destructor,

Construction order:

  1. Memory allocated

  2. Superclass to subclass. -> Members of class then class.

Note, when we delete an object, C++ sees a death order on a base class type, but everything is virtual, so we call the sub class destructor then the super class destructor.

Destruction order:

  1. Subclass to superclass

If the pointer were to a subclass pointer, both destructors would be called (in the same order: most-derived to most-basic), because the subclass has the superclass bits too! Virtual is not needed so much then; the problem is if we have a superclass pointer to a subclassed pointer, then we need the virtual to call the correct most-derived destructor.

We may not redefine any destructors from a more basic class.

Say we have D derived from B:

B
    m1

D
    m2

Construction: m1, B, m2, D - most basic (members first) to most derived

Destruction: ~D, ~m2, ~B, ~m1 - most-derived to most-basic

Never use assignment operators with polymorphism.

Technically, lacking the virtual with destructors is undefined behavior.

Most of the time, C++ calls the base class' destructor, and never calls the derived class' destructor. It frees the memory, and we lose the pointers to any dynamic members of the derived class. Memory leak!

What if we have non-dynamic memory in the derived class? It's still undefined! Just put virtual in the base class!

This is if we have polymorphism; if the pointer were to the subclass, the subclass destructor would be called correctly, as well as the superclass destructor.

Destructing a derived object always destructs up the hierarchy!

The compiler will know the inheritance hierarchy and spit back a compile-time error if we try to point a subclass pointer at a superclass pointer. Note also that we cannot delete things twice. Don't mix up pointers!

Virtual destructors are only needed with polymorphism, because then C++ may encounter situations where it's unsure what needs to be destructed. THAT SAID, have the destructor be virtual anyway, in case we later modify the code to use polymorphism anyway. ALWAYS define a virtual destructor.

Vtables

When a variable is defined, an invisble "vtable" is pointing to the proper set of functions to use, with an entry for every virtual function in the class. ONLY virtual functions are found in this table.

If the variable is of a subclass type, its vtable will have a pointer to its subclass version of the virtual function. So, every object knows exactly what version of the function to call. As long as the base class has virtual, that function is virtual from then on.

We can have pointers to functions!

Note that the vtables are used at run-time, not compile-time.

Summary

First we figure out what we want to represent in general.

Then we define a base class that contains functions common to all of the derived classes.

Then we write our derived classes, creating specialized versions of each common function.

We can then access derived variables with a base class pointer or reference.

Finally, we must always have a virtual destructor in our base class, whether it needs it or not. (Using inheritance, create a virtual destructor!)

OMG: How many people have asked the exact same question: "Do the derived classes need virtual in front their function signatures?"

Does it make sense to have Shape objects? No, so its functions are really dummy functions.

Pure Virtual Functions

We must define functions that are common to all derived classes in our base class to use polymorphism. The lame thing is the dummy functions in the derived classes. (But without them, we wouldn't be able to use polymorphism).

// LOL, Carey and a student blowing a spider back and forth at each other.

Since they are never used, their implementations could be anthing. But it'd be even better if we could remove them altogether.

We define abstract functions

Syntax:

virtual _returnType _identifer() = 0; 

These are called pure virtual functions.

Rules.

  1. Make a base class function pure virtual if we realize that the base-class version does not do anything useful.

Pure virtual functions can be in subclasses too!

If a base class has a pure virtual function, then its derived classes must define their own version of it.

If a class has at least one pure virtual function, than it is called an abstract base class (ABC). Not "American Born Chinese", haha.

Abstract Base Classes

Rules:

  1. Must either provide code for all pure virtual functions
  2. Or the derived class becomes an abstract base class itself!

Some definitions can be omitted, then the derived class effectively has that pure virtual function too.

Look up the inheritance hierarchy: does it have defined versions from previous superclasses, and then fills in the rest? If so, that function is considered defined.

If a class is an ABC, we CANNOT define any instances of it but we can define pointers to them.

But, if there is at least one function that is an inherited pure virtual function, and we don't redefine them, then the subclass becomes an ABC itself, and we cannot define any instances of it.

Note: we do not repeat the PVF in the subclass; it just inherits it; it "virtually" has the pure virtual function.

Why would we use PVFs and ABCs? IT forces the programmer to implement certain functions to prevent common mistakes, like forgetting to implement the specialized virtual functions of subclasses.

If we forget (and the forgotten function is not made pure virtual), then we call the base class version by mistake. If we did pure virtual, then we'd get an area, look at it and go ("Wait, that's not an ABC. Wait, there's supposed to be a virtual function specialiazed to that class derived from Shape!" Oh, right, I did not implement...")

Pure virtual functions force the programmer to implement the correct versions in the derived class.

Still, we can use ABC pointers and references; this lets us do polymorphism with that base class (and therefore pass in instances of derived classes). We never use the ABC member functions; instead, we call the redefined virtual functions of the derived types.

Example:

void printPrice(Shape& s)
{
    ...
}

Note that we cannot pass-by-value with an ABC. That would require creating a Shape, which is illegal with an ABC.

Also legal,

void printPrice(

It's almost like, we're able to see through a paper cutout; it just masks what we see. We see the actual thing we need through the paper.

In summary, pure virtual functions let us:

  1. Avoid writing dummy logic

  2. Force the programmer to implement derived class' functions.

Oh, and remember, virtual destructor in the base class, always.

As before, we can do an ABC pointer or reference to an instance of a derived class.

But we would not be able to point an ABC pointer to an ABC instance; because we cannot create any instances of an ABC! This also means no arrays of an ABC; but we can do an array of Animal pointers.

But we could do ABC pointers to ABC pointers.

There may be constructors for ABCs, but that doesn't mean that they will not ABCs (we cannot have virtual constructors).

What if we had

Animal - ABC Insect - ABC (derived from Animal) Fly - regular Ant - regular

Fly f;
Ant a;

Animal* p;

p = &a; // Point to 

p = &f;

Can this be done? Yes. Animal is a superclass to Fly and Ant. But we cannot point subclass pointers to superclasses; not all Animals are Ants.

We could also do:

Insect* i; 

i = &a; 
i = &f; 

Ant and Fly are derived from Insect.

Subclass destructor will run, then superclass destructor will run, automatically.

Challenge: Diary Class

// Assume that this class will be used in inheritance // and that all these functions may be redefined.

#include <string> 

class Diary
{
    public: 
        Diary(const std::string& title) // PBCR
        {
            m_title = title;
        }
        virtual ~Diary()
        {
            // EMPTY
        }
        virtual std::string getTitle() const // Should be const!
        {
            return m_title;
        }
        virtual void writeEntry(const std::string& entry) // Should be PBCR
        {
            m_entries += entry;
        }
        virtual std::string read() const // Should be const!
        {
            return m_entries; // Returns a COPY of m_entries

            // IF we did not want m_entires to be modified
            // then return by constant reference! 
        }

    private: 

        std::string m_title;
        std::string m_entries; 
};

Arvin got it;

"Do you want the Pop Tart, or what's in the bag?"

In that case, "Leggo my Eggo!" And he even gets syrup!

If the base class function is const, the redefined function must be const too!

Challenge:

Secret Diary Challenge

class SecretDiary : public Diary
    : Diary("TOP-SECRET") // A SecretDiary IS a Diary! 
    // We need to initialize the superclass!
{
    public:

        SecretDiary()
        {
            // EMPTY
        }

        virtual ~SecretDiary()
        {
            // EMPTY
        }

        // Entries are part of the base class
        virtual void writeEntry(const string& entry)
        {
            // DOESN'T WORK!
            // This would modify a copy of m_entries
            Diary::read() += encode(entry); 

            // This WOULD work if Diary's read()
            // returned a REFERENCE to m_entries

            // CANNOT base class private data
            // MUST use the base class public member functions!
            Diary::writeEntry(encode(entry));
        }

        virtual string read() const
        {
            return decode(Diary::read());
        }

    private:
        // DO NOT redefine data! 
        // DO NOT use protected data! 
        // Use PRIVATE data!
};

Scrambled Diary Challenge

See challenge part 3 in the PowerPoint.

If read() is not virtual in Diary, then we use Diary's version of read(), rather than SecretDiary's read(), which uses decode()!

This is why we would get scrambled text!

Lecture 9: Stacks & Queues

These are retroactive notes; this lecture was actually supposed to follow linked lists and precede inheritance, but Carey got sick, and so the whole schedule got thrown off.

This means even more studying now. I did not expect college to be this hard or to involve this much studying. Naïvety, I suppose.

Lectures 10 & 11: 3 February 2014 & 5 February 2014

On the midterms, David's median was 27; ours was 29! Lol, he totally trolled us with an :-( first. Smallberg has a bunch of graduating EE seniors, apparently.

WE MUST PRACTICE SOLVING RECURSION PROBLEMS!

It's time for what Joel Spolosky called "the big guns" of coding interview questions:

Recursion

Carey describes it as "one of the most difficult topics in computer science", but it does let us do all sorts of stuff. It's apparently his favorite lecture of the quarter!

Stacks & queues let us solve mazes and write calculators that can process whole natural expressions. Linked lists underpinned stacks and queues.

Inheritance and polymorphism let us avoid code duplication and easily extend our existing code to meet new needs.

And now, recursion will let us do stuff like play chess or checkers, solve Sudoku puzzles (in ~15 lines), and crack codes or ciphers. It is a big, difficult gun, but wieled well, we'll finally be able to do all the cool stuff that pop culture promised us!

It'll also let us do mathy stuff like factorials!

Thinking Paradigm Behind Recursion

Previously, we did problem-solving in a function with breaking stuff down into smaller, constituent problems, solving each of them with sub-functions, then gathering the solutions into one for the overarching problem.

With recursion, we'll solve the sub-problems by calling the larger function on itself!

"Lazy Person's Sort"

We have a pile of index cards with numbers on them. We want to sort the cards. Solution: hand off half to one person, half to another person, have them sort their respective halves, the recombine the sorted halves.

Problem: too many cards.

Solution: each of the slaves/willing assistants calls on two other people each themselves. It's a sort of pyramid:

            A
        B       B
      C   C   C   C
     D D D D D D D D
           ...

Problem: if there is only card left, it cannot be split up.

Solution: if handed only card, give it right back; it's already "sorted".

This is known as merge sort.

We just saw the power of calling a function on itself repeatedly to solve sub-problems that eventually solves the whole problem.

Each broken-up sub-part may not be of the same size. Just like how a Riemann Sum may not have a uniform partition size.

So how do we get to the actual merging part if we keep calling ourself?

Basically, we go down and down till we hit the base case, then we return back up, merging and merging little stuff. Merge sort is apparently one of the most efficient algorithms known to humanity.

Our job with recursion: how can our function use itself (on increasingly smaller subsets) to get the complete problem solved? It must be able to work on the full set or a subset. We must have faith like Indiana Jones crossing that bridge!

The Two Rules of Recursion

ONE: Every recursive function must have a stopping condition.

The stopping condition (base case): The recursive function is able to solve the simplest, most basic instance of its problem without using recursion. Instead, it runs once, then stops calling itself. (Example: base case for merge sort is a single element).

Example:

void eatTootsieRollPop(int layers)
{

// This is the stopping condition // In the base case of zero or less, // we run once (more) and end!

    if (layers <= 0)
    {
        cout << "We've hit the center!" << endl;
        return; // Don't forget to end!
    }

    cout << "Licking!" << endl;

    eatTootsieRollPop(layers - 1); // Recursion! Calling itself!
}

Without a stopping condition, a recursive function would run ad infinitum, something we definitely do not want to have happen. It'd be infinite Inception!

What happens if a recursive function actually does go on forever? Well, the call stack would overflow and we'll crash.

TWO: Every recursive function must have a "simplifying step"

Every time that the recursive function calls itself, a smaller sub-problem must be passed into, so that we eventually reach the stopping condition and terminate.

Without this simplifying condition, we'll never reach that stopping condition.

From previous example: (layers - 1)

// A copied value that is equal to layers - 1 // Layers is not actually modified; layers-- would modify it

// PBR vs. PBR is case-dependent; modifying the counter // would not always work [also, that counter would have // to come from outside the function; we'd be recreating // it every time otherwise]

Without that, we would never reach the stopping condition of if (layers <= 0)

Most recursive functions meet this second rule by splitting their inputs into two with each call, or by operating on an input one smaller in size than the last.

Is it better to divide many times? It depends on the problem. We'll be able to mathematically analyze this later on.

TWO.5: Recursive functions must only use local variables & parameters

Using globals, statics or class member variables would be an atrocious idea. This is not always wrong, but almost all of the time, it is a bad idea.

NEVER use a loop within a recursive function unless absolutely necessary.

The parameter-passing method is irrelevant (value, reference, pointer)

Tracing Through Recursion

Tracing through a complex recursive function can be confusing. To alleviate the headaches, we can pretend that each recursive call is a call to a different function that just happens to have the same name.

This helps a lot with tracing the function returns.

On paper, this can be done by writing down all the variables and parameters, and then repeatedly folding and unfolding the paper to avoid confusion over the returned values.

Distinguish between the different calls of the same recursive function

"How do you lick something with no layers? That could be misconstrued as something inappropriate."

Does C++ actually copy the function? No, this is just for visualization.

The debugger would show us going into the call again and again; the variables watcher would show us the current state with the current call; Visual Studio will let us go up and down the stack to see the different call states. I'll have to see if Xcode lets us do the same.

Wielding Recursion

Here is how to write a recursive function:

  1. Write the function signature

  2. Show how to use the function

  3. Add the base case code

  4. Add the recursive function call

  5. Write the function's completion logic

  6. Validate the function

Example: we want to calculate a factorial.

Step 1: Write the function header

  • What arguments need to be passed to the function and how?

  • What should the function return?

  • If this is a member function, should the function be const?

Our example will be int factorial(int number)

Step 2: Show how to use our function

  • Who calls this function, and from where?

  • How does it handle an input of size N vs size N - 1?

Example calls:

int threeItemMenuPossibilites = factorial(3);
int nowTwo = factorial(2);

In general:

int var1 = factorial(n);    // Gives us n!
int var2 = facotiral(n - 1) // Gives us (n - 1)!

Step 3: Add the base case code

  • Identify the simplest possible inputs

  • Add checks for these base cases (there may be multiple!)

  • Solve the problem without using recursion

  • Always consider all possible base cases!

In our example, 0! would be the base case. 0!, by the way, is equal to 1.

int factorial(int number)
{
    if (number == 0)
        return 1; 

    ...
}

Step 4: Simplify the input & call ourselves

  • Split or modify the input as needed

  • Have the function call itself to solve the larger part

We currently have:

int factorial(int number)
{
    if (number == 0)
        return 1; 

    int N = number; 
    int minusOne = ... // Need (N - 1)!
}

Oh, right--recursion!

int factorial(int number)
{
    if (number == 0)
        return 1; 

    int N = number; 
    int minusOne = factorial(number - 1);
}

This is our simplifying code, which here gets us one closer to the base case with each recursive call.

Step 5: Write the completion logic

  • Get the result from the recursive call

  • Further refine/process it, as needed

  • Return the finished product

int factorial(int number) {

if (number == 0)
    return 1; 

int one = number; 
int minusOne = factorial(number - 1);

return (one * minusOne);

}

Here, we recursively go down the number line from the input, then hit bottom, and bounce back up on the multiplicative wave!

It goes: 5 to 4 to 3 to 2 to 1 to 0.

Then it goes 1 * 2 * 3 * 4 * 5!

Step 6: Validate our new function

  • Validate the neonate function, always

  • Try the simplest possible inputs first

  • Try increasingly complex/large inputs

  • After one recursive call check, we're usually good

Alternative formulation of the steps (Carey really does update the slides every year):

Step 1: Write the function header

  • What will the function return

  • What do we need to pass to the function?

For the factorial example, we pass in an unsigned integer, and we return an unsigned integer.

Step 2: Define the magic function

  • Assume that David Smallberg created a magic function that always works that does what we want to do

  • It takes the same parameters, and return the same result-type

  • Restriction: It cannot work on problems of size N. It CAN work on problems of size less than N

  • Show how to use this magic function to solve problems of size elss than N

Imagine we already have a magic function. Show how we could use it.

Define a magic function, that has teh same paraemters but CANNOT wrok on a value of size N, so we can't do N! but we can do (N - 1)!

Step 3: Add the base case code

Determine the base case(s) and solve it (them) without recursion.

  • What is the simplest sub-problem(s) the function can solve without recursion?

  • What inputs allow us to immediately return some result without having the function call itself?

  • There may be multiple base cases

Here, 0! = 1.

Step 4: Solve the problem with the magic function

We can't use the magic function to do all the work, so break the problem into smaller parts:

N! = N * (N - 1)!

A factorial can be redefined as the top number times the factorial of the top - 1 number, e.g. 5! = 5 * 4! or 5! = 5 * (5 - 1)!

We already have N; no need for the magic function.

So we use David Smallberg's magic funcion on the (N - 1)! part.

Then we combine the results and return it.

int part1 = N; 
int part2 = magicFactorial(N - 1);

return part1 * part2; 

Step 5: Remove the magic

magicFactorial() { factorial() }

We just call ourselves! The sub-problem(s) is/are solved by our own function. We trust that our function will work on problems of sizes smaller than N.

The problem: If our function calls itself, what stops it from calling itself forever?

Answer: the base case code ensures that eventually we stop calling ourselves.

Step 6: Validate the recursive function

ALWAYS try our new function on the simplest possible input, then verify it with increasingly larger/more complex inputs. VERIFY that our implementation works. Typically, just one larger is enough to verify the function.

This lets us catch our mistakes!

Note that every recusrive call will create new copies of the local parameters and variables. We use the call stack for all this. Runaway recursive functions will cause a stack overflow.

Note also how the recursive calls match up with the factorial process:

3! = 3 * 2 * 1

Static Variables

void foo()
{
    static int a; // Static primitive types are initialized to 0

    cout << a;

    a = a = 1;
}

When we exit the function, the variable's lifetime is till the end of the program; but its scope is limited to foo().

It has the lifetime, but not the scope of a global.

Try to avoid statics. They are one way to check how often a a function is called, but that's just as easily accomplished with a counter variable (of a longer lifetime and large scope) passed into the function (by reference or pointer).

Note also that a would not be re-initialized to 0 with each call to foo().

A static class instance would have its default constructor called. Making recursion problems easier is possible with globals or statics but they should never be necessary. Do it the real way; use the full power of recursion!

Recursion on Arrays

// Carey is in a dress shirt and pants; // Symantec has a Top 150 people in the company // meeting in San Francisco today, apparently. // Apple does the same thing, but with top ~100

Now, we'll use recursion to get the sum of all items in an array.

  1. Function header

We need the array and its size.

Arrays may never be passed by reference

sumArray(int arr*, int n);

OR:

sumArray(int arr[], int n); 

We return the sum of all the values.

int sumArray(int arr*, int n);
  1. We have a magic function

Note that Carey is just making this up as a crutch to help us learn recursion.

Assume that the magic function does not use recursion.

It looks like this:

int magicSumArray(int arr*, int n);

Where n is < N. Smallberg put a booby trap in it!

To sum up smaller arrays:

magicSumArray(arr, n - 1); 

To get last n - 1 elements: (arr + 1, n - 1)

This gets us the element at index 1, the second element of an array that starts its indexing at 0. Remember that arr + 1 gets us to the next element, moving by the type size, not the number of bytes.

To get the first half: (arr, n/2)

To get the last half: (arr + n/2, n - n/2)

--> Advance to middle half, then iterate over the remaining items, which means there are n - n/2 items remaining (this also accounts for if there are an odd number of elements in the array).

  1. Determine base cases

What's the base case here? An empty array, which has a sum of 0.

If there is only one element, then the sum is just that the one element, the arr[0].

It is better to have have extra base cases for safety, then to not have them. We can always remove redundancies later on.

  1. Use magic

We need to break down our problem into smaller sub-problems.

We can go

  • Front-to-back

We process the first N -1 elements, ignoring the last element. Then we get the last element separately, and add up the two quantities.

int front = magicSumArray(arr, n - 1);
int back = arr[n - 1];

return front + back;

Or

return front + a[n -1]
  • Back-to-front

We process the last n - 1 elements and ignore the first element. Then later add the first element.

int rear = magicSumArray(arr + 1, n - 1);
return a[0] + rear; 
  • Divide and conquer

We process the first half, the second half, and then combine them:

int first = magicSumArray(arr, n/2);
int second = magicSumArray(arr + n/2, n - n/2);

return first + second; 

Now which one is faster for processing arrays? Here, all three need to visit all N elements, (we need to sum them up), so there is no advantage to any of them, at least here.

  1. Remove the magic

magicSumArray() really just calls our sumArray().

We're calling ourselves.

David: "Surprise!"

  1. Verify our function

Here, if we do front-to-back or back-to-front, the second check for n == 1 would not be needed.

If we do divide-and-conquer, the n == 1 check would be needed.

Challenge

void printArray(int arr*, int size)
{
    if (size == 0)
        return;

    // IF using divide-and-conquer
    if (size == 1)
        cout << arr[0] << endl;

        // If using back-to-front

    // We print the first element
    cout << arr[0] << endl;

    // We print the remaining elements
    printArray(arr + 1, size - 1);
}

John Thompson, new Chairman of the Board at Microsoft (named yesterday), used to be a CEO at Symantec. Carey knows him...

Update to print from bottom to top

void printArray(int arr*, int size)
{

    if (size == 0)
        return;

    // IF using divide-and-conquer
    if (size == 1)
        cout << arr[size] << endl;

        // If using back-to-front

    // We print the remaining elements
    printArray(arr + 1, size - 1);

    // We print the first element
    cout << arr[0] << endl;
}

Yes, this does print ou t in reverse, this is because we are recursive here!

It hits an empty, then propagates backwards.

Each call of the company of the recursive function sees a different version of the array.

Note that the last call passes in a location in memory past the end of the array, but our base case code accounts for the zero case, so we just return.

Recursion on a Linked List

Typically we just go down a linked list.

We'll pass a pointer to a node (could be a dummy node, or follow the head pointer to the first node).

We don't need a size value; we can just determine based on the next pointer.

If it's a circular linked list, we need a special case check for if we've hit first node again.

On an exam, never assume that an array or a linked list is not empty.

Function that finds the biggest item in a linked list.

struct Node
{
    int m_val; 
    Node* m_next
};

int biggest(Node* cur); 

Note that it's hard to know where the middle of the link list, unless we maintained a pointer to it.

We need to act on a subset of the list.

So we can use the array strategies, acting on the last N - 1 items, or first N - 1 items, then checking against the value of the first node or the last node.

// It's probably gonna be the head pointer, 
// but we could find the biggest part of just
// part of the list 
int biggest(Node* cur)
{
    // [ERROR]: Empty linked list!
    if (cur == nullptr)
    {
        return -1;
    }

    // Only one node in linked list
    if (cur->next == nullptr)
    {
        return cur->m_val;
    }

    // The value of the first node
    int candidate1 = cur->m_val;

    // Otherwise, find biggest in the
    // rest of the list
    int candidate2 = biggest(cur->next);

    int winner = (candidate1 >= candidate2) ? candidate1 : candidate2;

    return winner;

    // OR: return (candidate1 >= candidate2) ? candidate1 : candidate2;
}

When we get to the bottom, we compare one item to the n - 1 item, then we compare that winnner against the next value, and we take that winner and compare against the next value, and eventually we'll have the biggest value in the whole list.

This is like a rock-paper-scissors tournament, modified so that it runs linearly (rather than concurrently/in parallel), and propagates downward to two people (we're creating pairs) and then we compete back up the pairs (we're assuming ability is absolute, i.e. no luck, and re-running the tournament would deterministically give the same result, as here when we compare numbers).

Carey did a "Biggest gets head, lucky biggest"; he apparently wanted to do this during the linked list lecture, but Kim was delivering that one, so he decided that it would have been inappropriate, haha.

We need to do the challenges on our own.

On the earliest position challenge, consider passing one of the parameters by reference or pointer.

Be Careful with Recursion

Recursion is a memory hog. Why? Because we're constantly pushing the function's variables onto the stack for each call.

There is only copy of the function in the machine code, but we do have multiple copies of its variables.

So, if possible, do a problem without recursion, unless we're just doing it for practice.

If we do N - 1 for a sub-problem, then we'll end up with N copies of all the variables and we'll eventually cause a stack overflow.

If we can do stuff with a for-loop, do not do it with recursion. Recursion is used on the difficult stuff. Don't use it unless our recursive calls don't go too deep.

Binary Search

search(...)
{
    if (top > bottom)
    {
        // Our two ends have crossed; nothing found
        return -1; 
    }

    IF no words
        DONE

    ELSE IF middleWord == findWord
        RETURN - DONE

    ELSE
    {
        middleWorld = (top + bot) / 2
        IF (findWord == middleWord) // FOUND it!
            RETURN - DONE
        ELSE IF (findWord < middleWord)
            search(first half [exclude the non-matching middle])

        ELSE IF (findWord > middleWord)
            search(second half [exclude the non-matching middle])
    }
}

To exclude the non-matching middle, just shift the index or pointer, up/down, as needed.

Recursion Binary Search

Simplify a recursive function for user use by creating helper functions. Determine what we need from the parameters passed to the simple interface, a cover function. The helper function will actually do the dirty work. The cover might just call the helper, passing the processed parameters.

Some problems will need a lot of different parameters. To make things easier, just abstract away!

Solving Mazes with Recursion

Solving a maze with recursion is very similar to a stack-based solver, as it too uses a stack!

It will be a depth-first search that uses backtracking.

// He first taught this class at 28 // He had hair then, and could blend in the first row // Stands up, "I'm the professor!" Haha

How have we simplified the problem with this recusive call? We stuck bread-crumbs everywhere! We'll never repeatedly check a location; we're eliminating possibilties in the maze as we explore it. We'll be looking a maze with a N - 1 open slots each time; we'll either have a solution or no solution!

Lecture 12: 10 February 2014

// Quick hint on #4 of Homework 3

Say we have:

5 10 2 9 0 7 16

We're gonna split using the first number.

We end up with:

2 0 1 5 10 9 7 6

Now, we want smallest to largest (opposite of homework).

We want stuff to the left and to the right to go in ascending order. Here, 5 is already in the right spot, thanks to split()!

So, we want to call order() on the subset (on either side of the 5, using split(), and we'll order() with split().

Review: Recursion


Klinger story: small graduate computer vision class.

Professor always brought in food like oranges, and hard-boiled eggs. The professor asked a question, and some guy gave a response: "The purple pyramid!" (he normally said nonsense).

The professor: "That's absolutely right!"

Leonardo made a funny face, and he vibrated a table with a tray of pastries. The tray fell over and sent pastries flying.

"The pastries are flying!" and he ran out of the class.

He still got an A- in the class.


In the maze example, we had an implicit base case, where we hit the end of the function after propagating back up, and simply hit the end of the function without doing anything.

That allowed for backtracking to the last valid good exploratory position. Cool animation in the PowerPoint!

Notice that it when it hits the solution, it will keep on looking and explore every possibility in the array, despite having the solution.

Look up the Minimax algorithm (minimize/maximize) is a recursive algorithm for creating an intelligent computer AI opponent. It picks the best move for the computer by silently trying each legal move and seeing how the game woud have turned out. It simulates an ideal human player during this simulation. It examines a big tree of possibilities against possibilties.

We can tell the algorithm how far ahead we want it to check (e.g. 3 levels deep).

At the base case level, do a static evaluation, and see who's winning, black or white, e.g. with a number, +/-.

Otherwise, repeatedly (every move computer can make)< then it temporarily changes the board and checks how a human would respond (What's the worst a human could?) , then it returns the best move possibility for the computer.

A findBestHumanMove() is very similar to findBestCompMove(); they co-recur. This is co-recursion.

The computer will remember all the resulting scores from the possible combination of moves.

So, the difficulty of the computer opponent will be determined (primarily) by how far ahead it looks and analyzes.

The best chess programs don't go deep uniformly; that takes too much time and too much computational power. Instead, they throw away branches that make no sense (e.g. it's obvious this is a good or bad path). The algo will iteratively go deeper or shallower as needed. Then, they'll

Tic-Tac-Toe can be solved perfectly (we can build an AI that will always win or tie). There's only 9 squares. Chess is too complex to evaluate everything.

Generic Programming

The war on code and functionality duplication. We keep learning more ways to make our programs highly extensible and adaptive to our needs.

Generic programming means we'll be able to build stuff (especially algorithms and data structures) that can work on many kinds of data, e.g. a linked list that can serve as a container for Students as well as ints, etc. Similarly, we want a sort() that can sort many different things.

This is code reuse.

Custom Comparison Operators

First, know that we can overload operators like ==, <, >, <=, and >= just like we did the assignment operator ==.

To overload within a class:

class SomeClass 
{
    public:

        ...
        bool operator<(const SomeClass& other)
        {
            if ( // Compare data members, etc. ) 
                return true;
            else
                return false;
        }

    private:

        ...
};

Would this work with derived classes? This would compare only the Dog part, and not the GoldenRetriever() part.

As before, this can happen outside of the class too:

// Note that outside the class, we'll need two operands // Inside the class, the calling object is treated as the first // operand; note also that operator overloading requires that // at least one of the operands be of a class type (though // we can also have primitives passed in parameters, e.g. compare // our custom Number class to an int)

// ORDER MATTERS; we have to do Dog vs. Cat, and a separate // Cat vs. Dog

// We can also compare class types against other class types; // This would be

// In general, PBCR

bool operator<(const SomeClass& other, const SomeClass& another)
{
    ...
}

// NOTE: If the operator is overloaded outside of the class, // its implementation will ONLY be able to use the class' public // members

// ALSO: We cannot have more operands than the built-in // operators expect.

It may be helpful to recall that fido <= spot is equivalent to fido.operator=(spot)

There is NO default comparison operator for programmer-defined class types.

This is static binding, meaning we know at compile-time what sort of variable we have. Dynamic binding means we have to figure out at run-time what sort of variable we're actually dealing with, as with polymorphism.

Generic programming is powerful! With it, we can write programs far more quickly; it's a great force multiplier. This is a common paradigm among modern languages.

Here, we get to avoid writing special code for comparing different objects (which also avoids accidental comparison using different standards, or comparing using different data members).

Finally: if the objects passed into the overloaded operator are const, then any member functions we call better be const too.

Prime example: cout's << is an overloaded operator.

Templates

Previously, we sort of did generic functions with typedef. It sucks though, because we're constantly having to change the typedef declaration whenever we want to change the data type we use.

  1. Declare the template type
  2. Use that type throughout the generic function

To have a swap() function that works with any data type, we can do:

template<typename Blah>
void swap(Blah a, Blah b)
{
    // This assumes that the assignment operator is correctly defined
    Blah temp;
    temp = a; 
    a = b;
    b = temp;
}

Note that will only apply to the immediately following function or class.

We can also write template<class Blah>

With this current definition, we expect swap()'s arguments to be of the same type. Now, it can be any type, but the arguments must be of the same type.

We typename or class to be succeeded by a generic identifier.

This swap() would work on two arguments of the same subclass; because they're just items of the same type! We could use a superclass' assignment operator if we wanted to.

QUESTION:

What if we had template<class Blah> and created a class Blah? Would that be allowed? I'll try and find out!

Template Implementation Details

The entire templated function is put in a header file. It CANNOT be split between a header and source file, e.g. what we did before with a prototype and definition.

At compile-time, the compiler will generate a new version (machine code) of the function for each new variable type. The compiled executable will grow in size (little different from if we had written many different function versions for, but the source file would be smaller).

Templates are time-saving and bug-reducing and source-simplifying!

NOTE: We must use the template data type for at least one parameter or we'll have an error (i.e. we cannot use it for just a return-type).

When we use a templated function that expects two or more parameters of the same name, e.g. max(Blah x, Blah y), then we must pass in two arguments to max() that are of the same type, e.g. two Cats, two Dogs, but NOT an int and a float.

QUESTION: Could we define a templated comparison operator? Would that be a good idea? It seems redundant though.

We can override a templated function with a specialized function specific to a class type. We'll use the most specialized version (e.g. one that compares additional data members of a subclass).

Note that any operators we use inside of the generic functions must be properly overloaded. To speed up that implementation work, we could use operators within operator overloads, e.g. using == and < inside of the overload for <=

Multi-Type Templates

We can have

template<typename Type1, typename Type2>
void functionName(Type 1 first, Type 2 second)
{
    ...
}

Generic Classes

We can have generic classes too, ones that can hold any sort of data.

AGAIN: Everything goes into a header file

template<typename Item>
class SomeClass
{

    public:
        void setVal(Item a)
        {
            m_a = a;
        }

        // Don't redefine the ints here;
        // we don't need to!
        void print()
        {
            for (int i = 0; i < 10; i++)
                cout << m_a;
        }

    private:

        Item m_a;
};

Note that we would have to redefine how cout works for class types.

NOTE: In a class, we do NOT need to use the template data type. That would be lame to not use it though. Double-check this.

Note that we can only overload the primitive operators; we cannot create new operators.

To create an instance of a generic class:

SomeClass<typeWeWantToUse> instanceOfGenericClass;

ClassName<int> object1;

To define member functions externally, note that we use:

template<class Blah>
class Foo
{
    ...
    void bar(Blah a);
    ...
};


template<class Blah>
void Foo<Blah>::bar(Blah a)
{
    ...
}

goes between ClassName and ::

Check syntax for multi-type templates?

void Foo<Blah, Item>::function(Blah a, Item b)
{
    ...
}

Again, this is all in the header file; we're just writing the bodies outside of the class definition. If it's inside the class definition, we don't need to write inline (but if we didn't intend to inline, define them outside of the class.

Inline Methods

Inline methods are a request to the compiler (compilers do not have to honor it) to directly embed a function's call with its body logic (replace the call and jump with the machine code definition of the function).

Functions declared and defined inside of a class are implicitly inline. To do so outside of the class:

inline void Foo<Blah>::functionName(Blah b) const
{
    ...
}

Again, if this is a templated function, this is ALL in the header file (we're just defining the function outside of the class definition, but it's ALL in the header file).

This is some really ugly syntax...

This is faster. Why would we avoid inlining everything? We'd be copying that code and duplicating all over the place, creating a really large binary, and we'll hit diminishing returns as we use up memory.

BUT: This heavily slows down compilation.

Inlining is a trade-off between compilation time and execution time.

// Carey struggling with his laser-pointer/clicker // Its battery died. His personal idiosyncrasy is to have // a working laser. "Class is over!" So funny, haha.

"I have never looked at the real Stack class, because I have a life."

Hilarious, haha.

Templated classes allow us to build powerful linked lists and other data structures. Now, our data structures can hold any sort of data. (Make sure our templated classes work perfectly; then, we'll never have to rewrite data structure classes)

STL

The STL is a set of pre-written (and tested!) classes, all implemented with templates.

Boom! Time-saver

Vector

A is a dynamically-size array. It does NOT have a fixed size. They grow/shrink auto-magically/

#include <vector>

using std::vector;

    // To create an empty vector (0 elements)
    vector<string> myFirstVector;

    // OR:
    std::vector<std::string> myFirstVector;

This requires that the has a default constructor! No different from when we created arrays of stuff. If a class required parameter(s) to its constructor, then we might have a vector of pointers to instances of that class instead.

All of a vector's initial elements are automatically initialized. (using the default constructor)>

All of its items are contiguous in memory. A vector basically dynamically allocates an array. When we hit the end, the class allocates a new, larger dynamic array, copies over the old stuff, and deletes the old one. This is a big reason why vectors are slower.

Note that if the vector doubles in size when it fills up, then the capacity will quickly (out)grow the need.
The vector-growth would be implementation-dependent. Who knows what the STL does, haha.

Note that an array of a fixed size will always be faster than a vector. This trade

"I'm a little edgy right now, because I don't have my laser."

Stack and queue are container classes

If we pass a second parameter:

vector<int> vals(3, 4);

This will create a vector of 3 ints with initial value 4.

We could also do:

vector<Dog> myPuppyFamily(3, "Fido");

What sort of constructors are needed here? Is a default constructor still needed?

Vector member functions:

// To add a new item to the end of the vector:

push_back()

There is NO push_front() function for vectors.

// To read an existing item, use brackets, 
// just like with arrays
// '[]' is now an overloaded operator!

vals[number]

Bracks can only access existing items; if we go out-of-bounds, we'll get memory access errors (just as with arrays; because again, the underlying implementation is a dynamically-allocated array).

// To read/write the front or back elements
// of the vector:

front()
back()

// To remove the back item of the vector:
pop_back()

This means that if order matters for us, we need to be careful in how we push items to the vector such that if we need to delete something, we have that item at the end (we could write an exchange function that swaps two values inside of the vector).

QUESTION: What parameters would that exchange function take?

// To get the size of the vector (NOT the size of the
// underlying array)
size()

Keep in mind that ONLY vectors have a .size(), not arrays

// To know if the vector is empty
empty()

Summary of

    // To add a new item to the end of the vector:

push_back()

    // To read an existing item, use brackets, 
    // just like with arrays
    // '[]' is now an overloaded operator!

vals[number]

    // To read/write the front or back elements
    // of the vector:

front()
back()

    // To remove the back item of the vector:

pop_back()

    // To get the size of the vector (NOT the size of the
    // underlying array)

size()

    // To know if the vector is empty

empty()

ANSWER: Why must a templated class be completely in a header file?

Because C++ will create specialized versions for every time that the templated class is needed. If we have stuff split up, that would have prevented the compiler from knowing where the needed templated class is.

Summary of

// These notes were taken 12 February 2014, to continue // from the previous lecture on generic programming // and STL

STL's is a linked list for us to use. It can be a list of anything, so long as that type has a default constructor.

We can do:

push_back()
pop_back()
front()
back()
size()
empty()

AND:

push_front()
pop_front()

Also: Brackets are NOT usable with Only usable with or arrays.

So these are easy for insertion at head or tail.

When do we use vs a ?

Well, what if need to add stuff into the middle? The linked list would be better for inserting middle stuff, but the vector would be better for random access throughout.

This comes from the implementation details.

List Iteration

How do we iterate through a list?

Unlike a vector, we don't have [] brackets, so we need another way of going through a

None of the other STL containers have an easy way to go through themselves.

Say we have (works for lists, etc., etc stacks & quques)

We'll use an iterator variable and is like a pointer but it used only for STL containers. Typically have it start pointing it at some item, then increment and decrement to go up/down the container. The iterator can also read/write the item it points to.

vector<int> myVec; 

// This is an iterator
// specific to a vector 
// of ints

vector<int>::iterator it;

// Here, we create an iterator (scope resolved
// and clarified as being an iterator for a
// vector of ints) named it

// container<data_type>::iterator _name

To use it:

// To point at first item of container

it = myVec.begin(); 

// CANNOT do

it = myVec.front();

front() gives a value; begin() gives the location

The iterator can point it at any other vector of ints here. It's like a pointer.

Once the iterator points at a item, we can access the item's value, we can use:

// '*' operator has been overloaded

*it;

Here, we're dereferencing an iterator.

To move down one item:

it++; 

'++' has also been overloaded to get us to the next item. With a we can do +=.

There are no safeguards for ++ here, it will let us walk off the list if we're not careful. An iterator is actually its own class associated here with .

To point to the last item in the container? end() exists but points just past the last item in the container. This will let us go through everything including the last item, letting us do stuff with the last item.

To point to the last item:

it = myVec.end();

it--; // Decrement once to last item
      // Assumes list empty 

This lets us loop easily:

while (it != myVec.end())
{
    cout << *it << endl; 

    // This assumes we've defined how
    // cout should handle our items in the list

    it++; 
}

end() could be pointing to a dummy node, for example.

If we have an STL container of another class-type, we'll need

(*iterator).method(); 

Why? Because precedence(*) > precedence(.) So we can use the -> operator as well.

The * and -> operators have been overloaded. Iterators can be treated like pointers, but it is not possible to do something like begin() - end()

For EVERY STL container, the data-type held in the container must have a default constructor.

Can we have derived classes of CSProfessor and MathProfessor derived from Person. Can we then have a of Persons and then have those items set equal to a Professor? No, because polymorphism is only usable with pointers or references. We could have a of Person pointers.

E.g.:

class Base
{
    ...
};

class Derived1 : public Base
{
    ...
};

class Derived2 : public Base
{
    ...
};

list<Base> x; 

Derived1 y;

Can we do:

x.push_back(y); 

This would compile but it is not something we should do. Only put stuff that belongs into a .

But we do:

list<Base*> x; // List of Base pointers

Derived1 y; 

x.push_back(&y); // ADDRESS-OF y 

For iterators, we can compare equality if they point into the same container. Only allows for comparing vector's < >, etc.

Try overloading the * operator for our own class.

For a , use an iterator because we wanted to insert something in the middle.

Const Iterators

IF we pass in a container by constant reference, we CANNOT use a regular iterator. The regular iterator has the ability to modify the item it points to. Instead, we must use a const iterator. We'll see: cannot convert...const_iterator...iterator

void tickleNerds(const list<string>& nerds)
{
    list<string>::const_iterator it; 
    ...
}

Const iterators let us iterate through stuff, but we won't be able to modify the stuff its points at. This enforces the const promise we made.

begin() returns an iterator to the first item; end() returns an iterator to a place right below the last item.

front() and back() return the first and last values.

What is an iterator? It is an object that knows what it points to and how to go forward or backward.

// Amazing how much Carey's glasses and baldness are reminiscent // of Steve Jobs

Summary of

lets us associate two related values, just like what we did with our previous homework.

This one works likke:

map<string,int> nameToPhone; 

nameToPhone["Carey"] = 325239834;

Note that a map can only associate in a single direction, e.g. string --> int, not string <--> int

To go the reverse direction, we would need a separate .

To access a specific element at some position, use an iterator.

It works by creating a struct (e.g. Pair) that stores two items, of the types specified via template when we created the Map.

To map something to many things:

map<string, vector<int> > myMap; 

To find a previously-added association, use an iterator.

map<string,int>::iterator it; 

Then call the find() function; find() can only by used to find by the first item:

it = nameToAge.find("Carey"); 
// Binary search tree is used

We can also look at the Pair of values in the item in the Map pointers to by the iterator:

it->first;
it->second; 

What if the looked-for item doesn't exist? It returns an iterator that points to end().

A Map can only map from a single item, e.g. the first item cannot be a vector, but the second item can be.

if (it == nameToAge.end())
    cout << "Not found!\n"; 

To iterate through:

for (it = myMap.begin; it != myMap.end(); it++)
{
    ...
}

Maps always maintain their items in alphabetical order and are sorted automatically by the first parameter, i.e. by the first parameter to map, and the map will be sorted by blah, e.g. by strings.

Note that we must define an operator < for the left-hand class/struct! Why? Because maps automatically sort stuff that we add to them. If we do not do this, we will get a syntax error.

Within the map, we compare new Pairs via the first parameter. How does this all work using just the < operator?

To see if they're equal: !(a < b) && !(b < a)

The map will is thus able to determine > and ==.

Why do we use Maps? It allows for more encapsulation, for associating stuff on the fly, etc. We could always do class composition, but that takes a lot of work.

The first parameter to a MUST be a single item, but that single item could contain other data structures, including vectors, etc. We would just need to more work with the < operator.

If we do something like map<int, Stud>, then Stud no longer needs a < operator here.

Summary of

Create a set:

set<data_type> mySet; 

A set keeps a set of unique items and ignores duplicates when inserting.

insert()
erase()
size()

Are the items ordered? Yes, they are ordered smaller to bigger, and we would need an < operator for an item held in a . This allows for ordering, needed for binary search. Sets are binary search trees.

We can have sets of other data types.

To search through a set:

set<data_type>::iterator it; 

it = mySet.find(...);

if (it == mySet.end()) // Sentinel value
{
    cout << "Not found!" << endl;
}

All items will be alphabetically ordered.

To erase, we can pass in an iterator; this lets us delete specific items.

it = mySet.find("Doomed"); 

mySet.erase(it); 

// The iterator is now INVALID
// Don't dereference it! 

This does NOT erase the iterator, only the item that we point to. For sets, we can erase by value or by iterator.

Iterator Gotchas

If we have an iterator that points into a and we then add/remove items from the vector, then we must consider the iterator invalid. Remember: this is undefined behavior.

This applies to any iterators pointing into the vector before the add/remove operation(s)>

This comes from how vectors are dynamic arrays and may be creating a new dynamic array. The old iterator pointed at the old dynamic array though, which was freed from memory.

To erase an item in a (not via pop_back), do it via an iterator--but then forget about any other iterator that was pointing into that vector!

QUESTION: Do ever downsize? Implementation-dependent. There are multiple versions of the STL. Also, never subclass any STL stuff. That'd be crazy.

This is not a problem with sets, lists, or maps. HOWEVER: IF we erase the item that an iterator points to, then the iterator is invalid. Re-assign the iterator.

STL Algorithms

There is a separate find() function that can search most containers and arrays for a value.

set_intersection() finds the intersection of two sets.

To do all this: #include <algorithm>

find()

First argument is an iterator where we want to start searching. Second argument is an iterator that points just after where we want to stop searching. third argument is what we want to find.

find() returns an iterator to the item.

It could not find it, it will return whatever we passed in for the second parameter (which might not be the end() if we've narrowed down the search area).

This is a linear search.

list<string> names; 

a = names.begin(); 
b = names.end();

itr = find(a, b, "Judy"); 

find() will not look at b; it will only examine b - 1.

On an array, find will return a pointer or the value of the second parameter:

int* ptr; 

// Address-of a[4] means we only want to look
// up to a[3]; a[4] could be after the array
ptr = find(&a[0], &a[4], 19);
find_if()

find_if() will loop through a container/array and passes each item to a predicate function that we specify.

Again, first item, and place after last item.

The predicate function must return a boolean.

int* ptr;

ptr = find_if(&a[0], &a[4], is_even);

find_if() will return a pointer to the item if is_even() returns true and is done. Else, it moves onto the next item and passes a[n] into the predicate function.

The predicate function must take the item of the type in the array or container,and must return a boolean.

This all works by using function pointers.

find_if() lets us locate items meeting specific requirements.

sort()

Sort by passing in two iterators/pointers:

first one is the first item, and second one is just after the last item:

sort(item.begin, item.end()); 

To sort other items, we'll need a < operator.

Compound STL Data Structures

If we wanted a list of courses for each UCLA student?

map<string, list<Course> >

Also, leave a space between the last two > >; C++ thinks its's something else otherwise.

Again, the operator < is needed if we have something that it must compare order.

From Office Hours

// These notes were from 10 February 2014, // during office hours

// Hint on countIncludes()

If a1[0] == a2[0], recur with remainders of the two arrays

Later on, if there's another match, recur with the remainder of a1, and ALL of a2, to see if there's another permutation

If a1[0] != a2[0], check remainder of a1 against ALl of a2, to see if there's any permutation


What if we want to recursively go through a circular linked list?

void print(const Node* cur, const Node* head)
{
    // If no nodes in list
    if (cur == nullptr)
    return;

This base case check ended up being unnecessary

// One node, linked to itself if (cur->next == cur) { cout << cur->val; return; }

    cout << cur->val;

    // Final base case

    if (cur->next == head)
        retun;

    // RECURSION!

    print(cur->next, head);
}

Challenge: What about printing in reverse order?

Also, to take in an STL class-type as a parameter ( is the example here):

using std::vector;

void print(vector<int>& mylittleVector)
{
    for (size_t = myLittleVector.size(); ...)
        ...
}

Note that we must specify what the vector contains, and that we use size_t for referring to its size.

What happened this day? : 12 February 2014

// I made way too many "Big O" jokes // last night while previewing today's // lecture on time complexity

On next week's midterm: stacks and queues, inheritance and polymorphism, recursion. Nothing else.

Write code like hell. Google practice problems and solve them quickly. And again and again.

Lecture 13: 19 February 2014

Carey is having lunch at Ackerman today and we're welcome to come along to eat and chat! :D He apparently tries to do this every quarter at least a few times.

He apparently programmed while intoxicated once --and he didn't create too many bugs, haha.

Compound STL Data Structures, finished

// Reminders for midterm:

Always use an initializer list, always have a virtual destructor, and don't access private data of a base class.

We could map between a student and a list of courses:

// Note the separation between angle brackets
map<string, list<Course> > 

// << and >> are bitwise shift operators

So why do create a rather than create a Student class that has a of Courses built-in? Because: a map has binary search that has binary search that works in log2(N) time.

Example:

map<string, list<Course> > courseMap;

Course c1("CS 32");

// Put this course into the list associated with that Student
courseMap["Carey Nachenburg"].push_back(c1); 

This WILL be on the final exam!

Challenge: A compound STL data structure that associates People with their set of Friends.

// This lame brackets thing is due to be changed with C++14
map<Person, set<Person> >;

// Multiset? 

// An answer took longer than last time // "Incorrect!" // He's offering a lottery ticket this time around, haha // "Close, but no cigar." // "So close!" // "That is some ugly stuff, I don't even know..." // Uses a student's head as a desk, lol

If we have a of something, we need a < operator:

bool operator<(const Person& A, const Person& B)
{
    return (a.getName() < b.getName());
}

and require a <-operator for any left-hand template parameter.

Now associate a Person with the group of Courses and the grade they got for each course:

map<Person, map<string, Course> > myTranscript; // INCORRECT

Solution:

map<Person, map<Course, string> > myTranscript; 

We're assuming that Course has a less-than < operator. The left-hand data type for any or requires a less-than operator!

Guy who got the scratcher: "Um...I don't know how this works...I don't think I won anything."

Thanks to the STL, we can now write all this in minutes, compared to when Carey had to write everything from scratch.

Big-O Notation

Now we move on to evaluating the speed of an algorithm.

We want to be able to compare the speed of algorithms. First, we need to establish a standard for measuring speed.

We could try measuring how long it takes for something to finish, but this is inconsistent across computers and would involve really long waits for things that take forever to finish crunching.

Measuring the run-time of an algorithm is not useful.

What if we measured something via the number of instructions it takes to solve a problem of a specific, given size?

But what if it differed for larger or small problem sizes?

// "1 billiiion numbers, as from Austin Powers"

So let's do it via function that tells us how many instructions are used by a function to handle input data of some size.

"I take f(N) instructions to solve an input of N size." Where f(N) is a function.

There's Big O, Big Omega,

Best, Worse, and Average case measurements. Big O is the worst-case method.

Example: algo A takes 5*N^2 instructions for an input of N data

  1. We can compare for a given size of input
  2. We can predict the performance of these algos when applied to less or more data.

The Big-O approach measures by the gross number of steps that is requires for a size N input in the worst-case scenario.

We could be specific:

"This algo takes 5N^2 + 3N + 20 instructions to process N items."

With Big-O, we approximate, by ignoring the coefficients and the lower-order terms. We would simply say, "The Big-O of this algo is N^2". This a quick, overall impression of algo's worst-case efficiency.

STORY TIME:

He saw a food fight, back when he was in Sproul Hall, senior year, but no one was throwing food, but all of a sudden, some guys who had been mock-throwing food from the salad bar began an actual food-fight.

We use simple functions like log(n), n, n^2, nlog(n).

We would say O(n^2) as "O of n squared" or "O of nlog2(N)" (it's always assumed to be log base 2 in CS).

Computing Big-O

We need to determine the number of operations an algo performs, f(n), this is NOT Big O.

Operations:

  1. Accessing an item
  2. Evaluating a math expression
  3. Traversing a single link in a linked list, etc.

See the PowerPoint for examples.

We initialize, so one operation, we compare n and i N times, we increment N times, we initialize the inner loop counter n times (because of the outer loop), we compare n^2 comparisons.

If we wanted to compare two algo's with the same Big-O, we would compare them at the specific data sizes we're going to deal with, likely.

// York Peppermint Pattys today

  1. Determine f(n) [the number of steps required to solve a problem, in terms of the number of items n]
  2. Keep the most signficant term and toss the rest
  3. Remove any constant multiplier
  4. This is our Big O, "O of blah"

// Note that nlog2(n) > c*n for large n

Why do we toss constants? Because we're typically dealing with far more stark contrasts, e.g. nlog2(n) vs n^4

We're focusing on the most frequently-occuring operations.

So to find Big-O, just find the thing that happens the most often, and see how many steps it takes, in terms of the size of the input data.

Assume that we're analyzing for very large N; this makes the significant term obvious.

When we say O(n^2), "O of n squared", means "This algo takes roughly n^2 operations to process N items."

For very large data-sets, there is a vast difference between n^2, nlog2(n), n, etc. There can also be a O(constant), meaning we always take a certain constant number of steps for any data size.

It turns out that we cannot sort a set of data in less than nlog2(n) time.

We're almost always gonna get

log2(N), N, Nlog2(N), N^2, N^3, 2^N, N! [this last one is horrible]

log2(N) is screamingly fast, much like binary search (if something is already sorted).

The choice of algorithms makes all the difference in the world. Big-O time complexity means that we should always look for something that is fundamentally better.

There is NOT a big difference between 5N^3 and 1.5N^3.

N^3 is terrible though. This is a USC graduate that stopped drinking so much. A UCLA graduate would find something that does it in Nlog2(N). Carey cites this difference in approach as the differnece between CS-educated software engineers and self-taught coders.

We could write something that checks the size of an input and then uses the best algo for that data size.

Note that for small data-sets, there is little difference between algos. Use the easiest, least-buggy implementation. BUT for large data-sets, use the most efficient algo.

"Don't sweat the small stuff."

Do not prematurely optimize a program. Optimize a program once it works.

Big-O's origin for its name? It was originally a capital omicron and used by number theorists, apparently.

Big means capital, with O meaning order of complexity, apparently.

Jackie: "Big O might as well mean Oprah."

// Earlier, at the beginning of lecture: // "Has anyone here learned Big O before?" // I thought he'd say, "Has anyone here had a Big O before?"

Big-O Examples

Question: If I have an algo, does a less efficient algo consume more energy?

Smallberg is here! And he sorta knew why Big O was called Big O, haha, exactly as Carey predicted.

For the power consumption thing, Google worries about this, because their data centers consumes that much electricity. Their optimizations save them millions in electricity costs all the time.

Smallberg: "So are you saying that..."

Carey: "Oh dear..."

"Don't cause trouble..."

From example: For each n steps, we're gonna do n^2 steps, so O(n^3).

Anything that divides stuff in half, we're prolly gonna have a log2(n) in there somewhere.

It's a good thing that I have many of my (2^x)'s memorized for small-enough x's, haha.

Typically, we're always splitting stuff up in some way,

All logs are proportional to each other, so the log base doesn't matter that much.

The guy scratched a ticket. He just won $10,000?! No, Carey trolled him!

"Prizes may be claimed at Yo Mama's..."

OMG, Carey is too funny, haha.

Basically, multiplication is repeated addition.

We repeat something N times, then N times, then N times, we to get the total: N * k, where k might N again or log2(N), etc.

What if we had n^3 + n^2? Big-O ignores the lower-order terms; if we see two loops, just look at the larger one.

To place something at the end of an array? O(1) or O(constant).

"O of some constant" is really, really nice.

"You know what you won? Nothing!"

0 + 1 + 2 + ... + (n-1) is n * (n - 1) / 2

n * n - n / 2 --> n^2 for Big O

Shortcut steps:

  1. Locate all loops that do NOT run a fixed number of iterations, and determine their max number of iterations

  2. Turn these loops into loops with a fixed number of iterations, using their max number of iterations, e.g. replace i with n - 1 --> n.

Inner loops that compare against their outer loop counter may run a variable number of items.

Just replace the variable thing with the max number of iterations.

  1. Declare your big O.

"O of N [blah]"

If we have something in terms of Q, we would say O(Q^4), "O of Q to the fourth". It makes no sense to define a function in terms of

If we have:

for ( i < n )
    for ( j < i * i)
        for (k < j)

Then this is O(n^5), as we had n * n^2 * n^2

O(p^4)

Check what the loops' terminating conditions are

"What would you do if you didn't have fear?"

for (j < N)
    Circ arr[N];

Here, we create an array of N circles (we call the constructor N times), N times, so O(n^2).

In the loop, we construct N times, and destruct N times, so that's 2N times. This is assuming that the Circle constructor's is done in O(constant) time

An array of integers would not take this much time though; that would be a constant-time operation because all the compiler would do is allocate memory for the array, but not initialize anything.

What about multi-input algos? They take in two arguments, independent of each other.

We could end up with a Big-O time complexity of O(n * q).

// QUESTION: What if we had related arguments? Would things just be

Because the inputs are unrelated, one or the other might dominate, so we could have O(n + q).

Often, we have + when we have independent loops (or separate iterations of some sort), and * when we have nested loops (or iteration within iteration).

for (i < N)
{
    if (i == N/2)
        for (k < Q)
}

Big-O time complexity? N + Q, because only once for every every value of N do we have i == N/2, which means we only do an inner loop operation Q times total. So N + Q.

The STL and Big-O

To search a : O( log2(N) ) // Binary search; very fast

// To check if we didn't find anything; if mySet.find() == mySet.end() // end() is a sentinel value

To add to the end of a : O( 1 )

To delete the first value from a vector containing N items: O( N )

Without knowing the Big-O's of the STL classes, we won't know the Big-O of our own programs that use the STL.

If we write a loop that runs D times that searches within a set holding N items, then the Big-O of our loop is O( D * log2(N) ), as D is a variable independent of N.

Look to the PowerPoint for the Big O of the STL.

Lecture 14: 24 February 2014

We apparently totally crushed David's sections. with a median of 54/65, compared to their 48/65.

We're gonna have ice cream for the last day of class!

STL's Big-O continued

In the average case, a can insert and delete from the end in constant-time. Accessing is also done in constant-time.

When we analyze the time complexity of our own code, we need to know the Big-O of the STL's operations too, so that we know what our own code's Big-O will be.

For a or a , inserting, finding, and deleting can be done in O(log2(n)). "log n" NOT "n log n".

Note: the final exam will be more analytical than programming, more logic puzzles.

and are all constant-time for top and bottom stuff.

is O(1) or O(n) for its operations.

is the same, expect for finding an item, which will be O(x).

And reminder: Big-O is always in terms of the variables used. "n" is just the generic variable.

STORY TIME:

He was in India, at the Bombay Airport, waiting in line, trying to get into the airport.

His boss is behind him, and jittery, as he hates travel. He misheard "passport" as "password", so Carey replied "open sesame", HAHA.

Example:

set<int> nums;

for (int i = 0; i < q; i++)
    nums.insert( i );

Inserting is normally log2(q), but the set begins empty, and increases in size. For Big-O, evaluate the worst-case, which is that we need to assume that nums will hold q items.

So each time we insert, it takes log2(q) steps. Then we repeat this q times to insert q items.

If something is changing size, just assume that it's the biggest it can be, then evaluate from there on. We're assuming that it always has the maximum number of items it can have, as Big-O looks at the worst case.

Carey: "I don't have any napkins, so you can just use your shirt."

For set s, int n:

for (int i = 0; i < n * n; i++)
{
    s.insert(i);
}

The answer is O(n^2log2(n^2)) or O(n^2log2(n)), because the exponent inside the log can be taken out as a constant.

Now, we have a vector< set > v

v with N sets, and each set has Q items.

"Do you want a waffle?" "I already had breakfast."

Quite a few people actually turning down the waffles today. xD

What about number of even values in all of v ?

N * Q, because we have to go through every set in the vector. There are N sets, with Q items in each.

"You know what that sounds like? Wrong."

"Just Q?! That's worth a prize ticket--that's ballsy."

How about finding the first set with a particular value and then counting the number of even values in that set?

N * log2(Q) + Q [N or Q may dominate; need to include both terms]

We may have to go through all the sets, and then once we find the set, we have to go through all the Q items to count all the evens.

Evens-counting is O(Q) and not O(log2(Q)) because there's no built-in function for doing so in log2(Q) time; it has to be done linearly instead with an iterator.

We (+) Q because we only do the even-counting once.

Do NOT use multiplication unless something is done to every item; use addition when somethingis done to a single item.

What if we wanted to count all the evens in the

Sorting

Sorting is the process of ordering a bunch of items based on one or more rules, subject to one or more constraints.

We can sort just about anything; the number of items to be sorted is important; this affects our sort choice. Large data-sets require efficient sorting algos.

We need to figure out how to sort something, e.g. by first name, last name, and then GPA.

Constraints: Are the items in RAM or on disk? E.g., if we're sorting through Facebook's archives, and we need to sort chunks at a time. Are we dealing with something that can be fit in memory all at once?

What data container holds the data?

Rules

  1. Do NOT choose a sorting algo until we understand the requirements of a problem.

  2. Always choose the simplest sorting algo possible that meets our requirements.

Selection Sort

This is slow, and not used often in practice, but it'll come up in interviews.

Say we have a bunch of books on a self that we want to order ascending based on size of the spine.

First, we find the shortest book in the N size group.

We swap this with the first book. Then, we look at the remaining N - 1 books and select the shortest, and swap it with the second book.

Continue this until everything is sorted.

There is no n! algo that we would ever want to use.

Time complexity? O(n^2)

A step is any time we swap or point our finder at a book.

How do we arrive at O(n^2)? We're simplifying by assuming N swap steps, and then we have N + N -1 + N - 2+ ... --> N * (N+1)/2 --> N^2

When is it more or less efficient? What if something is already in order or mostly in order?

Selection sort will still be just as slow. It'll still go through everything because it doesn't know for sure that the first item really is the smallest one in the array of items.

On the final exam, we'll be asked something like: "What will this array look like after two iterations of a selection sort?"

Does a selection sort work well for a linked list? Sure! We can easily traverse a list, and the pointer-nature of nodes means we have an easy time swapping values between stuff. Note that we'd be changing what node we start at each time, which is easy, as we'd simply have simple pointer to the starting node for examination, and then we could simply follow that pointer to the next node for the next iteration.

Note that recursion is atypical for selection sort.

Is a selection sort stable or unstable?

We have a comedy show for the break.

"Don't say anything inappropriate or take off your clothes."

There are two CS majors competing in the Laugh Bowl this year. LaughFactory.com

"Adult friendships. Not like that!"

Impression of Smallberg time. That was hilarious!

Austin was the performer.

// Note: Jackie was late to class today.

People actually brought Pop-Tarts in class to toast them! xD

Stable vs. Unstable Sorting

This is not mental instability.

N old people line up to buy laxatives.

"Anybody need a definiiton for laxatives?"

The drugstore wants to sort them and serve them based on urgency.

"Who hasn't pooped in the longest time?"

Then need to choose a sorting algo that'll do things in a descending manner.

An unstable sorting algo re-orders the items without taking into account their initial ordering. E.g., Ebenezer was originally first in line, but ended up 3rd in line. This is because everyone was sorted based on the number of days they haven't ordered; the sort didn't care about the original line order.

"Andrea's my mom by the way. That would be really embarrassing."

A stable sort takes into account the initial order and maintains the initial order for items that tie based on the sorting criteria.

If you forget, just remember the laxatives!

So is a selection sort stable or unstable? Stable. We don't swap out the first item unless we find a value smaller/larger than it later in the list of stuff (depends on the sorting order).

// I love the GIF intermissions

"The dog is hyponotizing the cat. This is much funnier than you thought it was."

Insertion Sort

We use this commonly to sort playing cards.

With books:

Focus on the first two books. If the last book in this set is in the wrong order, remove it from the sehlf, shfift the books before it right as needed, and keep comparing the remove book with the shifted books, and insert it back into the proper slot.

We start with a size of two, and increase our set size, shifting books as needed.

Start with size s = 2.

While there are still books to sort:

Focus on the first s books

If the last book is out of order

Remove it

Shift the books before it to the right

insert our book into the proper slot

s = s + 1

Breaking ties depends on our comparison.

For Big-O. We may shift up to one book for round one. For round two, this might be two books.

During the last round: N - 1 shifts t to find the right spot (we're assuming insertion is done in constant time).

This is roughly O(N^2) steps overall.

If all the books are all already in the right order, then insertion sort never does any shifting, and will take O(n) time to figure this out. This is the best case for insertion sort.

A perfectly mis-ordered set (i.e. reverse of our intended order), will take N^2 steps.

See the PowerPoint for the implementation code.

Is this a stable sort? This depends on the implementation; by default, it is generally stable, as it won't move something unless necessary.

Bubble Sort

Everyone loves to make fun of bubble sort.

Start the atop element of the array.

If the first two elements are out of order, swap them.

Then advance forward, a[1] and a[2]. Compare them, if so, swap, then advance again, all the way till the end of the array.

IN essence: check two items at a time.

If we made any swaps, repeat the whole process.

Example: celebrities sorted based on the number of times they've been in rehab.

The smaller items "bubble" up toward te top.

Mentioning bubble sort would likely cause the interviewer to laugh.

Bubble sort has a bad (bubble) "wrap"

During each pass, we compare every element with its successor, N steps, and we if made any swaps, we may have to repeat this process, which means in the worst case we'll do N passes of N bubbles --> N^2

Bubble sort is O(N^2)

What if the data is already in order? O(N) to find out that the data is already in order.

Ask the interviewer: Does the provided algo terminate after making no swaps, or does it always go for N^2 times?

Final exam: We'll be given an array partially sorted, and we'll be asked: "Which sort did this?"

Every sort is different. The results are distinguishable.

Is bubble sort stable? Yes. We don't move stuff unless we necessary.

"The Lion Sleeps Tonight" --> Sorting dance, haha.

How to tell stuff apart (after one round of sorting):

Selection sort: Is the smallest item in the first slot?

Insertion sort: Is the second item smaller than the first item?

Bubble sort: Are the last two items out of order?

Note that bubble sort will always leave the biggest number in the last slot after the first iteration. Then on the second iteration, the two biggest numbers will be there, and so on.

Shell Sort

The Big-O of shell sort is actually unknown.

h-shorting

h-sorting underlies shell sorting.

Pick a value for h (some positive whole number)

Compare a[i] and a[i + h]; if they are out of order Swap tem If we swapped any items, repeat the whole process again

Bubble sort is basically an h-sort with a value of h = 1

A higher h-value does not make h-sort more efficient. An array that is h-sorted may not be truly sorted (unless h = 1). All h-sort does is guarantee that the i item is less than the i + h item.

So we'd compare first item and fourth item, then second item and fith item (h = 3). Then here, every item is less than the item 3 places away from it. It would be "3-sorted".

Shellsort

Pick a sequence of decreasing h-values ending with an h-value of 1: e.g. 8, 4, 2, 1

There have been many attempts to figure out the best sequence.

It is required that we end with h = 1. This guarantees that stuff actually gets sorted.

How does it work? We h1-sort, then h2-sort, then h3-sort, etc.

Example: 8-sort, then 4-sort, then 2-sort, then 1-sort (bubble sort).

Common pattern: exponential-decreasing h-values.

With each h-sort, we're making the array more sorted each time for the next sorting pass, so the end result is less than O(n^2) [the Big-O for bubble sort].

Can this be applied easily to a linked list? Sure: Santo had the idea of having two separate pointers.

We simply advance the pointers, with the starting difference being the h-value.

"You're now immortalized in my lecture notes."

Shell sort is not a stable sort. "Look at Wikipedia."

Shell sort is estimated to have a time complexity of ~O(N^1.25). It's usually used on low-memory run environments, as it uses little memory.

Lecture 15: 26 February 2014

Quicksort

But first, an STL challenge:

std::map > habitationHistory;

P people, with E former streets.

Finding the names of all people who lives on levering street? Assuming we have a set. P * log2(E). We have to go through all the people and then check their set of former addresses.

Bill ever lived on Westwood? log2(P) + log2(E). We find the right person, then we check if the that street is in their history.

Print out every name with each person's streets, in alpha order. P * E. We go through every person and then through all their streets. or a is already in order.


Okay, on to quicksort and *mergesort, the divide-and-conquer algorithms. There are known as the efficient sorts and are the ones we normally use in regular software engineering.

In general, they work like this:

  1. Divide the data-set into two groups of roughly equal size
  2. Sort each of these sub-sets (conquer)
  3. Combine the two sorted groups into one large sorted list (Line up your conquered enemies and make them watch you listen to you gloat about your victory.)

Notice how this is perfect for recursion!

Quicksort works like this (what we did a previous homework assignment without realizing it):

  1. If the array contains only 0 or 1 element, return
  2. Select an arbitrary element P (pivot) from the array (typically the first one)
  3. Move all elements that are less than or equal to P to the left of the array and all elements greater than P to the right. This is partioning (divide), and is what split() did in our homework. Note that the elements on either side are not in order (at this point). They're just less than or greater than the pivot value.
  4. Recursively repeat this process on the left sub-array and on the right sub-array This is the conquer step. Why do operate on the sub-arrays and forget about the pivot? Because it's already in the right spot! Everything to the left and to the right is out of order, but the pivot value fits between them. Note however that the pivot value will not always end up in the middle once the array is sorted.

Note that we could reverse this so that larger ends up on the left, and and smaller on the left. Note that this sort is unstable, as ties do not maintain their original order.

In more advanced algos, multiple values are picked randomly, find the median element, and then use that (since it's closer to the true median value).

In code:

void quickSort(int array[], int first, int last)
{
    if (last - first >= 1)
    {
        int pivotIndex;

            // Divide!

        pivotindex = partition(array, first, first);

            // Conquer!

        // Left side; don't touch the pivotValue again
        quickSort(array, first, pivotIndex - 1); 

        // Right side; don't touch the pivotValue again
        quickSort(arary, pivotIndex + 1, last); 
    }
}

See split() in the homework, which modified parameters to let us know what the partition values were.

partition() will actually complete in O(n) time. Why? Because its low and high trackers are checked to see if low ever exceeds high, which would mean we hit the end.

Note also how the pivotValue may not end up in the exact middle.


What's the Big-O of quicksort? Well, we go through the array to partion it, which takes N steps, then we repeat this for each half. The number of halves? log2(N) [2 ^ what power is equal to the size of the data-set?]

For each iteration, we partition, costing N steps, then we partition the halves, N/2 and N/2. Then four arrays, partitioned at a cost of N/4 + N/4 + N/4 + N/4. N steps!

So, we take N steps each time to partition (as we just showed), and we repeat this log2(N) times (the number of halves we can make till we hit just 1 or 0 items left [our base case]) in a subarray.

So, quicksort's average Big-O is O(nlog2(n))

However, quicksort is very slow for a set of data that is already sorted or mostly sorted. Then, the partitioning hardly moves anything around but still takes N steps anyway. Then, when we recursively do this, there is no left or right side. The problem reduction is minimal, so the "problem" is solved slowly.

We repeat this process N times (no split), and each time we partition, we take N times, so it takes N^2 now.

Then, the algo will only lop off item off the side each time, and then repeat this N items, for N partitions each time. This problem also comes up with data that is in reverse order.

So quicksort's worst-case Big-O is O(n^2)

AVOID quicksort for data that is already mostly or completely sorted, or in (mostly) reverse order (everything gets moved to one side [no splitting]).

For an array of N items, which has N! possible configurations, quicksort is nlog2(n) for most of the configurations (which would be out of order).

Quicksort works well with a doubly-linked list as we can go up and down easily. It is an unstable sort, because the pivot pick is rather random, and we might end up moving stuff around.

In terms of memory usage, quicksort's RAM requirements vary and can be memory-intensive.

Can it be parallelized across multiple cores? Yes: once the partioning happens, the subsets can be given to different cores, which can distribute again if we have a lot of cores.

Mergesort

Merge takes pre-sorted ararays as inputs and outputs a combined third sorted array. We learned this as the Lazy Person's Sort.

The underlying basic merge algo:

Take the left-most book in both shelves. move the the smallest book to the new, third shelf.

In other words: go through both arrays, compare their corresponding elements, and copy over the smaller/larger value into the third result array (depending on if we want ascending or descending).

If either array runs, copy over the entire remaining contents of the other array (they're guaranteed to belong there, since the arrays are pre-sorted).

We can take a single array and split using different indices trackers (assuming the tracked parts are already sorted into two parts, and we know where those parts begin).

Once all this is done, we copy over the contents of the third, temporary array into the original input array. Delete the temporary array.

Full mergesort algo:

  1. If array has 1 element, base case: return
  2. Split array into two equal section3
  3. Recursively call mergeSort on left half
  4. Recursively call mergeSort on right half
  5. Call basicMerge to combine the resulting halves

The base case is 1 and NOT 2, because the two items might be out of order, which basicMerge would take care of.

// Many people are missing from the class today, haha, // likely on account of Project 3

Look to the UCSF visualization of sorts

// Holy cow, Carey's calendar is ridiculous! // One way to keep programming: do just enough // to get more money but not be promoted


STORY TIME:

Back when Carey was an intern at Symantec, he was analyzing DOS viruses. The company wasn't as strict back then. Everything is kept locked up in a lab. But back then, he was allowed to login remotely and copy files back and forth to get some work done. So he had a virus on the computer on work computer, on the gateway, and he was about to transfer it back, but he wrote "copy [blah]" but this automatically ran the copy.exe virus on the gateway computer. He realized this, and tried to manually clean up the gateway. He does so. His colleague: "Dude, you infected the entire network!"

Every computer is running a scan of Norton and every file is coming up infected. He fears being fired and going to jail. He's crying. His boss apparently pulled a joke. A scan found the infection right away and removed it. They made a joke definition that would detect every file, and so it made look like everything was infected.


NOTE: mergeSort works in-place, all within the array, except for basicMerge() part, which requires a temporary array.

Big-O analysis time:

The maximum number of levels for mergeSort? log2(N). What about the merging cost? We merge a total of N items at the bottom (halves + halves + halves + ...)

At the second-to-bottom level, it also takes N steps.

At every level, we merge N items.

So mergeSort() is always O(nlog2(n))

Why would we choose quickSort() over mergeSort()?

Because mergeSort() requires allocation of temporary containers (in fact, double the memory)!

quickSort() does not require that.

mergeSort() caveats? No, regardless of how items are arranged. The time and memory cost comes from allocating temporary containers for basicMerge()

Is this easy for a linked list? Yes, just follow the links, swap values as needed.

It is a stable sort. Are there are any special uses for mergeSort() that other sorts can't handle? Yes: if we have large datasets split across multiple hard-drives, then mergeSort() is perfect for it, since reading/writing to HDDs is slow.

It can totally be parallelized across mulitiple cores, though basicMerge() must be done under a single core.

Look at the cheat sheet!

Trees

A special linked data structure that has many uses in CS.

It can manipulate hierarchical data, make information easily searchable, manipulate sorted lists, simplify expression evaluation, and make decisions (decision trees).

Time for some inappropriate.

Go back 32 levels from a person (32 generations), we'll have ~ 4 billion. So go back far enough, and it looks like everything is incest, haha.

Treets are made of nodes, with a root pointer, analogous to the head pointer of lineked lists. The root node, pointed to by this root pointer, may have 0 or more children nodes. And so on for each of the children nodes.

Trees with two children for each node are called a binary tree.

A tree with no nodes is call an empty tree, typically a base case.

A node with 0 children is called a leaf node.

If the root has no children, it is a root and a leaf.

Trees are linked lists with multiple forward pointers.

Binary Trees

A tree where every node has at most two children nodes.

With the exception of the root node, every node has exactly one parent. Every two nodes descending from the same parent node are called sibling nodes>

An ancestor node is one which lies between the current node and the root node, including the root.

Amongst the levels, we don't have links: if we did, that'd be a graph.

Subtree: Any node in the tree can be viewed as the root of a smaller tree, a subtree. We'll use recursion to process subtrees on either side of a binary tree.

"A binary tree is bi, not that bi"

Left and right sub-trees: If we pick a node from our tree, we can identify its left and right sub-trees.

Node depth is the deptht of a node is the distance of a node from the root of the tree, where the root has dept 0.

Full binary tree: Every leaf has the same depth and every non-leaf (not counting the root node) has exactly two children. N depth, with 2^(n+1) - 1 nodes

Many operations are possible with a tree. We can add items, delete items, search for something, remove a section of a tree (pruning) or add on a section (grafting).

To show that a child does not exist, use a nullptr.

Smallberg: "I deliberately tanked my class so I could get ice cream."

Binary Tree Traversals

Any time we traverse through a tree, we always start with the root node.

Four ways to do this:

  1. Pre-order
  2. In-order
  3. Post-order
  4. Level-order

Pre-order Traversal

It's recursive.

  1. Process the current node (add, print, etc.)
  2. Process (recursively) the nodes in the left sub-tree
  3. Process (recusrively) the nodes in the right sub-tree

Why "pre-order"? Because the first thing we do is we process in the value in the node first.

Dingleberry man visited to watch the lecture: "Carey on!"

void preOrder(Node* cur)
{
    if (cur == nullptr)
        return; 

    cout << cur->value; // Process the current node

    preOrder(cur->left); // Recusively process left sub-tree
    preOrder(cur->right); 
}

Note that the subtree process calls will NOT have knowledge of the nodes above it. Instead, it's as before with recursion, when recursively operating on an array meant we only had knowledge of our current subset of it.

Going to a leaf's child will give us a nullptr, meaning we process the leaves too (check if child pointer is nullptr would skip leaves).

This is a depth-first search. It can also be done with a stack.

We visit every node ONCE, so traversal is O(N).

In-Order Traversal

  1. Process the nodes in the left sub-tree
  2. Process the current node
  3. Process the nodes in the right sub-tree

Processing the current node happens in-between processing the sub-trees.

Notice the order in which stuff gets printed out.

Post-Order Travesal

  1. Process the nodes in the left sub-tree
  2. Process the nodes in the right sub-tree
  3. Process the current node

We always go left-to-right on trees.

In-order used for binary search trees typically.

Level-Order Traversal

NOT recursive.

  1. Use a temp pointer variable and queue of node pointers
  2. Insert root node pointer into the pointer
  3. While the queue is not empty: A. Dequeue the top node and put it into temp B. Process the node C. Add the node's children to queue if they are not nullptr

Again, what we did on the second midterm.

We visit each level's nodes, left to right, before going onto nodes in the next level. This results from the FIFO nature of a queue. This one is a breadth-first search.

// Carey just asked us to pump up his BruinWalk score, haha.

Big-O of Traversals

Every traversal visits each node up to three times (hit it, go left, return, go right, return), so they all take O(n). We don't skip nodes or skip branches.

Lecture 16: 3 March 2014

// It's already March!

// Project 4 spec's is already partially up // It's a database-building project // It's meant for storing and querying data // It can also order and output data // It'll be done with binary search trees

Evaluating Expressions

Previously, we've done evaluation of postfix expressions.

Now, we can do arithmetic expressions with binary trees!

// I wonder about the steps required to get it all into the // tree though.

CS 132 for compiler-writing, useful for evaluating expressions. Data structures come up again with compiler writing too.

Say we have something like this:

        *
    +       -
  5   6   3   1

We begin with the root pointer and evaluate using this general algo:

  1. If the current node is a number, return its value (This is our base case)

  2. Recursively evaluate the left sub-tree and get the result

  3. Recursively evaluate the right sub-tree and get the result

  4. Apply the operator in the current node to the left and right results and return that.

This is a post-order traversal.

This could of course be generalized to any sort of operator/operation, operating on many types of values. Our nodes could contain pointers to functions, or have functions unto themselves, etc. Code is powerful.

This could work for boolean expressions too, where NOT would have a single child.

Quick bit of code to do this:

template <class Data>
struct Node
{
    Data m_value; 
    Node* m_left; 
    Node* m_right; 
}


Data evaluate(Node* cur)
{
    if (isnum(m_value))
        return m_value; 

Binary Search Trees

NOTE: Binary Tree is NOT a Binary Search Tree.

A BT has two children per node. A BST has ordered children per node. Read the problem VERY carefully.

BSTs were designed to rule search.

This is made possible by their structure:

For any given node in a BST:

  1. All nodes in the left sub-tree must be less than the current node's value

  2. All nodes in the right sub-tree must be greater than the current node's value

Some special cases allow for <= or >= as well.

Note that BSTs are not always balanced.

Does this make a difference? Yes, it does. We'll see.

Are duplicates allowed? Depends on our needs.

We can choose to always place duplicates on the left or right side, or have a third field in each node that has a list of all the duplicates.

We can do many different things with BSTs:

  • Check if it's empty
  • Search it for a value
  • Insert an item
  • Delete an item
  • Find the height of the tree
  • Traverse the binary tree (used for many of the above)
  • Free the memory used by the tree (a necessity!)

Searching a BST

To search a BST:

  1. Begin at the root node

  2. Continue forward until we hit a nullptr

  3. If goal is == current node's value, then found! We can return true, or a pointer to the node, etc.

  4. If goal is < current node's value, go left

  5. If goal is > current node's value, go right

  6. If we hit a nullptr, the value was not found in the BST; indicate that to the caller in some way

What if there are duplicates? We'd have to keep traversing. Why would we have duplicates? Because we have two people with the same name but they also have other data.

Carey bought all the prizes at Walmart and all the "inappropriate prizes" at Ahhz. The STL is actually using a BST. and also use BSTs. We're learning how to do this stuff from scratch.

Recursively:

template <class Data>
class Node
{
    Data m_value;
    Node* m_left;
    Node* m_right;
};

These would be part of a larger BST class.

template <class Data>
bool searchBST(Data value, Node* ptr)
{  
    // Not found
    if (ptr == nullptr) 
        return false;  

    // Found!
    else if (value == ptr->m_value)
        return true; 

    // Value is less than current
    // Go left
    else if (value < ptr->m_value)
        return(Search(value, ptr->left));

    // Don't forget to return the result
    // of a recursive call!

    // Value is greater than current
    // Go right
    else  
        return(Search(value, ptr->right));
}

Iteratively:

template <class Data>
bool searchBST(Data value, Node* ptr)
{  
    while (ptr != nullptr)
    {

        // Found!
        if (value == ptr->m_value)
            return true; 

        // Value is less than current
        // Go left
        else if (value < ptr->m_value)
            ptr = ptr->m_left;

        // Value is greater than current
        // Go right
        else  
            ptr = ptr->m_right;
    }

    // Not found
    return false;
}

// I just earned some Oreos and a prize ticket // for answering that the average Big-O // for an average BST is O(log2(N))

// It is NOT (Nlog2(N)); after all, // we can traverse in O(N); why the hell // would searching a binary search tree // take longer?

In the average case, searching a BST will take O(log2(N)) time, as we eliminate 50% of the possibilities each time we go left or right. In the worst case (where no branching off is possible), searching will take O(N) time.

The latter comes when we have a badly-formatted BST.

4 billion nodes can be searched in just 32 steps.

Inserting a New Value into a BST

Insertion is trickier? Why? Because we have to maintain the tree's very specific structure. The new value must be placed such that the tree is still a BST afterward.

// Calling our search() function as our first step would be lame // That's adding extra, unnecessary steps. Just have insert() // be its own thang

General algo:

IF the tree is empty
{
    Allocate a new node with given value
    Point root pointer to new node
    RETURN
}

Begin at root of tree

// Stopping condition checked iteratively or recursively
WHILE we're not done 
{
    // Value already exists; duplicates not allowed with this one
    IF given value is == current node's value
        RETURN 

    IF given value is < current node's value
    {
        IF there is a left child
            Go left
        ELSE
            Allocate a new node with given value
            Set current node's left pointer to new node
            RETURN
    }

    IF given value is > current node's value
    {
        IF there is a right child
            Go right
        ELSE
            Allocate a new node with given value
            Set current node's right pointer to new node
            RETURN
    }
}

QUESTION: What if a new node belongs somewhere in-between the root node and its descendants?

ANSWER: It would end up as a right child node of the intermediate.

As for Big-O? Well, we find the right insertion spot in O(log2(N)) time (or worst case, O(N) time), and then insertion is done in constant time.

Note how classic binary search trees just add stuff in whatever order it happens to arrive.

And deletion? Deletion is a huge pain with BSTs...

QUESTION: What if we had to delete the root node?!

// Carey is eating dinner with his TAs tonight // He'll probably grill them intensely, haha

Given a random array of numbers, if you insert them into a BST, the resulting tree will be rather bushy, and its depth will be around log2(N).

But if we insert an ordered array of numbers, the BST will be a long line of nodes, a really inefficient structure for a BST.

If our values are largely ordered, consider inserting them radiating outward from the median, randomly, etc. That will lead to a much more balanced BST.

So why do we assume log2(N) for BSTs? Most are gonna meet that.

Finding the Min & Max Values in a BST

This is actually very easy with a BST, thanks to its structure.

To find a min, just keep going left!

Iteratively:

template <class Data>
Data getMin(Node* ptr)
{
    if (ptr == nullptr)
        return TREE_EMPTY;

    while (ptr->m_left != nullptr)
        ptr = ptr->m_left;

    return ptr->m_value;
}

Recursively:

template <class Data> 
Data getMin(Node* ptr)
{
    if (ptr == nullptr)
        return TREE_EMPTY;

    if (ptr->m_left == nullptr)
        return ptr->m_value;

    return getMin(ptr->m_left);
}

To find a max, just keep going right:

template <class Data>
Data getMin(Node* ptr)
{
    if (ptr == nullptr)
        return TREE_EMPTY;

    while (ptr->m_right != nullptr)
        ptr = ptr->m_right;

    return ptr->m_value;
}

Recursively:

template <class Data> 
Data getMin(Node* ptr)
{
    if (ptr == nullptr)
        return TREE_EMPTY;

    if (ptr->m_right == nullptr)
        return ptr->m_value;

    return getMin(ptr->m_right);
}

This can be done in O(log2(N)) time. Compare this a regular ol' binary tree, which will be O(N).

REMEMBER: Check: Is it a BT or a BST?

Printing out a BST Alphabetically

This is simple:

Use the in-order traversal pattern, as this will go down the left, then the current nodes, then the right, which aligns perfectly with alphabetical order.

void printBST(Node* cur)
{
    if (cur == nullptr)
        return; 

    printBST(cur->m_left);

    cout << cur->m_value;

    printBST(cur->m_right);
}

This will be done in O(N) time, as we need to visit all of the items.

This works for printing stuff out in numerical order too!

This is because in-order goes in-order: the stuff that is less, then the middle, then the bigger.

// Ah, I never could handle the sugariness of Oreos

Destructing a BST

Even the oldest of trees must die eventually.

But how do we do so? Every node will have to be destructed because it was likely manually allocated.

Easy: use the post-order traversal pattern. The youngest die first.

void razeBST(Node* doomed)
{
    if (doomed == nullptr)
        return; 

    // Go for left subtree
    razeBST(doomed->m_left);

    // Go for right subtree
    razeBST(doomed->m_right);

    // Delete current node
    delete doomed;
}

Here, again, Big-O is O(N), as we must visit every node.

This allows us to avoid losing the left and right pointers.

Deletion in a BST

// 9,000 lines of code!


STORY TIME:

The guy who pulled that joke on Carey (with all the scans running).

Carey was once an intern and had been working on something for a month. He booted up his computer one day: "No hard drive found."

He was thinking about he should have used version control. He opens the chassis, and found that his hard drive had been disconnected. It was a prank.

He built a password sniffer, got his password, stored it and said it whenever he walked by Sammie.

Sammie was in charge of the compilation and build process.

He came back from a night of partying. Carey wrote a program that would tweak all the assembly code to have syntax hours. It was only on his computer. It produced thousands and thousands of errors when Sammie tried to run the build. Carey notes that he would be fired for such pranks these days. Symantec was like a start-up in those days.

Carey: "Don't ask for permission, ask for forgiveness."


To delete something from a BST, we need something to take the place of the deleted node. How do we handle the re-linking?

If we don't handle the deletion properly, we'll break the unique structure that characterizes a BST.

High-level algo:

Given a value V to delete:

Find the value V in the tree with a standard BST search
{
    Use two pointers: a cur pointer and a parent pointer    

    If the node was found, delete it from the tree, preserving
    the structure
}
  1. Search for the value V:

    Find the parent node of the doomed node

  2. Deletion has 3 cases:

    • Node is a leaf node (this is easy)

      • Delete the node, set the parent's child pointer to a nullptr
    • Our doomed node has only one child

      • The grandchild jumps up to take the part of the child
    • Our doomed node has two children

Case 1:

// Determine if it's the left or right
// child that is doomed    
if (parent->left == cur)
    parent->left = nullptr;
else if (parent->right == cur)
    parent->right = nullptr;

// Delete the node
delete cur; 

Special case: What if it's the root node that is doomed?

The parent pointer is nullptr

If the root node is a leaf (there's only one node in the BST), delete the current node (the root node) and set the root pointer to nullptr.

Case 2:

// Get a pointer to cur's only child
Node* grandchild; 

// Since this is case 2, we know that
// there is only one child node

if (cur->left != nullptr)
    grandchild = cur->left; 
else
    grandchild = cur->right; 

// Link parent to grandchild
// This left/right check maintains
// the BST structure

if (parent->left == cur)
    parent->left = grandchild;

else if (parent->right == cur)
    parent->right = grandchild; 

delete cur; 

If the doomed node is the root node (with a single child):

// Get a pointer to cur's only child
Node* grandchild; 

// Since this is case 2, we know that
// there is only one child node

if (cur->left != nullptr)
    grandchild = cur->left; 
else
    grandchild = cur->right; 

rootPtr = grandchild;

delete cur; // Where cur == original root node

Case 3:

We need to select a replacement that will still leave the BST consistent (and we can't add anything). It's a sort of puzzle.

In general, when deleting a node K, we want to replace K with either

  1. K's left subtree's largest-valued child

  2. K's right subtree's smallest-valued child.

This works out to preserve the structure. Either one works.

It is actually two deletions, because we moving means we have to delete the moved node too.

Goal: Replace target node with a name that is > all names in left sub-tree or < all names in right sub-tree

ptr = cur-> left
while (ptr->right != nullptr)
    ptr = ptr->right; 

Copy ptr's node's value into temp
Remove the node pointed to by ptr (the replacement) from the tree
    This is a recursive call, either case 1 or 2
    (as it's the rightmost or leftmost node;
    here it's the leftmost node)
Copy temp into cur

Case 3 deletion requires Case 1 or Case 2 deletion as well!

Then, the deletion will have been completed.

This WILL be on our final exam. Deletions in general will cause a classic BST to become more and more unbalanced.

No one uses classic BSTs these days; they just can't maintain their efficiency. So instead, we'll use a balanced binary search tree, which is what used in STL's , and .

Note that and are balanced search trees.

To print stuff out, it simply uses an in-order traversal to print the items out in order.

Office Hours

// He's actuallly using the projector in this room today, // which is cool

// Jeffrey figured out another algorithm for BST node deletion // It heavily increases the depth of the tree though, // which decreases the efficiency of all of its operations

The old way of writing function pointers:

insertion_sort(parameter, bool (*comp(...));

Smallberg wrote it

insertion_sort(parameter, bool comp(...));

This lets us pass functions to functions.

This allows non-member functions to call upon other functions.

This lets us be more flexible with a function; we can just change what sub-algo we pass into an algo, and instantly switch out what it does. Note that the pointer function that we pass into had better have the same signature (return-type and parameters) as we list in the function parameter.

e.g. :

function(int parameter, string parameter, int sub_algo(char parameter1));

Then the sub_algo() looks like this:

int sub_algo(char parameter1);

And the function call looks like this:

function(5, "test", sub_algo('k'));

QUESTION: Can we templatize function pointers?

Duplicates: If it was a single item, then we could just maintain counters at each node for duplicates. Most BSTs have more data associated with each node though.


Challenge problem: Found an O(N) way to sort an array of 1 million random numbers whose values range from 1 to 5.

We could just go through and count the numbers of 1's, 2's, etc., then go back through the array and stick that many 1's, 2's, etc. in.

This is done in k * N time, where k is a constant (the range span, here 1-5). This beats O(nlog2(n)), the best time complexity we know of for data-sets where we don't know much about their contents.

With something like the 1 million 1's, 2's, 3's, etc., though, we know a set of very specific contraints on the data, and can figure a clever O(n) way to sort them. O(n) should be the lower bound to sort the data, as we have to look at all the data. Unless we have something where data knows about other data and its order, O(n) should be the lower bound for sorting.

!nullptr == true

dynamic_cast: the cast will work if the intended result is the same thing or something derived from it.

"Are all [blah] are [blah]?" We cannot go up the hierarchy, e.g. a subclass pointer cannot point to a superclass, so an attempted dynamic_cast in that direction would not work.


Challenge:

Lecture 17: 6 March 2014

// Getting close to exceeding the number of lines // of notes written for CS 31! // I wrote 9,348 lines of notes for that class. // Now, CS 32 will exceed it handily. // Strange to think that I've written over 18,000 lines // of notes for CS

Huffman Encoding

Huffman encoding is one data compression technique used for compressing/decompressing files, the sort of thing we use to create ZIP archives and what-not.

First, a review of ASCII.

ASCII is the encoding scheme used by most modern computers. In this schema, each character is stored in memory as a number, e.g. 'A' is 65.

This abstraction is merely a nice cover for how everything is actually stored and handled as binary bits instead.

Huffman encoding works off the fact that many things repeat sequences of bits. Also, note that this is a lossless compression method.

Its general algo:

  1. Compute the frequency of each character
  2. Build a Huffman tree (a binary tree) based on these frequencies
  3. Use this binary tree to convert the original file's contents to a more compressed form
  4. Save the converted (compressed) data to a file

Count Frequency

The first step is really like computing a histogram, a chart that records how frequently something shows up.

These are common in early elementary:

// The frequency with which the 
// digits 1, 2 & 3 appear in some larger number,
// as one arbitrary example 

        x
x       x
x   x   x
x   x   x

1   2   3

For Huffman encoding, we'll probably have something like:

CHARACTER      FREQUENCY
---------      ---------

   'U'             5
   'C'             9
   'L'             2
   'A'             4
   '!'             3

Build a Huffman Tree

To build a Huffman tree based on those frequencies:

NOTE: A Huffman tree is a binary tree, NOT a BST.

Create a binary tree leaf node for each entry
in the frequency count table, but do NOT
insert any into a tree (yet)

While we have more than one node left: 

    Find the two nodes with lowest frequencies

    Create a new parent node

    Link the parent to each of the children

    Set the parent's total frequency equal to
    the sum of its children's frequencies

    Place the new parent node in our grouping

Now label each left edege with a 0
each right edge with a 1

The bit encoding for a character is the path of 0's and 1's taken from the root for three to the character of interest.

Multiple trees are possible (depending on how we grouped nodes together, as there can be ties), so multiple encoding schemes are possible. Note how it uses fewer bits for more common characters. In addition, the encodings have unique prefixes. It is unambiguous in this encoding as to what encoding lines up to what character. This can be done with groups of characters too.

Compression

Now use the binary tree to convert the original file's contents into a more compressed form, i.e. find the sequence of bits (1's and 0's) for each char in the message.

Save the Archive

Now take this compressed sequence and save it to a file, one that will be much smaller than the original file.

Of course, we need to attach the encoding scheme used, or else we won't know what each sequence of bits was supposed to represent. We need to encode the tree in a way: each tree was unique, so it's added overhead.

For small enough stuff, that overhead would push the "compressed" file over the size of the original, for larger files, we can save 40-80% of disk space!

Decoding

To decode, we:

  1. Extract the encoding scheme from the compressed file

  2. Build a Huffman tree (a binary tree based on the encodings) Follow the 0's and 1's, as they indicate left/right, and insert a new node there.

  3. Use this binary tree to convert the compressed file's contents back to the original characters Go until we hit a leaf, then output the character located there.

  4. Save the converted (uncompressed) data to a file

ZIP files use an even more effective compression.

The best we can do here is compress from 1 byte to a bit. If we compress larger characters, we can save even more space.

Balanced Binary Search Trees


To insert: O(log2(N))

To search: O(log2(N))

To erase: O(log2(N))

Traversal: O(N)

BBSTs are O(log2(N)) for everything except for traversal. Note how they don't have the worst-case O(N) possibility, unlike a normal BST.


We've noticed that BSTs become less efficient over time as we insert and delete nodes. Often, this is because they linearize out and deepen in their depth. Ideally, we want to make as few visits to nodes as possible to get to stuff and get stuff done. We don't want a pathological trail that takes forever to traverse. We want a bushy Christmas tree.

We want to maintain an even tree.

Definition: A binary tree is perfectly balanced if for each node, the number of nodes in its left and right subtrees differ by at most one.

Three popular approaches exist for building a BBST:

  • AVL trees
  • 2-3 trees
  • Red-black trees

We're doing AVL; look up the others sometime. There are many others too. They shift nodes around as needed to balance the tree.

AVL Trees

AVL Trees are BSTs in which the height of the left and right sub-trees of each node differ by at most 1.

Note the difference in balancing requirements.

They are implemented by assigning each node a balance value:

0: the node's right and left-subtrees have the same height -1: the node's left subtree is 1 higher than the right 1: the node's right subtree is 1 higher than the left

Insertion

Case 1:

After we insert a new node into the AVL tree, all nodes in the tree still have balances of -1, 0, or 1.

In this case:

  1. Insert the new node normally (just like in a vanilla BST)
  2. Update the balances of all the parent nodes, from the new leaf to the root
  3. If all of the balances are still 0, -1, or 1, done!

Case 2: We insert a new node, and it causes one or more balances to become less than -1 or greater than 1

This requires us to rebalance the tree to the range of acceptable balances.

There are two-subcases: single & double rotation

In single rotation, some nodes are rotated over once. In double rotation, two rebalances are required.

There are at most two shifts in an AVL tree.

Note that the STL and classes use BBSTs (though not necessarily AVL trees).

Know that rebalancing (even twice) is O(log2(N)), so insertion is still O(log2(N)).

The Modulus Operator

Time for Carey's favorite data structure, hash tables.

O(log2(N) + L)

Reminder: % operator returns the remainder of dividing something by something:

1234 % 100 == 34

100 goes into 1234 twelve times, remainder 34

Note an interesting property of finding the remainder of a division:

E.g. N % 5:

0 % 5 = 0 1 % 5 = 1 (5 doesn't go into 1 at all) 2 % 5 = 2 3 % 5 = 3 4 % 5 = 4 5 % 5 = 0 (clean division) 6 % 5 = 1 7 % 5 = 2 8 % 5 = 3 9 % 5 = 4 10 % 5 = 0 ...

Note that modulo of a number returns a range of numbers guaranteed to be between 0 and that number N - 1, so (variable % N) ranges from 0 - (N - 1)

To get a specific range:

% range + beginning

range = (max - min)

Hash Tables

Thus far, the most efficient ADT we know of thus far is a balanced binary search tree, O(log2(N)), for everything.

Can we do better? How about the audacious goal of attaining O(1)?

Let's begin with a pseudo-predecessor to a true hash table:

What if we wanted to create an ADT that could store all the UCLA Student IDs (9 digits), where the indices are the ID numbers. That would a 1 billion element array!

To add a new ID#: set array[N] = true

We now know that that ID is active when we go straight to it. Accessing an element in an array is done in constant-time.

This is insanely fast--but insanely expensive in terms of memory. We only have ~50,000 students, but have 1 billion element array. We're wasting 999,950,000 slots just to know if a student ID is active or not.

So let's reduce the number of slots required.

NachenSmall Corp. dictates that our program must use 100,000 slots.

We need a mathmatical function that can take in an ID# and somehow converts it to a unique slot number between 0 and 99,999 in the new, smaller array.

Our domain is [0, 1 billion - 1] and the range is [0, 99,999] for our function.

f(x): [0, 1 billion - 1] -> [0, 99,999]

This will be our hash function for converting between the original and something smaller and more compact.

To add a new item:

void addItem(int n)
{
    int slot = hashFunc(n);
    m_array[slot] = true; 
}

Or: m_array[hashFunc(n)] = true;

Slots in hash tables are called buckets.

int hashFunc(int idNum)
{
    int bucket = idNum % ARRAY_SIZE;
    return bucket;
}

This function will return values between 0 and 99,999, perfect for our new, smaller array.

Hash Collisions

Note how we may end up with the same hashes. This is known as a collision, and this is a problem.

For us, this happens when the last five digits of the ID number are the same.

We have ambiguity: which ID number are we trying to represent?

A collision is where two or more values both "hash" to the same bucket.

Closed Hash Table with Linear Probing

To deal with collisions, this is one possibility.

We figure out a target bucket via that hash function.

If the target buck is empty, we store our value there, but we store the full original value, not the hash.

This prevents ambiguity. If the bucket is occupied, we scan down until we find the first empty bucket. Put the value there.

Here, insertion and searching is O(N) in the worst case, where the table is almost filled-up, and there are many collisions.

To create a hash table, we must consider the size of our intended dataset.

To search, we compute our bucket number with our hash function, and we probe linearly downward until we find our value or hit an empty bucket; the latter case means that the value is not in the hash table. This will wrap around (thanks to modulo) to try to insert in the earlier buckets too, if possible.

In general, this approach addresses collision by putting each value as close as possible to its intended bucket. We have locality.

And, since we store the original value, there is no ambiguity.

The hash table is called "closed" because it has a fixed-size. Example: a night-club has a limited capacity. Once we run out of empty buckets, we cannot add new values. We'd have to create a new hash table and copy over the old values by re-hashing (to accommodate the new size of the larger hash table).

In code:

struct Bucket
{
    int idNum; // The value we store
    bool used; // Is the bucket empty? 
               // Initialize this to TRUE
}; 

We could also choose to terminate search or insertion operations after a certain number of tries if we know that our hash table couldn't be that bad.

What about searching and collisions? We stored the full, original value! We search linearly, and in the worst case, check all N buckets to see if our value is present, wrapping around to the beginning as needed.

Note that recursion is pretty much never used with hash tables. Do it iteratively.

The cool thing about hash tables? We can store whatever the hell we want in them. We could have a comprehensive database, which we can search by a particular field, the one that was hashed to buckets.

We search by the hashed field, and can then grab the other fields' data.

Deletion

What happens if we just zero-out a particular position?

Our search algorithm will stop prematurely (when we're looking for a value that has collided with another and and have put the collisions in later buckets) because we hit an empty bucket.

The moral: Use closed hash tables where we never need to delete anything. We are limited by the fact that we need to account for the hashing. We'd end up with all sorts of special cases and extra complexity.

Examples: dictionary, a list of the dead (no zombies!)

If we delete where a collision, we may prematurely abort a search, failing to find the sought-for value.

Open Hash Table

Now let's see another way to deal with collisions, one that avoids a closed hash table's problems with deletion and size capping.

Now, our buckets will point to a linked list of values.

To insert:

  1. Compute a bucket number with our hash function

  2. Add the new value to the linked list at array[bucket]

  3. Done!

Now, it's constant time to get to a bucket, but to traverse the linked list, it's O(L).

There is no a priori size limit to the open hash table. It'll slow down with too many items and collisions though.

To search:

  1. Compute bucket # with hash function

  2. Search the linked list at array[bucket]

  3. If we hit the end of the linked list, the item is not in our table!

To delete:

  1. Go to the right bucket using the hash function
  2. Remove the node from the linked list

Note that closed hash tables are faster for when we know our maximum size, and we avoid the dynamic allocation, deallocation of open hash tables.

If we need to delete, we must use a open hash table.

If we size the hash table large enough, then we avoid multiple collisions, and our average Big-O will be ~O(1) in practice. O(1) on our test.

In the worst-case (everything is a collision), then it's O(N).

We could of course store the items in a BST or BBST instead for even faster operation. That adds complexity though.

Or: a hash table within a hash table!

Hash Table Efficiency

Efficiency depends on

A. Type of hash table B. How full the hash table is C. How many collisions are in the hash table

If we have a completely or nearly empty hash table: O(1) for everything. (Go to right bucket, insert/search)

We avoid linear probing (closed) or linear traversal (open).

BUT, if our hash table is nearly full: it may now be O(N) for insertion and searching.

So our trade-off is between hash table size and efficiency.

The load of a hash table is the max number of intended values divided by the number of buckets to be available.

This is almost always < 1.

L = max/buckets.

Example: 0.1 = our hash table has 10 more buckets than needed (we avoid collisions)

To compute the average number of tries needed to insert/find an item for a closed table with linear probing:

1/2(1 + 1/(1 - L)) for L < 1.0

For an open hash table:

1 + L/2 for L < 1.0

There's not too big a difference between the two (they'll be around ~O(1)).

We would obviously try to avoid loading up the hash table too heavily.

Remember: dynamic size with deletion too? Open hash table.

Lecture 18: 10 March 2014

// Definitely beat the number of lines of notes for CS 31

Focus for final will be on material that was new or not covered on the past two midterms. It will be more analytical.

Review of hash tables load factor. Note that hash tables are best for when we know how many items we'll need to handle, max. If we do not know, then some other data structure would do better.

Why would we use a closed hash table rather than an open hash table? Because allocation is slow in comparison to the fast, constant-time insertion into a closed hash table.

Also, hash tables are terrible for traversing something in order, e.g. the names we manage in our Database for Project 4.

For searching, however, the totally beat everything.

Sizing a Hashtable

To size a hashtable appropriately:

  1. Determine the max number of items
  2. Determine the average number of searches we want to find an item in this hash table type (closed or open)
  3. Solve for the load factor
  4. Load factor is max/buckets; solve for number of buckets

We're working backward to get the number of buckets.

We're looking for an effective trade-off between memory usage and fast searches. It all depends on our constraints.

Always try to choose a prime number of items. This allows for a more even distribution and fewer collisions. It'll divide evenly into fewer numbers.

Example: 2,021 instead of 2,000

Hashing Non-Numbers

What if we want to hash a string?

We need a hash() function that will give us numbers.

Example:

int hash(string& name)
{
    string name; 

    for (int i = 0; i < name.length(); i++)
        total = total + name[i];

    total = total % HASH_TABLE_SIZE;

    return total;
}

But this just adds up the encoding values for the letters, and so this produces the same result for different strings, e.g. BAT and TAB.

Those are different strings, and we should get different hashes for them, but this hash function doesn't do that, so this means we will have a lot of collisions.

Alternatives:

total = total + (i+1) * name[i];

Note that this could cause overflow problems where the string.size() * blah > INT_MAX.

There will always be collisions, no matter what our hashing scheme is. Hash tables just have to deal with that reality. This one does eliminate the problem with anagrams hashing to the same value though.

  1. A hash function must always give the same bucket number for a given input value.

We do NOT want random hashes!

  1. The hash function should disperse items throughout the hash array as randomly as possible.

  2. When coming up with a new hash function, always measure how well it disperses items (do experiments).

Create a graph of the number of items per bucket number.

x
x x x x x
1 2 3 4 5 

vs.

Try CRC32, CRC64, SHA2, etc., but MD5, etc. are not secure enough cryptographically. These are open-source hashing functions.

Note that we still have add our own modulo based on our table size.

Hash Table vs. BSTs

Speed: O(1) vs. O(log2(N))

Simplicity: Simple vs. complex

Max size: Limited (closed HT), or high load impedes performance

vs. the consistency of BSTs under high load, especially if balanced.

If we want to exapnd a hash table, it's like creating a whole new hash table, though there are incremental expansion schemes.

Space efficiency: HTs can waste space; BSTs use only as much space as needed

Ordering: HTs are random; BSTs are inherently ordered

Just searching: HT Traversing or order required in some way: BST

What is the cost of sorting items? Nlog2(N), even with our fastest sorting algorithms.

To get items in order with a HT, we'd have to sort fast.

What if we're mostly searching rather than doing stuff in order? This favors using a hash table. Conversely, if order is of greater importance, use a BST. It all depends on the use case.

Tables

Say we want to keep tracks of all our friends and info on them.

A group of related data is called a record or a row of data.

Each record has a number of fields like name, age, etc.

A collection of records is called a table.

We may have many records that share some fields, but a field with a unique value for every record is called a key field.

Have a struct/class represent a record, then have a collection of them be our table (e.g. vector, array, etc.)

// 10,000 lines!

In our Project, we don't happen to have a key field.

A table is an ADT onto itself. It is designed to hold records conforming to a particular schema that specifies the format of records and their fields.

To search a table by a particular field, we could do simple linear search, but this is O(N).

Instead, we could sort and do a binary search. That'd be O(log2(N)). This is a problem for insertion, of course, as we have to re-sort every time we insert. That's an overheard of a O(Nlog2(N)).

This would also lock in our searching abilities. If everything is ordered by name, how would we search by name or phone number? Searching by one field would be O(log2(N)), but everything else would be linear, O(N).

What about storing our records in a binary search tree? This avoids re-sorting, but we still are limited to efficient search by one particular field.

We could create separate BSTs, one organized by one field, one organized by another field, but this is duplicating data, wasting space.

Intead, we'll still use a vector to store all our records.

Then, we'll have a secondary data structure that associates a field with their slot number in the vector.

This secondary structure lets quickly look up a name, and find out where that person and all the associated data are in the records structure. BST-based Maps or MultiMaps are perfect for associating indexed fields to their slot numbers.

These secondary data structures are called indices (sing. index), which use B-Trees and let us know where data is stored.

However, note that we are still duplicating some data, the indexed fields.

Once we know the slot number, a -like structure is perfect for constant-time access to the particular item.

Why do we use slot numbers and not pointers to items? We can't fit everything in memory (databases are typically massive).

What happens if we have to delete a record? Updating all the indices and such would be a pain. Instead, we could put a tombstone marker in the place of deleted item, to let us know that the record is available.


// PROJECT 4 NOTES:

For findEqualSuccessor, check current, then check the one before it, for predecessor then check current, and then check one after it.

1, 2, [2.5] 3, 4, 5 P S

Do this iteratively!


STORY TIME

There was a computer program called Wisdom, that would randomly generate paragraphs, footnotes, etc., and it could generate a grammatically-correct paper. So Carey generated the conclusion to his physics paper using this. Recently, some guys have generated random research papers and showing how this nonsense was getting accepted at conferences. This illustrates the lameness of academia.


We have as many indexes as we need for our particular table.

Note that a can use the brackets [] operator.

m_IDtoSlot[student.number] = slot;

To insert:

Add the record to the records data structure. Update the index data structures as needed for each of our indexed fields.

Hash-Based Indices

Of course, we could use hash tables to search fields and associated hash numbers.

Modern databases use either one, depending on whether order matters.

Understand how our table will be used, which will let us decide how to index each field. If we do later need to output stuff in order, we can always just run a sort.

and

This is a hash-based version of a , a "hash-map" (older name). There's a hash-based as well, a "hash-set".

We can use this for our project!

This is inserting items into a hash table, but each item has data associated with it (or two data, as with an ). This allows constant-time operations with everything. Again, decide if we need to output stuff in order.

These will resize automatically and they allow deletion as well, suggesting they use a open hash table.

They're "unordered" because HTs are unordered.

Priority Queue

In a regular queue, FIFO, first-come, first-served.

Instead, each item in a PQ has a priority rating. We always dequeue the item with the highest rating.

They support a new item, get the value if the highest priority item, remove the highest priority item.

We need to sepcify how to determine the priority of each item in the queue. e.g. Doctor determining which injured person to treat first.

We could do this with a BBST, but what if we a had a limited set of priorities (high, medium, low)?

What's a basic data structure to handle this?

Three linked lists: one for each priority rating. Think of seating classes for First Class, Business, Coach for airplanes.

But what if we have a large number of priorities?

Heaps

This is not the heap, as in the memory location.

Instead, a heap uses a complete binary tree, useful for priority queues, in which (assuming N depth):

  • The top N - 1 levels of the tree are completely filled with nodes.

  • The bottom-most node are as far left as possible, with no empty slots between nodes

These are NOT BSTs!

There are two types of heaps: minheaps and maxheaps.

Maxheap:

  1. Quickly insert a new item (Olog2(N))
  2. Quickly retrieve the largest item from the heap

Minheap:

  1. Quickly insert a new item
  2. Quickly retrieve the smallest item from the heap

Maxheap

Maxheap BT follows these rules:

  1. The value contained by a node is always >= values of its children
  2. The tree is a COMPLETE binary tree.

Minheap would reverse the 1st rule to <=.

This is not a BST, so only the immediate node family matters.

Note how the biggest value is guaranteed to be at the top of the tree.

So peeking at the top value is O(1).

Extracting the Biggest Item
  1. If the tree is empty, return ERROR

  2. Otherwise, the top item in the tree is the biggest value Remember it for later

  3. If the heap has only one node, then delete it and return the saved value

  4. Otherwise, copy the value from the right-most node in the bottom-most row to the node

  5. Delete the right-most node in the bottom-most level (Choosing this node keeps things left-justified, to avoid creating gaps).

  6. Repeatedly swap the just-moved value with the larger of its two children until its value is greater than or equal to both of its children (sifting down).

    If it's already >=, then we never move it. In the end, the second-biggest item from before is now the biggest item, and has been moved to the top, maintaining the validity of the maxheap. This lets us handle any number of priorities, where the maxheap inserts based on priority rating.

  7. Return the value from earlier to the caller

This will be on our final exam. Make it easy by drawing diagrams.

Adding a Node to the Maxheap
  1. If the tree is empty, create a new root node and return

  2. Otherwise, insert the new node in the bottom-most left-most position (to maintain left justification for completeness)

  3. Compare the new value with its parent valye

  4. If the new value is greater than the parent's value, then swap them

  5. Repeat steps 3-4 until the new value rises to its proper place, which might be the root node (meaning it was bigger than the original largest value)>

Reheapification is the name for this process.

Big-O is log2(N) for insertion/removal.

Array-Based Implementation

We never actually use a BST with pointers for heaps. It's hard to locate the appropriate locations.

Instead, we'll use an array.

We know that each level of our tree has 2x (twice) the number of the nodes of the previous level.

We can think of translating a complete binary tree (CBT) over to an array, one level at a time.

If we just have our nodes, one level at a time, in an array, we know where each level starts. This how the memory heap works. What about sizing the heap? Either know the size ahead of time, or use a or something else that can resize dyanmically.

We use a simple int variable to track how many items are in our heap. What about finding the children and parent?

  1. We can always find the root value in heap[0]

  2. The bottom-most, right-most node in heap[count - 1]

  3. We can always find the bottom-most, left-most empty spot (to add a new value) in heap[count]

  4. We can add/remove a node by simply setting heap[count] = value and/or updating the count.

This is better than a sorted array that we resort at each insertion. That'd be be O(Nlog2(N)), vs. this, which is O(log2(N)).

To locate a node's children:

(given the slot number of the parent)

left child(parent) = 2 * parent + 1 right child(parant) = 2 * parent + 2

2i + 1, 2i + 2 are the simple, easy formulas, where i is the slot number of the parent

// This can be derived from manually listing // the translations

To find the parent node:

parentSlot(childSlot) = (childSlot - 1 ) / 2

(i - 1) / 2 works because of integer division.

Reheapification is done immediately upon insertion, which we do by comparing to the parent (which we find via these formulas).

Summary:

  • Root node at heap[0]
  • Bottom-right at heap[count - 1]
  • Botom-left at heap[count]

This is all we need to build a heap.

Recommendation: Use a tree, then copy over the values from the tree back into the array, to make things easier.

"This is not a heap. This is a heap helper. This is not a hamburger, this is a Hamburger Helper."

Extraction with an array-based Heap
  1. If the count == 0, return ERROR

  2. Otherwise, heap[0] holds biggest value

  3. IF count == 1, set count = 0, return the saved node

  4. Otherwise, copy the value from the rightmost, bottom-most node into the root node heap[0] = heap[count - 1]

  5. Delete the right-most node in the bottom-most by decrementing our count

  6. Compare our newly-copied value to its two children heap[i] vs heap[2 * i + 1] and heap[2 * i + 2]

  7. Swap if necessary, till we're done or hit the root node

Lecture 19: 12 March 2014

Last Day of Class

// The last CS 32 lecture! D: // I’m so sad; this class was amazing!

[REDACTED 12-24-2015: I don't want to spoil the fun of the last lecture!]

Adding Node to an Array-based Maxheap

  1. Insert a new node in the bottom-most, left-most open slot: heap[count] = value count = count + 1

  2. Compre the value with its parent value. Swap if out of o

  3. If the new value is greater than parent, swap

  4. Repeat

Class challenge. "Do I get a prize ticket?" "I don't think they're useful anymore."

Big-O of Heap Insertion

We need to comparing, and we need to check up the ancestors, so O(log2(N)) for insertion.

Extraction: O(log2(N))

Since we need to compare and swap.

Heapsort

Heapsort is guaranteed to at least Nlog2(N)), the naïve one that uses a separate heap.

The real heapsort doesn't use a separate array. That naïve implemenation had a lot of overhead.

Instead, we can do everything within the array.

This semi-official is not quite as efficient as the fully official one, then we'll see the altter.

  1. Convert our input array into a maxheap (shuffle around)
  2. While are numbers left in the array A. Remove the biggest value from the heap b. Place it in the last open slot of the array

To cleverly shuffle around the values:

Start by visualizing our array as a tree. Note, this algo operates on the array itself.

for (curNode = lastNode through rootNode) [rightmost, bottommost,
                                           last item in array]
{
    Focus on subtree at curNode

    Think of this subtree as a maxheap

    Keep shifting the top value down until your subtree
    becomes a valid maxheap [use heapification algo
    where we swap with the larger child until the current
    is larger than both of its children] 

    // Move to next Node
}

Start at the bottom, keep heapfiying from bottom to top. Check that the maxheap tree is correct.

We've heapified higher and higher subtrees, relying on the lower subtrees.

Note that we wasted a lot of time looking at single-node subtrees.

We only need to re-heapify when we reached a subtree with at least two nodes. To jump to that:

startNode = N/2 - 1; // Lowest one down, right-most with 2 children

for (curNode = startNode thru rootNode)

Jump to that slot in the array, and corrolate with the tree nodes.

Note that at least half of a complete binary tree has no children, because of the bottom row. With this, we skip 50% of the reheapification, (N/2 items), so this lets us increase efficiency.

While there are numbers left in the heap:

  1. Extract the biggest value from the maxheap and re-heapify This frees up the last slot in the array, and the heap now occupies only the first N - 1 slots.

  2. Put the extracted value into this freed-up slot of the array.

Next time, we'll extract, leaving the second-to-last slot free.

Decrement the count as part of the extraction; this is how we know when we're done.

Minheap would give a descending order.

Extraction, reheapification, insertion -> in order!

Converting an array into a maxheap is O(N) because of how we skip 50% of the nodes.

"I found it on Wikipedia so it must be true."

Extraction and reheapifying is O(log2(N))

So O(N + Nlog2(N)) --> O(Nlog2(N))

Introduction to Graphs

A graph is an ADT that stores a set of entities and keeps track of the relationships between all of them.

Examples: People and relationships, cities and distances.

It might not just be a connection, but a value associated with that connections. The edge has a value.

Web pages and links between them (Google Page Rank).

Vertices (nodes) are the people, city, web pages, etc.

Edges (arcs) connect two vertices to each other.

Edges typically connect two vertices, but self-connections are also possible, e.g. a bus on a looping route.

There are directed graphs where each edge goes from one vertex to another in a specific direction. It goesn't go both ways, e.g. one-way flight. A-->B

THere are undirected graph, where all edges are bi-directional, where we can go either away along each edge. A--B

Adjacency Matrix

Use a double-dimensional array with the size of both dimensions equal to the number of vertices.

Each element indicates whether or not there is an edge between vertex i and vertex j.

e.g. bool graph [5][5]; graph[0][3] = true;

This would be a directed graph. Unless, [0][3] and [3][0] are marked true. [0][0] would indicate a self-connection.

This could be changed to values, and even have different values depending on which way we go. These are directed edges.

This is called an adjacency matrix.

A BST is a form of a directed graph: we can only go to the children, and is a directed acylic graph (DAG).

To represent an undirected graph, just bi-directionally connect: [i][j] == [j][i]

An interesting property around them:

If we multiply the matrix by itself: All the people are now identified as 2 connnections away from someone away. The first one marked those 1 away. Do it again, and we get 3 away.

"Why does that work?" "I have no idea."

I'll double-check the matrix math after I take 33A.

Facebook and other social networks do not use this technique; this would involve very large arrays. This was referenced in the first lecture!

"In some cases, one friend."

Adjacency List

We can use an array of linked lists or a vector of linked lists to represent a graph.

If we add a number j to list i, there is an edge from vertex i to vertex j.

// 0-->3
graph[0].push_back(3); 

Each list lets us know the connections.

List vs. Matrix

Scenario #1: 10 million users where most people have a few hundred people. Instead of a 10x10 million array, use an adjacency list instead.

This is called a sparse graph, where there are only a few connections from one part to another part.

Scenario #2: 1,000 cities with airlines from city to almost every other city. Use an adjacency matrix.

Low node connectivity (many items) --> use an adjacency list

High node connectivity (few items) --> use an adjacency matrix

Consider the specific use case. It would be faster to search an adjacency matrix.

We could have an array of hash tables or an array of sets, etc.

Use an adjacency matrix where there are lots of edges between few vertices (dense graph). The number of cells grows O(N^2).

Use an adjacency list for where there are few edges and lots of vertices (>10,000), e.g. Facebook.

Individual vertices are connected to few other vertices.

High school dating habits: "We would call those man-whores or sluts."

Graph Traversals

A tree is a kind of graph.

Depth-first and breadth-first traversals.

Depth-first is like a pre-order traversal. Use recursion!

Breadth-first is like a level-order traversal. Use a queue!

Depth-first keeps moving till it hits a dead end or a previous-ly visited vertex, then it backtracks and tries another path. (Check if previously-visited; no bread crumbs used)

Use a stack or recursion.

Breadth-first keeps exploring in growing concentric circles, exploring all vertices 1 away, 2 away, etc.

This is like tree traversal and like our maze exploration.

Depth-first Traversals

If already visited
    RETURN 

Mark current as visited
Process

For each edge leaving current
Determine vertex the edge takes us to (direction depends on use case, maybe)
Call depth-first traversal on that vertex

Real algo doesn't visit already-visited vertices

Breadth-first Traversals

Process current, then 1 away, then 2 away, then 3 away. Go out via the mutual friends. This can be done with a queue.

Add start vertex
mark as discovered

While queue not empty

And that's it! Loud applause! :D