CS 70

Concept Map

Looking for the place where the course talks about something? Each concept below links to the sections of the lessons, homework and help pages where it comes up, starting with where it's introduced. Places that haven't been released yet are shown in grey, with the date they open.

Type in the box to narrow the list. It knows some of the other names people use for things, too (try "UB", "segfault" or "copy and swap"), and the links between concepts point at what each one builds on and what it's easily confused with.

Not here? Search the full text with DuckDuckGo.

The course

late passes

A partnership has one 24-hour homework extension, and each student has three for first-try proficiency checks.

Also: late work, extensions

Introduced: Late Work Syllabus

Lessons

  • Scenario Five (extensions for illness: ask early) Thinking About Pair Programming · Lesson 1

Policies

↔ See also schedule and deadlines, submitting your homework

proficiency checks

A group of four exam-style checks beside each homework: closed-book, in one sitting, graded demonstrated or not, with second and final tries.

Also: PCs

Introduced: Proficiency Checks Syllabus

Lessons

Policies

  • Grading (grading, retries and final tries) Syllabus
  • Late Work (late passes for first-try checks) Syllabus

↔ See also course grade and grade scale, schedule and deadlines

academic honesty

The Honor Code in CS 70: no copied code, cite every source, respect the assignment's intent, and write your own.

Also: academic integrity, collaboration

Introduced: Pair Programming: Our Expectations (six scenarios: encouraged to forbidden) Thinking About Pair Programming · Lesson 1

Lessons

  • Scenario One (searching the web for error messages) Thinking About Pair Programming · Lesson 1
  • Scenario Three (intent of the assignment: concepts vs. implementations) Thinking About Pair Programming · Lesson 1

Homework

Policies

↔ See also getting help, AI usage policy

getting help

Ask early and well: in lab, at grutoring or office hours, or on the page; show what you tried, and push first.

Also: grutoring, office hours, Piazza

Introduced: Getting Help Welcome! · Lesson 1

Lessons

  • Scenario Six (public vs. private questions) Thinking About Pair Programming · Lesson 1

Homework

Policies

Help Pages

Debugging Lab Activity

First Day with CS 70

↔ See also academic honesty

pair programming

One joint solution on one machine: the driver types, the navigator steers, and you swap about every 30 minutes.

Introduced: Reflecting on Pair Programming (benefits, costs, being a good partner) Thinking About Pair Programming · Lesson 1

Lessons

  • Scenario Two (driver and navigator; splitting the work is forbidden) Thinking About Pair Programming · Lesson 1

Homework

Policies

Pair-Programming Availability

Exploring the Terminal

CS 70 Animal Friends

The talking animals (Pig, Duck, Hedgehog and friends) pop up in asides to ask what a student would ask and to add side explanations.

Also: Duck, Goat, Rabbit…

Introduced: The CS 70 “Animal Friends” Welcome! · Lesson 1

Policies

how the course works

A flipped class: online lessons first, then lab, office hours and grutoring; lesson questions need real effort, not correctness.

Also: flipped class, weekly page, lesson questions, lab check-in, class meetings

Introduced: How Will This Course Go? (flipped class) Welcome! · Lesson 1

Lessons

Policies

grading rubric

What graders look at beyond correctness: clarity, elegance, style, completeness, correctness, at four levels from Excellent to Missing.

Also: how homework is graded

Introduced: Grading Guidelines

Homework

Help Pages

↔ See also course grade and grade scale

AI usage policy

Treat AI like a friend who took the class: fine for concepts and error messages, never for writing your code.

Also: LLMs, ChatGPT, Copilot, Claude, AI code completion, using AI, LLM

Introduced: AI Usage Policy Syllabus

Homework

Policies

↔ See also academic honesty

course grade and grade scale

48% assignments, 44% proficiency checks, 8% engagement; grades are truncated, and under 50% in a category can lower yours.

Also: final grade, grade breakdown, 48/44/8, truncated, letter grades, 50% rule

Introduced: Course Grade Syllabus

↔ See also grading rubric, proficiency checks

schedule and deadlines

Every homework and proficiency check with its release, due and late-due dates; homework is due Thursdays at 11:59 p.m.

Also: due dates, due times, 11:59 p.m., release dates, when is X due

Introduced: Assignments (homework cadence) Syllabus

↔ See also late passes, proficiency checks

accommodations

Contact your home college's accessibility office; we will work with them so you have what you need.

Also: disability, accessibility, accessible education

Introduced: Accommodations Syllabus

health policies

Masking is optional unless you are sick or exposed; if you are ill, stay home and pair remotely.

Also: masks, COVID, illness, sick, remote pairing, COVID-19

Introduced: CS 70 COVID-19 and other Health Policies Health Policies

Policies

textbooks

None required; Code Complete, C++ Primer and Sedgewick's Algorithms in C++ are useful references.

Also: required readings, books, Code Complete, C++ Primer, Sedgewick

Introduced: Textbooks Syllabus

free swim

An optional, open-ended part of an assignment, done for the joy of making something, with a few bonus points.

Also: optional part, bonus points, extra credit, extension ideas, more fun

Introduced: Free Swim HW 1

submitting your homework

Pushing isn't submitting: run submit-this on the server and paste the submission code it prints; no confirmation message means you haven't submitted.

Also: submit-this, submission code, how to submit, Gradescope, uncommitted changes, did my submission go through

Introduced: What Counts as Submitting Submitting Your Assignment · HW 0, Episode 2

Homework

↔ See also git and GitHub, late passes

Numeric types and memory models

memory diagrams

Pictures we draw to trace what's in memory as code runs; only the value goes inside the box.

Also: drawing memory, boxes

Introduced: How? Memory Diagrams in CS 70 · Lesson 1

Lessons

Homework

Help Pages

Memory Diagram Practice

Arrays

More Memory Diagrams

  • Activity More Memory Diagrams · Lab Activities

→ Leads to the stack

the stack

Where local variables live: one slot per local, a labeled frame per function call, filled from the top and growing down.

Also: stack frame, stack slot, call stack, local variables, stack vs heap

Introduced: Modeling Memory in CS 70 Modeling Memory · Lesson 1

Lessons

Homework

Help Pages

Memory Diagram Practice

← Builds on memory diagrams⇄ Contrast with the heap and new→ Leads to reading a backtrace↔ See also iterators, depth-first and breadth-first search

von Neumann architecture

The CPU, registers and memory design most computers follow; CS 70's model keeps the stack and drops the registers.

Introduced: Modeling Memory in CS 5: Von Neumann Architecture Modeling Memory · Lesson 1

variables (name, type, value, location)

Every variable has a name, a type, a value and a location; in C++ the type is fixed when you declare it.

Also: variable declaration, static typing, dynamic typing, explicit type, implicit type

Introduced: Python and C++ Similarities (name, type, value, location) Variables in Python & C++ · Lesson 1

Lessons

Homework

  • The Memory Model (only the value is in memory) Written Questions · HW 0, Episode 2

C++'s guiding principles

Zero Overhead (don't slow programs down needlessly) and Power to the People (trust the programmer) explain much of C++'s behavior.

Also: Zero-Overhead Principle, Power to the People, why C++ doesn't check, design goals of C++

Introduced: The Zero-Overhead Principle (Zero-Overhead) C++ Guiding Principles · Lesson 1

Lessons

↔ See also iterator validity

object lifetime

Every object, whatever its type, passes through allocation, initialization, use, destruction and deallocation, in that order.

Also: five stages, allocation/initialization/use/destruction/deallocation

Introduced: The Five Stages of an Object's Life Lesson 2

Lessons

Help Pages

→ Leads to scope and declaring blocks, returning values

scope and declaring blocks

A name is usable from its initialization to the closing brace of its declaring block; after that the object is destroyed.

Also: in scope, out of scope, declaring block, block scope, can't use variable after loop

Introduced: Declaring Blocks Loops and Conditionals with Object Lifetime · Lesson 2

Lessons

Homework

  • Name-Clash Alert! (a local variable named log hides the library function) Phase 7 · HW 7

Help Pages

← Builds on object lifetime

indeterminate values

An uninitialized built-in variable holds whatever was there, which can differ between machines and runs; reading it is undefined behavior.

Also: uninitialized variable, garbage value, junk value

Introduced: Differences Related to Variable Values Variables in Python & C++ · Lesson 1

Lessons

Homework

← Builds on undefined behavior⇄ Contrast with initialization

numeric types

C++ has several integer and floating-point types, differing in how many bits they use and what those bits mean.

Also: int sizes, long, short

Introduced: Number Types in C++ Numeric Types—Fundamentals · Lesson 2

Homework

First Day with CS 70

  • An Experiment (double vs. int) First Day with CS 70 · Lab Activities

→ Leads to platform data models (LP64, LLP64), size_t and fixed-width integer types, integer division, bit manipulation

platform data models (LP64, LLP64)

Sizes of int and long vary by platform (LP64 on Mac/Linux, LLP64 on Windows); the standard promises only minimums.

Also: LP64, LLP64, ILP32, sizeof, int size differs on Windows, memory model

Introduced: Fundamental Integer Types in C and C++ Numeric Types—Fundamentals · Lesson 2

Homework

  • Types and Representations (sizes on the server) Written Questions · HW 0, Episode 2
  • Questions (Node is 12 bytes of data, 16 with padding) Empirical Exploration · Written Questions

← Builds on numeric types

signed vs. unsigned

Unsigned types use every bit pattern for non-negative values; signed types give half to negatives. Mixing them surprises people.

Also: unsigned overflow, size_t

Introduced: Signed and Unsigned Integers Numeric Types—Fundamentals · Lesson 2

Lessons

Homework

Help Pages

⇄ Contrast with size_t and fixed-width integer types

size_t and fixed-width integer types

size_t holds counts and indexes, ptrdiff_t offsets, and intN_t/uintN_t have exactly N bits; all are names for built-in types.

Also: size_t, ptrdiff_t, int32_t, uint8_t, cstdint, cstddef

Introduced: Other Integer Types Numeric Types—Fundamentals · Lesson 2

Homework

Help Pages

← Builds on numeric types⇄ Contrast with signed vs. unsigned

floating point

Fractional numbers stored like scientific notation, with bits for a significand and an exponent; approximate, not exact.

Also: double, float

Introduced: Floating-Point Numbers Numeric Types—Fundamentals · Lesson 2

Lessons

Homework

Help Pages

integer division

Dividing two integers gives an integer, dropping the fraction; make one operand a double before dividing if you want decimals.

Also: truncating division, int / int, why is 5/2 equal to 2

Introduced: When Everything is the Same Type Promotion and Conversion · Lesson 2

Lessons

Homework

First Day with CS 70

  • An Experiment (hdist and vdist as int) First Day with CS 70 · Lab Activities

← Builds on numeric types⇄ Contrast with conversion

promotion

Automatic widening to a bigger type of the same kind whose range covers the original, so nothing is ever lost.

Also: integer promotion

Introduced: Promotion: _Different Sizes_ of the Same Type Promotion and Conversion · Lesson 2

Homework

⇄ Contrast with conversion

conversion

Any move between numeric types that isn't a promotion; C++ does it automatically, and it can lose information.

Also: implicit conversion, narrowing

Introduced: Conversion: Changing Between Types Promotion and Conversion · Lesson 2

Lessons

Homework

Help Pages

Memory Diagram Practice

⇄ Contrast with integer division, promotion, user-defined conversion→ Leads to safe conversions, casts

safe conversions

Convert on purpose: to_int(x), to_uint16_t(x) and friends check that the value fits and throw std::overflow_error if it doesn't.

Also: narrowing_cast, static_cast, -Wconversion

Introduced: The CS 70 Narrowing-Cast Library Safe Conversions

Homework

  • Two-Key Steering (to_int16_t before brace-initializing a Coord) Your Turn · HW 5

Help Pages

← Builds on conversion⇄ Contrast with undefined behavior↔ See also casts

undefined behavior

Break a rule and C++ promises nothing: a crash, wrong answers, or working fine today and failing tomorrow.

Also: UB, UBSan

Introduced: The Zero-Overhead Principle C++ Guiding Principles · Lesson 1

Lessons

Homework

Help Pages

Arrays

⇄ Contrast with safe conversions→ Leads to indeterminate values, sanitizers↔ See also compile time vs. run time, exceptions, iterator validity

choosing numeric types

Keep it simple: int by default, char for characters, size_t for counts and indexes, double for real numbers; prefer signed.

Introduced: Which Type to Use Practical Advice for Numeric Types · Lesson 2

casts

static_cast, dynamic_cast, const_cast, reinterpret_cast; the C-style (int)x guesses among them, so never use it.

Also: static_cast, C-style cast, (int)x, const_cast, reinterpret_cast, explicit conversion

Introduced: 1.6 Do not use C/Java-style casts Coding Idioms

Help Pages

← Builds on conversion↔ See also safe conversions

bit manipulation

Work on single bits of an integer with &, |, ^, ~ and the shifts << and >>.

Also: bitwise operators, &, |, ^, <<, >>

Introduced: 2. Bit Manipulation Font Fun: A Code Reading Exercise · HW 1

← Builds on numeric types

Arrays

arrays

Our first data structure: fixed-size, contiguous, homogeneous, ordered storage, and the building block under fancier ones like std::vector.

Also: primitive arrays, C arrays, std::array

Introduced: Arrays, Our First Data Structure! (vs. Java arrays and Python lists) Lesson 2

Lessons

Homework

Arrays

→ Leads to array decay, out-of-bounds access, C strings and string literals

array properties

Contiguous, ordered, homogeneous, fixed-size (Cats Often Hide Fish): which is why the machine can find any element fast.

Also: contiguous, homogeneous, fixed-size

Introduced: Fundamental Properties of (Primitive) Arrays Arrays, Our First Data Structure! · Lesson 2

Lessons

Homework

constexpr

Promises the compiler a value is known at compile time and never changes, so it can size an array.

Introduced: Allocation for Arrays of Primitives (array sizes must be compile-time constants) Declaring Arrays in C++ · Lesson 2

Lessons

Homework

⇄ Contrast with the const qualifier↔ See also compile time vs. run time, magic numbers

indexing and pointer arithmetic

a + i is the address i items along from a, and a[i] is the compiler's shorthand for *(a + i).

Also: arr[i], *(arr + i)

Introduced: Accessing Other Items (address plus offset) Accessing Array Elements · Lesson 2

Lessons

Help Pages

Arrays

array decay

On its own, an array's name stands for its first element's address, and unlike other variables it can't be reassigned.

Also: array to pointer decay, array name is a pointer, decays to a pointer

Introduced: The Value of an Array Variable Accessing Array Elements · Lesson 2

Lessons

Arrays

← Builds on arrays⇄ Contrast with pointers

out-of-bounds access

An index outside the array is undefined behavior: C++ doesn't check, so you read or scribble on whatever lives there.

Also: buffer overrun

Introduced: Breaking Array-Access Rules Out-of-Bounds Access · Lesson 2

Lessons

Homework

Help Pages

Arrays

← Builds on arrays

segmentation fault

The operating system shuts down a program that touches memory outside its own region; suspect a bad index or a bad pointer.

Also: segfault, crash

Introduced: Segmentation Faults Out-of-Bounds Access · Lesson 2

Lessons

Homework

  • Question 6 Written Part · HW 3
  • Helpful Hints (a common symptom of pointer bugs) Implementing IntList (#1) · HW 5

Help Pages

style and elegance

Code is for human readers: similar things look similar, different things look different, following the CS 70 style guide.

Also: naming, whitespace, idioms

Introduced: Use (In)Consistency to Your Advantage Style and Elegance · Lesson 2

Lessons

Homework

Help Pages

→ Leads to cpplint, clang-format, commenting, magic numbers

++i vs. i++

++i increments and hands back the new value; i++ stashes the old one first. Use ++i: C++ readers expect it.

Also: prefix increment, postfix increment, pre-increment, post-increment

Introduced: Consistency: Applying Idioms Style and Elegance · Lesson 2

Homework

Help Pages

testing

Tests exist to uncover bugs, not to show the code works; you can't test everything, so think about edge cases.

Also: writing tests, test cases, TDD

Introduced: Program Bugs Can Have Very Serious Consequences (why testing matters (Therac-25)) Program Correctness Matters · Lesson 2

Lessons

Homework

Help Pages

→ Leads to the CS 70 testing library, the development process↔ See also stubs, invariants

commenting

Interface comments (\brief, \param, \returns) in the .hpp say what; implementation comments in the .cpp say why. No TODOs left.

Also: comments, doxygen, \brief, \param, \returns, TODO comments

Introduced: Commenting

Homework

  • Your Task, Part 2 (docstring comments on every declaration) An Interface for an Int Queue · HW 5

Help Pages

← Builds on style and elegance

magic numbers

Give a literal value a named constant instead of repeating it: the name explains it and one edit changes it.

Also: named constants, magic constants, magic strings, literals

Introduced: 1.3 Avoid magic numbers Coding Idioms

Help Pages

← Builds on style and elegance↔ See also constexpr

the conditional (ternary) operator ?:

cond ? a : b is an expression giving a when cond is true and b otherwise.

Also: ternary operator, x ? a : b, conditional expression

Introduced: Update Constructor and pushBack (a computed capacity_ in the list) Dynamic CoordVector · HW 4

Homework

Compilation

compilation stages

Source code goes through four stages, each with its own output: preprocess, compile, assemble, link.

Also: preprocess, compile, assemble, link

Introduced: What is Compilation? (what compilation is; compiled vs. interpreted) Lesson 1

Lessons

Homework

Help Pages

→ Leads to the preprocessor (directives and macros), compile time vs. run time

compiling vs. linking

Compiling turns each .cpp into a .o file; linking gathers the .o files and libraries into one executable.

Also: object files, linker errors, undefined reference

Introduced: Linking Stage: Object File(s) → Executable (why two commands) Compilation Commands · Lesson 1

Lessons

Homework

Help Pages

Multiple Files

  • The Task Multiple Files · Lab Activities

Automating the Build Process

↔ See also header files, recompilation

compilation commands

clang++ -c prog.cpp makes prog.o; clang++ -o prog prog.o links it into an executable; ./prog runs it.

Also: clang++ flags, -c, -o

Introduced: Compilation Stages: C++ source → Object File (-c: compile to an object file) Compilation Commands · Lesson 1

Lessons

Homework

Help Pages

Arrays

Multiple Files

  • The Task Multiple Files · Lab Activities

multifile programs

Split a program over several .cpp files so shared code is written once, compiled separately, then linked.

Introduced: Summary of Compilation (building several .cpp files) Compilation Commands · Lesson 1

Lessons

  • The Problem (why split: code duplication) Why Multiple Files? · Lesson 1
  • A First Attempt (splitting cowchat in two) A Multifile Program · Lesson 1

Homework

Help Pages

Multiple Files

  • The Task Multiple Files · Lab Activities

↔ See also header files

header files

A .hpp file of declarations that several .cpp files #include, so nobody types (or compiles) the same declaration twice.

Also: .hpp vs .cpp

Introduced: Header Files Lesson 1

Lessons

Homework

Multiple Files

  • The Task Multiple Files · Lab Activities

→ Leads to templates and compilation↔ See also include guards, #include, declaration vs. definition, multifile programs, compiling vs. linking, recompilation

declaration vs. definition

A declaration says a function exists and what it takes and returns; the definition is its body. Declare before you use.

Also: forward declaration

Introduced: The Problem: printmoos Not Declared! (why the compiler needs a declaration) A Multifile Program · Lesson 1

Lessons

  • Fixing the Problem (forward declaration) A Multifile Program · Lesson 1
  • An Example (forward declarations for mutual calls) Should a Source File Include Its Own Header File? · Lesson 1
  • The Class Header File (class definition vs. member function definitions) Declarations/Definitions · Lesson 1

Homework

↔ See also header files, recompilation

#include

#include pastes a file's whole contents in before compiling; quotes for our own files, angle brackets for system ones.

Also: preprocessor

Introduced: #include Directives Lesson 1

Homework

Help Pages

Multiple Files

  • The Task (adding only the #includes each file needs) Multiple Files · Lab Activities

→ Leads to include guards↔ See also header files

the preprocessor (directives and macros)

A first pass over the text: directives starting with # (#include, #define, #ifndef) rewrite the source before the compiler sees it.

Also: #define, macro, #ifdef, #ifndef, #endif, conditional compilation, preprocessor directive

Introduced: Summary (first stage) What is Compilation? · Lesson 1

Lessons

Homework

← Builds on compilation stages→ Leads to include guards

include guards

The #ifndef/#define/#endif wrapper that keeps a header's declarations from appearing twice when it's included more than once.

Also: #ifndef, #define, #endif, #pragma once

Introduced: A Simple Example (the problem: double inclusion) Another Problem · Lesson 1

Lessons

Homework

Help Pages

← Builds on #include, the preprocessor (directives and macros)↔ See also header files

recompilation

After a change, rebuild only what depends on it: a changed .cpp needs itself and a relink; a changed header, every includer.

Also: what to rebuild after a change

Introduced: Exercise: Compiling a Multifile Program (only the changed file) Lesson 1

Lessons

Homework

Help Pages

  • Why So Many Steps? (why separate compilation saves time) Compiling and Running Code in C++
  • Prerequisites (header changes must trigger recompiling includers) Working with Makefiles

Automating the Build Process

  • Review build-all.py (build-all.py rebuilds everything) Automating the Build Process · Lab Activities
  • rebuild.py (recompile only what changed) Automating the Build Process · Lab Activities

→ Leads to Makefiles↔ See also header files, declaration vs. definition, compiling vs. linking

Makefiles

A Makefile lists targets, their prerequisites and the commands to build them; make rebuilds only what is out of date.

Also: make

Introduced: Working with Makefiles

Homework

Help Pages

Automating the Build Process

← Builds on recompilation↔ See also recursion

compiler errors

Read which tool complained: the compiler rejects wrong types, undeclared names and syntax mistakes; missing or duplicate definitions are link errors.

Also: error messages, warnings

Introduced: The Compiler Handles Types (type errors and conversion warnings) Compiler Responsibilities · Lesson 1

Lessons

Homework

Help Pages

↔ See also stubs

compile time vs. run time

Names, types and syntax are settled by the compiler; values only exist once the program runs.

Also: compile time, run time, runtime error, compile error vs runtime error

Introduced: The Compiler Handles Types (types are compile-time knowledge) Compiler Responsibilities · Lesson 1

Lessons

← Builds on compilation stages↔ See also constexpr, templates, undefined behavior

References and pointers

references

Another name for data that already exists; fixed at initialization, it never changes what it names.

Also: & in a type, aliases, reference to a pointer, Node*&

Introduced: Reference Types Lesson 2

Lessons

Homework

Help Pages

  • Initialization (references have no box) Rules for Drawing Memory Diagrams

Context Matters

More Memory Diagrams

  • Snippet 3 (a reference parameter returned as a reference) More Memory Diagrams · Lab Activities

⇄ Contrast with pointers→ Leads to const references, pass by value / pass by reference, returning references↔ See also what a symbol means depends on context

const references

A read-only name for existing data: no changes through that name, and no non-const reference to a const.

Introduced: Read-Only (const) References const References · Lesson 2

Lessons

Homework

← Builds on references, the const qualifier↔ See also lvalues and rvalues

the const qualifier

const promises a variable won't change; unlike constexpr, its value needn't be known until the program runs.

Also: const variable, read-only, const vs constexpr

Introduced: The const Qualifier const References · Lesson 2

Lessons

Homework

⇄ Contrast with constexpr→ Leads to const references

C++ is not Java

A C++ reference always names one real location: it can't be re-pointed and it can't be null, unlike Java's.

Also: Java references

Introduced: Warning: C++ Is Not Java Lesson 2

Lessons

Homework

⇄ Contrast with pointers

pass by value / pass by reference

By value, a function gets its own copy and the caller's data is safe; by reference, it works on the original.

Introduced: Example: References as Function Parameters Lesson 2

Lessons

Homework

  • The Memory Model (increment(int x) works on a copy) Written Questions · HW 0, Episode 2

← Builds on references→ Leads to output parameters (several results from one call)

output parameters (several results from one call)

A reference parameter lets a function fill in results for its caller, so one call can hand back several values.

Also: out parameter, return multiple values, std::tuple, structured bindings

Introduced: References Exercise 4: Multiple “Return” Values via References Lesson 2

← Builds on pass by value / pass by reference

pointers

A pointer is a memory address with a type: float* is the address of a float; follow it with * to get the float.

Also: int*, memory address, hexadecimal, hex address, ptr

Introduced: Pointer Types What's the C++ Type for a Memory Address? · Lesson 1

Lessons

⇄ Contrast with array decay, references, C++ is not Java, iterators→ Leads to address-of and indirection, the arrow operator ->, C strings and string literals, iterators↔ See also what a symbol means depends on context

address-of and indirection

&x is the address of x; *p follows pointer p to the thing it points to. Roughly opposites.

Also: &x, *p, dereference

Introduced: Accessing the Value at an Address (the indirection operator *) Accessing Array Elements · Lesson 2

Lessons

Help Pages

Context Matters

← Builds on pointers↔ See also what a symbol means depends on context

the arrow operator ->

p->member follows pointer p and reaches the member in one step; the same as (*p).member, but preferred.

Also: ->, arrow, (*p).x, member access through a pointer

Introduced: An Example that Works Too Hard Saving Time by Not Moving/Copying Data · Lesson 1

Lessons

Help Pages

← Builds on pointers, member variables

past-the-end pointer

A pointer just beyond the last element; a first pointer and a past-the-end pointer describe a range, and p < end stops the loop.

Introduced: Past-the-End Pointers Lesson 1

Lessons

Homework

→ Leads to iterators, begin and end

const and pointers

const float* points to read-only data; float* const is a read-only pointer; use both consts to lock both.

Also: pointer to const, const pointer

Introduced: The Solution: const Read-Only Access · Lesson 1

Lessons

  • An Example (const at several levels) Reading Complicated Types · Lesson 1

reading types

Read a type from the variable's name: right to the end, jump back, then right to left.

Also: inside-out rule, complicated types

Introduced: Declaring Arrays in C++ (inside-out rule) Lesson 2

Lessons

Homework

this

Inside a member function, this is a hidden pointer to the object it was called on; say *this for the object itself.

Introduced: The this Pointer in Member Functions Lesson 1

Lessons

Help Pages

the heap and new

The heap is memory we allocate and free whenever we say; new allocates, initializes, and returns a pointer to the new thing.

Also: dynamic allocation, free store, static allocation, automatic allocation, new T[n], dynamic array

Introduced: The Heap (the heap) The Heap and new · Lesson 2

Lessons

Homework

Help Pages

⇄ Contrast with the stack→ Leads to delete and delete[], classes that allocate memory, ownership↔ See also static members

nullptr

A pointer value meaning "points to nothing": unlike a garbage address you can check for it, though following it is still forbidden.

Also: null pointer

Introduced: Null Pointers Lesson 2

Lessons

Homework

C strings and string literals

A string literal like "Hello" is a C-style const char*, not a std::string; "Hello"s makes a real one.

Also: const char*, string literal, C string, char array, std::string vs char*

Introduced: Templates vs. Overloading Lesson 1

Homework

  • Task 2: Modifying Text (toupper and tolower on characters) Coding Part: More Fun With Fonts · HW 1
  • Constant Definitions (constexpr char[] file names) Plotting Example Data · HW 2
  • Helpful Hints (C loops over const char* until the zero byte; convert to std::string) Phase 3 · HW 8

← Builds on arrays, pointers

delete and delete[]

delete p destroys and deallocates the thing p points to; delete[] is for arrays from new[]; use the matching form.

Introduced: The delete Keyword Lesson 2

Lessons

Homework

Help Pages

← Builds on the heap and new

memory leaks

Heap memory we have lost every pointer to: still taken, unreachable, and not returned until the program ends.

Introduced: "Resizing" The Array Elephant Parade, Part 4: Memory Leaks · Lesson 2

Lessons

Homework

Help Pages

→ Leads to Valgrind

dangling pointers

A pointer to memory that has been deallocated; following it is a bug, and may look fine until the memory is reused.

Introduced: Elephant Parade, Part 5: Dangling Pointers and Double Deletes Lesson 2

Lessons

More Memory Diagrams

  • Snippet 2 (its reference twin) More Memory Diagrams · Lab Activities

⇄ Contrast with double delete↔ See also iterator validity

double delete

Deleting the same heap memory twice, usually through a dangling pointer; most often a crash.

Introduced: Elephant Parade, Part 5: Dangling Pointers and Double Deletes Lesson 2

Homework

⇄ Contrast with dangling pointers

lvalues and rvalues

An lvalue has a memory location (and often a name); an rvalue is a temporary result that lasts for one line of code.

Also: temporaries

Introduced: Results from Expressions Discovering Temporaries · Lesson 1

Lessons

More Memory Diagrams

↔ See also returning values, const references

returning references

A function can return a reference, which makes the call an lvalue you can assign to; never return one to a local variable.

Also: dangling reference

Introduced: Functions Can Return References Returning References · Lesson 1

Lessons

  • Pitfalls (pitfall: reference to a local) When to Return References · Lesson 1
  • Overloading Operators (operator<< returns its left operand so calls chain) Overloading · Lesson 1
  • Putting It All Together (operator[] returns a reference so x[1] = ... works) Lesson 1

Homework

More Memory Diagrams

  • Snippet 2 (returning a reference to a local) More Memory Diagrams · Lab Activities

← Builds on references⇄ Contrast with returning values↔ See also assignment operator

returning values

A call that returns a value initializes an object in the caller's stack frame; inside the function that spot is called _retval.

Also: return by value, copy elision, RVO, return value optimization, NRVO

Introduced: How Functions Return Result Values Returning Values · Lesson 1

Lessons

More Memory Diagrams

  • Snippet 1 (returning a Coord by value) More Memory Diagrams · Lab Activities

← Builds on object lifetime⇄ Contrast with returning references↔ See also lvalues and rvalues

what a symbol means depends on context

One symbol can mean several things in C++, so ask what surrounds it: a type, an expression, a declaration?

Also: what does & mean, what does * mean, same symbol different meanings, declarations vs statements vs expressions

Introduced: Random Character in a File, Part 1 a “-” sign. (the - sign) Context Matters · Lab Activities

Context Matters

↔ See also references, pointers, address-of and indirection

Classes and object lifetime

classes

A class bundles data with the functions that use it into a new type; each object is an instance.

Also: objects, instances, OOP

Introduced: Exploring a C++ Class Lesson 1

Lessons

Homework

→ Leads to struct vs. class, nested classes, type aliases (using)

struct vs. class

A struct is a class whose members are public by default; C++ programmers use it to bundle plain data, like a tree Node.

Also: struct, plain old data, struct or class, POD

Introduced: struct vs class Encoding a BST in C++ · Lesson 1

Homework

← Builds on classes, access control

member variables

Each object's own data, also called data members; CS 70 always ends their names with an underscore, like age_.

Also: data members, trailing underscore

Introduced: Member Variables (a.k.a. Data Members) Lesson 1

Lessons

  • Using Member Variables (using them inside member functions) Member Variables (a.k.a. Data Members) · Lesson 1

Help Pages

→ Leads to the arrow operator ->

member functions

Functions that belong to a class: declared in the .hpp, defined in the .cpp as Cow::moo, called with a dot.

Also: methods, ::

Introduced: Member Functions Lesson 1

Lessons

→ Leads to the scope-resolution operator ::

the scope-resolution operator ::

someplace::something means something inside of someplace: Cow::moo is moo in Cow, std::cout is cout in std.

Also: ::, double colon, Cow::moo

Introduced: Defining Member Functions Member Functions · Lesson 1

Lessons

Homework

← Builds on namespaces, member functions

const member functions

A trailing const promises not to change the object, and is what lets a function be called on a const object.

Introduced: const Member Functions Lesson 1

Lessons

Homework

Help Pages

→ Leads to mutable data members↔ See also iterators

namespaces

A named collection of functions and variables that keeps names from colliding; std::cout is the cout inside namespace std.

Also: std::, using namespace std

Introduced: What is a Namespace? Lesson 1

Lessons

Homework

First Day with CS 70

  • First Tasks (removing the std:: prefixes) First Day with CS 70 · Lab Activities

→ Leads to the scope-resolution operator ::

access control

public: and private: in the class definition decide who may use each member; privacy is per class, not per object.

Also: public, private

Introduced: Access Control Lesson 1

Lessons

Homework

→ Leads to struct vs. class, friend

constructors

A special member function that initializes a new object's data members; a parameterized one takes arguments, the default one takes none.

Also: default constructor, ctor

Introduced: Constructors Lesson 1

Lessons

Homework

  • Constructors & Destructors (default constructor only) CS 70 Turtle Class Interface · HW 2
  • Your Task… (default constructor sets LEAF; add a one-argument constructor) Phase 4 · HW 7
  • Let's Go! (the parameterized constructor) Phase 4 · HW 8

→ Leads to member initialization lists, copy constructor↔ See also synthesized functions

member initialization lists

The colon list before a constructor's body where every member gets initialized; use it instead of assigning in the body.

Introduced: Initializing Members with the Member-Initialization List Member-Initialzation Lists · Lesson 1

Lessons

Homework

Help Pages

← Builds on constructors

initialization

Every object is initialized exactly once, by exactly one constructor; a built-in type you don't initialize gets an indeterminate value.

Also: default/direct/copy initialization, brace initialization

Introduced: Differences Related to Variable Values (why initialize) Variables in Python & C++ · Lesson 1

Lessons

Homework

Help Pages

  • Initialization (drawing initialization) Rules for Drawing Memory Diagrams

⇄ Contrast with indeterminate values, assignment operator→ Leads to brace initialization

brace initialization

Write Cow bessie{3, 12} with braces and no equal sign; braces are stricter than parentheses, allowing promotions but not conversions.

Also: curly braces, uniform initialization, list initialization, Cow bessie{3, 12}

Introduced: Curly Brace Initialization Constructing Objects · Lesson 1

Homework

  • Your Task (an array of objects in the list) Setting the Scene · HW 3

← Builds on initialization

copy constructor

Takes a const reference to an existing object and initializes a brand-new copy; also used for by-value parameters and returns.

Also: copy ctor

Introduced: Copy Initialization of Objects All About Initialization · Lesson 2

Lessons

Homework

← Builds on constructors⇄ Contrast with assignment operator→ Leads to copy-and-swap

synthesized functions

The compiler can write default and copy constructors, assignment and destructor; always say = default, = delete, or write your own.

Also: = default, = delete, compiler-generated

Introduced: The Default Constructor Can Be _Automatically_ Synthesized (synthesized default constructor) Constructors · Lesson 1

Lessons

Homework

Help Pages

↔ See also constructors

assignment operator

operator= changes an existing object to look like another one; a = b calls a.operator=(b), unlike the = in a declaration.

Also: operator=

Introduced: Use Phase for Instances of Classes Use Phase · Lesson 2

Lessons

Homework

⇄ Contrast with initialization, copy constructor→ Leads to copy-and-swap, self-assignment↔ See also returning references

destructors

~Cow() runs automatically when an object is destroyed, to clean up; never call it yourself, and always have one.

Also: dtor

Introduced: Destruction of Instances of Classes Destruction · Lesson 2

Lessons

Homework

Help Pages

classes that allocate memory

When an object owns heap memory through a pointer, its constructors, destructor, copy and assignment all need extra work.

Also: heap-allocated members

Introduced: When Classes Allocate Memory… Lesson 1

Lessons

Homework

← Builds on the heap and new→ Leads to ownership

ownership

The class that owns a resource creates it and destroys it; if two objects both think they own the same data, that's a bug.

Also: object ownership, who deletes, owns its objects

Introduced: The Principle of _Ownership_ Initializing Heap Memory in Member Functions · Lesson 1

Lessons

Homework

  • Sanity Check (only the owner cleans up) Dynamic CoordVector · HW 4

← Builds on classes that allocate memory, the heap and new

deep vs. shallow copy

A shallow copy duplicates the members, so two objects share heap memory; a deep copy duplicates what they point to too.

Introduced: Beware of Shallow Copies! (shallow copy) Providing a Copy Constructor · Lesson 1

Lessons

Homework

copy-and-swap

Take the parameter by value, swap members with that copy, and let its destructor clean up the old contents.

Also: copy and swap idiom, swap, rule of three

Introduced: Less Code! The Copy-and-Swap Idiom for Assignment Assignment for Custom Classes: Assignment Operators · Lesson 1

Lessons

Homework

← Builds on copy constructor, assignment operator

self-assignment

x = x must leave x alone; an operator= that frees its memory first needs a this == &other check.

Introduced: Dealing with Self-Assignment Assignment for Custom Classes: Assignment Operators · Lesson 1

Homework

← Builds on assignment operator

delegating constructors

A constructor can call another constructor of its class where the member-initialization list would go: Barn() : Barn{DEFAULT_SIZE}.

Introduced: Delegating Constructors Revisiting the Default Constructor · Lesson 1

Homework

overloading

Functions (and operators) may share a name; C++ picks one by the number and types of the arguments, never by the result.

Also: function overloading, operator overloading, operator<<, operator[], overload resolution

Introduced: Overloading Lesson 1

Lessons

Homework

Help Pages

static members

A static member belongs to the class, not any object: one shared copy, reached as Cow::name; a static function has no this.

Also: static member functions

Introduced: Homework 3 Mini Lesson: static Class Members static Members · HW 3

Lessons

Homework

↔ See also the heap and new

exceptions

throw reports an error from a function that can't do its job, like adding a Cow to a full Barn.

Also: throw, std::length_error, exception, throwing an error

Introduced: Adding Cows to the Barn (throw when full) Initializing Heap Memory in Member Functions · Lesson 1

Homework

Help Pages

↔ See also undefined behavior, interface, encoding, implementation

friend

friend class IntList; lets IntList use Iter's private members; use it sparingly, only for classes designed to work as a pair.

Also: friend class, friendship, friend function

Introduced: Nested Classes, Privacy and Friendship (friend class IntList;) Iterator Encoding · HW 5

← Builds on access control

nested classes

A class defined inside another (IntList::Iter) is logically part of it, sees its private members, and must be defined inside the outer class's braces.

Also: nested class, inner class, IntList::Iter, forward declaration of a class

Introduced: Nested Classes, Privacy and Friendship Iterator Encoding · HW 5

← Builds on classes

type aliases (using)

using const_iterator = Iter; gives an existing type a second name, so users write IntList::const_iterator while the code keeps its own naming.

Also: using, typedef, using const_iterator = Iter, public alias for a private class

Introduced: Additional Specifics of Our IntList::const_iterator Class (using const_iterator = Iter) Iterator Encoding · HW 5

← Builds on classes

enumerations (enum)

A user-defined type with a small set of named values (really integers), such as LEAF, ROOT and RANDOMIZED.

Also: enum, enum class, bst_style, named constants

Introduced: What's an enum? TreeSet<T> Specifications · HW 7

Homework

  • Your Task… (declare bst_style outside the class; store it in a data member) Phase 4 · HW 7

mutable data members

A mutable data member can change even inside a const member function, for bookkeeping that isn't part of the object's visible state.

Also: mutable, logical constness, update a member in a const method

Introduced: How to Update Statistics Inside a const Function Phase 7 · HW 8

← Builds on const member functions

Iterators and lists

auto

The compiler fills in a variable's type from its initializer; the type is still fixed at compile time. Use it when it helps readability.

Also: type inference

Introduced: C++'s auto Keyword C++'s auto keyword · Lesson 2

Lessons

Help Pages

std::vector

A growable array that knows its size and capacity; push_back adds at the end, and begin/end loops work as they do for arrays.

Also: vector, push_back, STL

Introduced: A Simple Program Using Primitive Arrays (why: fixed-size arrays vs. a vector that grows) Lesson 2

Lessons

Homework

  • Written Questions (a primitive array behind the scenes, doubling when full) HW 5
  • Questions (space per element and the doubling sawtooth) Empirical Exploration · Written Questions

⇄ Contrast with std::list↔ See also amortized analysis, doubling capacity

std::list

The standard doubly linked list; its begin() and end() give iterators that are not pointers but behave enough like them.

Also: linked list (standard)

Introduced: A Simple Program Using std::list Lesson 2

Lessons

Homework

  • Your Task (forward_list: remove_if with a lambda, or before_begin and erase_after) Erasing Elements · Phase 9

⇄ Contrast with std::vector

iterators

An object representing the location of one item in a collection: start at begin(), advance with ++, use * for the item, stop at end().

Also: iterator

Introduced: What Is An Iterator? Lesson 2

Lessons

Homework

Help Pages

← Builds on pointers, past-the-end pointer⇄ Contrast with pointers→ Leads to range-based for, in-order traversal↔ See also const member functions, the stack, operation counting

begin and end

begin() gives the starting location and end() a special past-the-end value for != to compare against.

Also: past-the-end iterator

Introduced: Putting It All Together (begin() and end() returning pointers on your own class) Lesson 1

Lessons

Homework

← Builds on past-the-end pointer

range-based for

for (T v : c) hides the iterator: C++ calls begin and end for you and hands you each item.

Also: for-each loop, for (auto x : c)

Introduced: Hiding the Iterator Lesson 2

Lessons

Homework

← Builds on iterators

const_iterator

A read-only iterator whose * gives a const reference; containers hand out iterator or const_iterator depending on constness.

Also: read-only iterator, const iterator

Introduced: Read-Only Iterators Lesson 2

Homework

iterator validity

An iterator is valid while its container and item are still there; after an erase or resize, don't trust it.

Also: iterator invalidation, invalid iterators, iterator rules, past-the-end misuse

Introduced: Only Use _Valid_ Iterators Only Use Valid Iterators · Lesson 1

Lessons

Homework

↔ See also dangling pointers, undefined behavior, C++'s guiding principles, debugging, interface, encoding, implementation

interface, encoding, implementation

Interface: what it does. Encoding: how its data is organized. Implementation: the code that makes it work.

Also: abstraction, representation, contract, promises, API

Introduced: What's an Interface? Lesson 1

Lessons

Homework

Help Pages

→ Leads to container interfaces: stacks, queues, deques↔ See also exceptions, iterator validity

linked lists

Nodes that each hold an item and a link to the next: quick at the front, slow to reach the nth.

Also: IntList, nodes

Introduced: <sc>String-List</sc> Encoded using a Linked List What's an Encoding? · Lesson 1

Lessons

Homework

⇄ Contrast with array-backed lists↔ See also invariants

array-backed lists

A list kept in an array, swapped for a bigger one when full: quick indexing, slow inserts near the front.

Also: dynamic arrays, IntVector, CoordVector, capacity

Introduced: A First Draft of the CoordVector Class (first draft: fixed-size CoordVector) CoordVector, Part 1 · HW 4

Lessons

Homework

⇄ Contrast with linked lists→ Leads to circular buffers (ring buffers)↔ See also doubling capacity, amortized analysis, summations, O and Ω

queues

First in, first out, like a bank line: add at the back, remove from the front. A priority queue removes the most important first.

Also: queue operations, FIFO, std::queue, std::deque

Introduced: Queue vs Stack Operations Queue Operations · HW 4

Lessons

Homework

↔ See also circular buffers (ring buffers), depth-first and breadth-first search

container interfaces: stacks, queues, deques

Stack, queue, steque, deque, list, set, map, multiset and multimap: what you may do with a container, apart from how it's encoded.

Also: stack data structure, LIFO, FIFO, deque, steque, abstract data type, ADT

Introduced: The Depth-First Search Approach (stack: LIFO) DFS Solver · HW 4

Lessons

Homework

← Builds on interface, encoding, implementation→ Leads to depth-first and breadth-first search

invariants

A condition that is true whenever no member function is half-way through running; for IntList it says what front_, back_ and size_ must look like.

Also: class invariant, data-structure invariant, check_invariants, selfCheck, sanity check, precondition

Introduced: Invariants (empty, one element, two or more) IntList Encoding · HW 5

Homework

Help Pages

↔ See also linked lists, testing

circular buffers (ring buffers)

Instead of shifting elements, keep an offset to the logical start and wrap indexes round the end of the array.

Also: ring buffer, wraparound, offset, deque as an array, circular array

Introduced: The Clever Solution: Circular Buffers Queue Operations · HW 4

Homework

← Builds on array-backed lists↔ See also queues

depth-first and breadth-first search

Depth-first dives down one path and backs up at dead ends (a stack); breadth-first spreads out level by level (a queue).

Also: DFS, BFS, backtracking, shortest path, solving a maze, graph search

Introduced: Solving the Maze, Part 1 (depth-first search) DFS Solver · HW 4

Homework

← Builds on container interfaces: stacks, queues, deques↔ See also the stack, queues

Complexity

empirical timing

Timing a program says how long that program took under those exact conditions; extrapolate carefully.

Introduced: Empirically Timing Programs Lesson 3

Lessons

Homework

operation counting

Choose an operation and what n means, then write a function C(n) for how often that operation runs.

Also: input size, choosing n, counting operations

Introduced: Identifying Operations (identifying the operations in code) Lesson 2

Lessons

Homework

  • Questions (count array accesses or pointer follows) Applying Theory · Written Questions

↔ See also iterators

summations

Σ adds up a per-iteration count over a loop; Gauss's formula: 1 + 2 + … + N = N(N+1)/2.

Also: sum of i, N(N+1)/2, arithmetic series, geometric series

Introduced: Example 3 (Gauss's formula: sum of 1..N) Nested Loops · Lesson 3

Lessons

Homework

Help Pages

↔ See also array-backed lists

asymptotic analysis

How does cost scale as the input grows toward infinity? Ignore coefficients and small terms; compare growth.

Introduced: Asymptotic Analysis Asymptotic Complexity Analysis · Lesson 3

Lessons

Homework

→ Leads to common orders of complexity

common orders of complexity

Standard reference classes for Θ: constant, logarithmic, linear, linearithmic, quadratic, cubic, exponential, and up.

Also: O(1), O(log n), O(n log n), linearithmic, quadratic, exponential, orders of growth, O(n), O(n^2)

Introduced: Order of Complexity Big Θ · Lesson 3

Lessons

Homework

← Builds on asymptotic analysis

Θ (big Theta)

f is Θ(g) when f/g settles on a finite, non-zero constant: the two grow at a similar rate.

Also: Theta, tight bound

Introduced: Big &Theta; Big Θ · Lesson 3

Lessons

Homework

  • The Interface (stating exact costs: copy and assign are Theta(n)) Implementing IntList (#4) · HW 5

⇄ Contrast with O and Ω

O and Ω

O means no worse than and Ω means no better than, in growth rate; both together give Θ.

Also: big O, big Omega, upper bound

Introduced: Big \\( \mathrm{O} \\) (Big O) Big O and Ω · Lesson 3

Lessons

Homework

⇄ Contrast with Θ (big Theta)↔ See also array-backed lists, quicksort

little o and little ω

o means definitely better than, ω definitely worse than: the strict versions of O and Ω, like < and >.

Introduced: The Whole Asymptotic Family Lesson 3

Lessons

best, worst and expected case

When n doesn't pin down the input, count the fewest operations (best), the most (worst), or the typical (expected).

Also: average case, expected case, average case analysis

Introduced: Another Example (why: n doesn't determine the count) Best- and Worst-Case Analysis · Lesson 3

Lessons

Homework

⇄ Contrast with amortized analysis↔ See also quicksort

expected value

A weighted average of each case's cost, weighted by that case's probability: the "typical" number of operations.

Also: probability, average, weighted average, expectation

Introduced: Uniform Probability Assumption (uniform-probability assumption) Expected Case Analysis · Lesson 3

Lessons

linear search

Check array elements one at a time until you find x: Θ(1) best case, Θ(n) worst and expected.

Introduced: Look Up in an Array Case Study: Linear Search · Lesson 3

Lessons

⇄ Contrast with binary search

quicksort

Pick a pivot, partition around it so it lands in its final spot, then recurse on each side.

Also: quick sort, pivot, partition

Introduced: Quicksort Explained Big O and Ω

Lessons

← Builds on recursion⇄ Contrast with heapsort↔ See also best, worst and expected case, O and Ω

amortized analysis

Amortized time is chosen per operation so that any run of operations, from the very start, takes at most the sum of those times.

Also: banker's method, amortized time

Introduced: Amortized Time Characterizing Operation Costs · Lesson 1

Lessons

  • Irregular Single-Operation Performance (work shifted around (motivation)) Variable Costs · Lesson 1
  • IntVector push_back() (push_back: aggregate method and the $3 charge) Lesson 1
  • Aggregate Method (aggregate method) Proving Amortized Bounds · Lesson 1
  • Banker's Method (banker's method) Proving Amortized Bounds · Lesson 1
  • Physicist's Method (physicist's method (potential function)) Proving Amortized Bounds · Lesson 1
  • Takeaways (what an amortized bound promises) Proving Amortized Bounds · Lesson 1
  • Contrasting Amortized Time (versus worst-case and expected time) Amortized Time vs. … · Lesson 1
  • Example 1 (applying a bound: total for m inserts) Splay-Tree Complexity 2 · Lesson 1
  • Example 2 (applying a bound: m lookups) Splay-Tree Complexity 2 · Lesson 1
  • Before You Start… (first push versus the 300-millionth) Lesson 2
  • Proposal (amortized expected) Dynamic Table Size · Lesson 1
  • Exercise 2a (n inserts: amortized expected) Interpreting Hash Table Complexities · Lesson 1
  • Fibonacci Heap (amortized Theta(1) Change-Priority (Fibonacci heap)) Amortized Complexity · Lesson 1

Homework

⇄ Contrast with best, worst and expected case, in-order traversal→ Leads to doubling capacity, splay trees↔ See also std::vector, array-backed lists, hash tables

doubling capacity

Double the array whenever it fills: m pushes cost about 2m moves in all, so push_back is amortized Θ(1).

Also: push_back cost

Introduced: Update Constructor and pushBack (double in pushBack()) Dynamic CoordVector · HW 4

Lessons

Homework

← Builds on amortized analysis↔ See also std::vector, array-backed lists, hash tables

Trees

sets and maps

A set stores keys and answers "is it here?"; a map stores each key with a value, like a Python dictionary.

Also: lookup, insert, std::set, std::map, unordered_map, unordered_set

Introduced: Search (insert and lookup; map vs. set) Lesson 1

Lessons

Homework

→ Leads to multisets (counting keys)

binary search

On a sorted array, look at the middle and throw away the half that can't hold the item: lookup in O(log n).

Also: bisection, searching a sorted array

Introduced: Performance of a Sorted Array-Backed List (sorted array) Search · Lesson 1

⇄ Contrast with linear search

tree terminology

The shared vocabulary: node, edge, parent/child, root, leaf, subtree, height (an empty tree is –1), binary, balanced.

Also: root, leaf, height, depth, size

Introduced: Tree Terminology Lesson 1

Lessons

Homework

→ Leads to balanced trees, binary heaps

balanced trees

A tree is balanced if no branch is much longer than another; balance keeps height Θ(log n), where a stick is Θ(n).

Also: balanced tree, tree balance, self-balancing tree, height-balanced, stick

Introduced: Tree Terminology (definition of balanced) Lesson 1

Lessons

Homework

← Builds on tree terminology

binary search trees

A binary tree where each key is bigger than everything in its left subtree and smaller than everything in its right.

Also: BST

Introduced: Binary Search Trees (Lookup) (definition) BST Lookup · Lesson 1

Lessons

Homework

→ Leads to recursive helper functions, random trees

recursion

Say precisely what the function promises, handle the base case, then trust that promise on a smaller input and finish the job.

Also: recursive, base case, recursive step, recursive function

Introduced: Designing Recursive Algorithms (designing recursive algorithms) BST Insert · Lesson 1

Lessons

  • In-Order Traversal (applying the design steps to Print-In-Order) Iterating Over Our BST · Lesson 1

Homework

Automating the Build Process

  • make (make is a recursive function) Automating the Build Process · Lab Activities

→ Leads to quicksort, recursive helper functions↔ See also Makefiles, in-order traversal

recursive helper functions

A public member function hands the real work to a private recursive helper that takes the internal data (the Nodes) as a parameter.

Also: helper function, private helper, insertNode, wrapper function

Introduced: insert() C++ Implementation: insert() · Lesson 1

Lessons

Homework

← Builds on recursion, binary search trees

BST delete

No children: just remove it. One child: move it up. Two children: replace it with the largest key to its left.

Introduced: BST Delete Lesson 1

Lessons

Homework

in-order traversal

Do the left subtree, then the node, then the right subtree, and a BST's keys come out sorted.

Also: tree iterator, in-order iterator, DFS, BFS

Introduced: In-Order Traversal Iterating Over Our BST · Lesson 1

Lessons

Homework

← Builds on iterators⇄ Contrast with amortized analysis↔ See also recursion

tree rotations

A constant-time rewiring of a node and one of its children that reshapes a tree but keeps it a valid BST.

Also: rotate left/right

Introduced: Rearranging BSTs with Rotations Lesson 2

Lessons

Homework

  • Your Task… (write rotateLeft and rotateRight helpers) Phase 5 · HW 7
  • Maintaining Sizes (update subtree sizes during a rotation in constant time) Phase 6 · HW 7
  • Balancing Functions (single versus double rotation in balanceLeft and balanceRight) Weight-Balanced Trees · Phase 9

→ Leads to red–black trees, splay trees

2–3–4 trees

Nodes hold one to three keys (two to four children), so every leaf stays at the same depth; 4-nodes are split on the way down.

Introduced: 2-, 3-, and 4-Nodes (2-, 3- and 4-nodes) Multiple Types of Nodes · Lesson 2

Lessons

⇄ Contrast with red–black trees→ Leads to red–black trees

red–black trees

A 2–3–4 tree drawn as a binary tree, with red nodes marking the extra keys of 3- and 4-nodes.

Also: RB tree, LLRB

Introduced: Node Coloring (node coloring) Red–Black Trees · Lesson 2

Lessons

← Builds on 2–3–4 trees, tree rotations⇄ Contrast with 2–3–4 trees

splay trees

A BST that rotates every inserted or found key up to the root, so recently used keys are cheap to find again.

Introduced: Splay Trees Lesson 1

Lessons

← Builds on tree rotations, amortized analysis

locality of reference

The tendency of a system to look up the same things repeatedly; temporal locality means recent lookups are likely to repeat.

Also: locality, temporal locality, recently used, LRU

Introduced: Locality of Reference (temporal locality) A Motivating Example: Network Routing · Lesson 1

Lessons

Homework

  • Comparisons (Q2.2: caches explain why random keys run slower) Written Questions · HW 8

↔ See also linear probing

randomized BSTs

At each node on the way down, randomly decide whether the new key becomes that subtree's root, imitating a shuffled insertion order.

Also: insert at root, move to root

Introduced: Randomized BSTs Randomized Trees · Lesson 2

Lessons

Homework

  • Homework 7 (implement a self-balancing BST by randomized insertion) HW 7
  • BST Styles (the three insertion styles: LEAF, ROOT, RANDOMIZED) TreeSet<T> Specifications · HW 7
  • Your Task… (insert and move to root (the ROOT scheme)) Phase 5 · HW 7
  • Update insert (insert at root with probability 1/(size+1), else recurse) Phase 7 · HW 7
  • Questions (RANDOMIZED insertion behaves like std::set on sorted input) Phase 8 · HW 7

⇄ Contrast with random trees

random trees

A BST built by inserting keys in random order: balanced-looking shapes vastly outnumber sticks, so the expected depth is Θ(log n).

Also: random BST, randomly built tree, random insertion order, expected height

Introduced: Randomly Generated BSTs Lesson 2

Lessons

Homework

← Builds on binary search trees⇄ Contrast with randomized BSTs

random numbers

A PRNG makes random-looking numbers deterministically; the seed picks its sequence; RandUInt32's get(N) returns 0 to N-1.

Also: RandUInt32, seeding

Introduced: From Dice to C++ (pseudorandom generators; why not rand() % N) Generating Random Numbers · Lesson 2

Lessons

Homework

Help Pages

Exploring the Terminal

↔ See also collisions, hash tables

lower_bound

Returns an iterator to the first element that is equal to or comes after the value you give it, or end if there is none.

Introduced: Phase 3: Implementing lower_bound in TreeSet<T> Phase 3 · HW 7

Homework

choosing a balanced tree

There is no best tree: red–black guarantees the worst case, splay trees reward locality, randomized trees are simplest.

Introduced: Comparing Approaches (randomized versus red-black versus splay) Contrasting BSTs · Lesson 2

Lessons

  • More to the Story (m inserts: simple BST versus red-black) Splay-Tree Complexity 1 · Lesson 1
  • Comparisons (simple BST vs splay vs red-black) Splay-Tree Complexity 2 · Lesson 1
  • Summary (randomized BST: best, worst and expected) Analyzing Randomized Trees · Lesson 2

Homework

  • The TreeSet<T> Interface (required costs: O(height), expected O(log n) when RANDOMIZED) TreeSet<T> Specifications · HW 7
  • Exploration (compare LEAF, ROOT, RANDOMIZED and std::set on big dictionaries) Phase 8 · HW 7
  • Questions (sorted input: LEAF and ROOT build sticks; lookup O(n) versus O(log n)) Phase 8 · HW 7
  • Testing Your Weight-Balanced Insertion (compare height and average depth across insertion schemes with minispell -w) Weight-Balanced Trees · Phase 9

Hash tables

hash functions

Turns a key into a hash value we map to a bucket. It must be deterministic, and should spread keys uniformly.

Also: hashing, hash value, perfect hash function, cryptographic hash, SHA-256, checksum

Introduced: Hash Functions Fixing Lookup · Lesson 1

Lessons

Homework

hash tables

An array of buckets plus a hash function that says which bucket each key belongs in, so we needn't search.

Also: buckets, table size, prime table size, removing from a hash table

Introduced: Hash Functions Fixing Lookup · Lesson 1

Lessons

Homework

→ Leads to Markov models and n-grams, multisets (counting keys)↔ See also random numbers, amortized analysis, doubling capacity

collisions

Two keys that want the same bucket. They're inevitable, so resolving them is the core problem for hash tables.

Introduced: Collisions Lesson 1

Lessons

Homework

  • collisions (count inserts into a non-empty bucket, including during reallocation) Phase 7 · HW 8

↔ See also random numbers

separate chaining

Give each bucket its own container, usually a linked list called a chain, so several keys can share a bucket.

Introduced: Separate Chaining Lesson 1

Lessons

Homework

⇄ Contrast with open addressing↔ See also load factor

load factor

λ = N/M, the average number of items per bucket. It measures how full the table is and drives the expected cost.

Also: LF

Introduced: Load Factor Expected Complexity of Separate Chaining · Lesson 1

Lessons

Homework

  • Writing loadFactor (keys divided by buckets, not by total count; empty table is 0) Phase 6 · HW 8
  • HashMultiset Interface (DEFAULT_MAX_LOAD_FACTOR; loadFactor = keys / buckets) HashMultiset<T> Specifications · HW 8

→ Leads to dynamic resizing↔ See also separate chaining, open addressing

dynamic resizing

As keys arrive, allocate a bigger table (usually double) and re-insert every key, keeping λ below a maximum.

Also: rehashing

Introduced: How to Resize a Hash Table Dynamic Table Size · Lesson 1

Homework

  • Phase 6: Rehashing (why: the table size is unknown ahead of time) Phase 6 · HW 8
  • Writing rehash (build a new table, reinsert KeyCounts, swap) Phase 6 · HW 8
  • HashMultiset Interface (rehash and the rules for when reallocation must happen) HashMultiset<T> Specifications · HW 8

← Builds on load factor

open addressing

One key per bucket; if yours is taken, follow a sequence of probes until you reach an empty bucket.

Also: probing

Introduced: Collision Resolution: Linear Probing Linear Probing · Lesson 2

Lessons

  • Details (insert and lookup procedure, wrap-around) Linear Probing · Lesson 2

Homework

  • Open Addressing (all elements live in the array; probe on collision) Phase 9

⇄ Contrast with separate chaining→ Leads to clustering↔ See also load factor

clustering

Runs of filled buckets make probing slow. Primary: contiguous keys. Secondary: keys with the same start bucket share a probe sequence.

Also: primary clustering, secondary clustering

Introduced: Primary Clustering (primary clustering) Linear Probing · Lesson 2

Lessons

← Builds on open addressing↔ See also linear probing, quadratic probing, double hashing

linear probing

Try bucket H, then H+1, H+2, ..., wrapping around. Easy to write, but keys pile up in clusters.

Also: primary clustering

Introduced: Linear Probing Lesson 2

Lessons

  • Example (insert 13 keys by hand) Linear Probing · Lesson 2
  • Linear Probing (pros and cons) Comparisons: Pros and Cons · Lesson 2

Homework

  • Your Task (probe the next index, wrapping around; stop at an empty slot) Open Addressing · Phase 9

↔ See also locality of reference, clustering

quadratic probing

Probe H, H+1, H+4, H+9, ... to jump out of clusters. Needs a prime table size and λ below 0.5.

Also: secondary clustering

Introduced: Collision Resolution: Quadratic Probing Quadratic Probing · Lesson 2

Lessons

  • Example (insert 13 keys by hand) Quadratic Probing · Lesson 2
  • Quadratic Probing (pros and cons) Comparisons: Pros and Cons · Lesson 2

↔ See also clustering

double hashing

A second hash value sets the step: probe H, H+I, H+2I, ..., so every key gets its own probe sequence.

Introduced: Collision Resolution: Double Hashing Double Hashing · Lesson 2

Lessons

  • Double Hashing (pros and cons) Comparisons: Pros and Cons · Lesson 2

↔ See also clustering

hash table complexity

With a good hash function and resizing: expected Θ(1) Lookup, amortized expected Θ(1) Insert, worst case Θ(n).

Also: expected O(1)

Introduced: Hash Table Complexities (the bottom line and its fine print) Dynamic Table Size · Lesson 1

Lessons

Homework

Markov models and n-grams

Count which characters follow each k-letter context, then roll dice weighted by those counts to invent words that sound right but aren't.

Also: Markov chain, n-gram, bigram, trigram, context length, training

Introduced: The Idea, by Hand Phase 1 · HW 8

Homework

← Builds on hash tables

multisets (counting keys)

Like a set, except inserting a key again adds one to its count; Python calls it a Counter.

Also: Counter, count of each key, HashMultiset, frequency table, histogram, std::multiset

Introduced: The Idea, by Hand Phase 1 · HW 8

Homework

← Builds on hash tables, sets and maps

Concluding topics

templates

A template is a recipe for code that works with many types; its template parameters stand for the types.

Also: generic code, template <typename T>, in instantiation of, template instantiation, ADL

Introduced: Function Templates Lesson 1

Lessons

Homework

⇄ Contrast with polymorphism↔ See also compile time vs. run time

templates and compilation

A template can't be compiled on its own, so its definition goes in a header, #included at the bottom of the declaring one.

Also: -private.hpp, why templates live in headers

Introduced: Compiling a Template? Templates and Compilation · Lesson 1

Lessons

Homework

← Builds on header files

typename

Put typename before a name like Vector<T>::iterator that depends on T and names a type; the compiler will tell you where.

Introduced: When to Add typename—The Practical View (practical view) Example: IntVector to Vector<T> · Lesson 1

Lessons

Homework

  • Adding typename (when typename is needed; C++20 relaxes it for return types) Phase 2 · HW 7

user-defined conversion

A single-argument constructor converts into a class; a type-cast operator converts out; explicit turns either off.

Also: explicit, operator bool, conversion constructor

Introduced: Conversion Into an Instance of Class (into a class: single-argument constructors) Classes Can Provide Type Conversion · Lesson 1

Lessons

⇄ Contrast with conversion

priority queues

Remove the most important item first: Insert, Get-Min and Pop-Min, with smaller keys meaning higher priority.

Also: PQ

Introduced: New Interface: Priority Queue Priority Queues · Lesson 1

Lessons

binary heaps

A complete binary tree where every key is no bigger than its children's, stored level by level in an array.

Also: min-heap, max-heap, sift up, sift down, float up, sink down, heap property

Introduced: Binary Heaps (structure and order properties) Lesson 1

Lessons

← Builds on tree terminology→ Leads to heapsort

heapify

Turn an arbitrary array into a heap by sinking items down from the back to the front: Θ(n), better than n inserts.

Introduced: Min-Heapify (Rough) Analysis (float up from the front vs. sink down from the back) Heapify · Lesson 1

Lessons

  • Conclusion (conclusion: sink down back to front, Theta(n)) Heapify · Lesson 1

heapsort

Max-heapify the array, then repeatedly pop the maximum into the freed end: O(n log n), the best possible worst case.

Also: sorting lower bound, std::sort

Introduced: <sc>Heap-Sort</sc> HeapSort · Lesson 1

Lessons

← Builds on binary heaps⇄ Contrast with quicksort

polymorphism

A function is polymorphic if a parameter accepts more than one type; C++ gives us templates, overloading and inheritance.

Also: subtype polymorphism

Introduced: What is Polymorphism? Lesson 2

Lessons

⇄ Contrast with templates

inheritance

A derived class gets its base class's members and is a subtype of it, usable wherever the base class is wanted.

Also: derived class, base class

Introduced: An Animal Base Class (base class and derived classes) Petting Zoo · Lesson 2

Lessons

→ Leads to dynamic dispatch, object slicing

dynamic dispatch

Choose the member function from the object's actual type at runtime, not the variable's declared type; ask for it with virtual.

Also: virtual, dynamic_cast, virtual function, vtable

Introduced: Dynamic Dispatch (static type vs. dynamic type) Lesson 2

Lessons

← Builds on inheritance⇄ Contrast with object slicing

object slicing

Copying a Cow into an Animal keeps only the Animal part, so the copy stops behaving like a Cow.

Also: slicing, sliced object, vector of base-class pointers, polymorphic storage

Introduced: Revisiting Our engageWith Function Using the Petting Zoo · Lesson 2

Lessons

← Builds on inheritance⇄ Contrast with dynamic dispatch

abstract classes

A class with a pure virtual function (= 0) can't have objects; one with nothing but pure virtuals is an interface class.

Also: pure virtual, interfaces

Introduced: Pure Virtual Member Functions Lesson 2

Lessons

choosing data structures

No data structure is best: pick the interface first, then weigh lookup patterns, variation, repeated lookups and space overhead.

Also: AVL tree, skip list, trie, Bloom filter, B-tree

Introduced: Which Interface? (pick an interface first) Spell Checker · Lesson 1

Lessons

Homework

Tools and practice

git and GitHub

git keeps every version of your files; GitHub hosts the shared copy. Clone once, then add, commit, push and pull.

Also: version control, commit, push

Introduced: A CS70 Horror Story (why version control) Version Control · Lesson 1

Lessons

Homework

Policies

Help Pages

→ Leads to merge conflicts↔ See also submitting your homework

cpplint

A style checker for Google's C++ style (with CS 70's tweaks); run it on homework to catch style problems.

Also: lint, linter, style checker, Google style guide

Introduced: But (In)Consistent With What? Style and Elegance · Lesson 2

Homework

Help Pages

  • Style (checking line length with cpplint) Grading Guidelines

← Builds on style and elegance↔ See also clang-format

Unix command line

The handful of shell commands you need on the server: pwd, ls, cd, cp, mv, rm (careful!), and Tab to complete.

Also: shell, terminal, CLI

Introduced: Log in and Configure Git (hostname, pwd, ls and exit) Connecting to the CS 70 Server · HW 0, Episode 2

Homework

Help Pages

Exploring the Terminal

→ Leads to the CS 70 server, setting up C++ on your own computer, redirection and pipes

Helix

The editor on the server: i to type, Escape to stop, :w to save, :q to leave. The mouse and arrow keys work.

Also: editor

Introduced: Meet Your Editor (running hx) Connecting to the CS 70 Server · HW 0, Episode 2

Homework

Help Pages

debugging

Find where your belief about the code is wrong: improve your evidence, check assumptions one at a time, and expand what you're certain of.

Also: gdb, debugger, asan

Introduced: Debugging Your Code

Lessons

Homework

Help Pages

Debugging Lab Activity

→ Leads to gdb↔ See also iterator validity, assert, Valgrind

Valgrind

Runs your compiled program under watch and reports memory errors and leaks, with line numbers if you compiled with -g.

Also: memcheck, leak check

Introduced: Using Valgrind to Find Memory Leaks

Homework

Help Pages

Arrays

← Builds on memory leaks⇄ Contrast with gdb, sanitizers↔ See also debugging

assert

A check that stops the program, naming file, line and condition, when something that must be true isn't. For your own bugs.

Introduced: Using assert in C++ Using Assertions

Homework

Help Pages

Debugging Lab Activity

↔ See also debugging

command-line arguments

main's argv holds the arguments, with argv[0] the program's own name; argc says how many.

Also: argc, argv

Introduced: Working With Command-Line Arguments

Homework

reading user input

cin >> x reads a word and getline(cin, s) a line; to read everything, get characters until EOF. End-of-file is not end-of-line.

Also: cin, getline

Introduced: Python Code (cin >> vs getline) A First Look at C++ · Lesson 1

Homework

Help Pages

Exploring the Terminal

→ Leads to reading and writing files, streams

lab setup

Log into a lab Mac as Guest, open Terminal, ssh to the CS 70 server; everything lives on the server, nothing on the lab Mac.

Introduced: How to Work on a Lab Machine Using Lab Machines

Help Pages

↔ See also setting up C++ on your own computer

the CS 70 server

Your own account on cs70.cs.hmc.edu, a shared Linux machine where everyone's compiler and libraries match; log in with ssh.

Also: ssh, cs70.cs.hmc.edu, log in, username, password, cs70-message

Introduced: Set Up Your CS 70 Server Account Connecting to the CS 70 Server · HW 0, Episode 2

Homework

← Builds on Unix command line↔ See also setting up C++ on your own computer

setting up C++ on your own computer

Install Clang and Git (plus gh, optionally Helix) on your own computer with Xcode tools, Homebrew, apt/dnf or MSYS2.

Also: install Clang, Homebrew, MSYS2, apt, dnf, xcode-select

Introduced: Setting Up Your Own C++ Development Environment Setting Up a C++ Development Environment · HW 1

Homework

← Builds on Unix command line↔ See also the CS 70 server, lab setup

the Turtle class and embroidery files

CS 70's Turtle class stitches embroidery (.dst) files; call save(), then watch them with dstterm.

Also: Turtle, libembroidery, .dst, dstterm, satin stitch, embroidery machine

Introduced: The Turtle Class Getting Started · HW 2

Homework

reading and writing files

An ifstream feeds a file into your program like cin: read with >> or getline, then check fail() and eof().

Also: ifstream, ofstream, fstream, read a file, eof, fail

Introduced: Reading text from files (ifstream and getline) Coding Part: More Fun With Fonts · HW 1

Homework

Help Pages

← Builds on streams, reading user input

streams

A stream is where characters come from or go to; << writes to whichever stream you were handed, so don't hard-code std::cout.

Also: cin, cout, cerr, stdin, stdout, stderr

Introduced: There are three streams, not two (standard error and the three streams) Exploring the Terminal · Lab Activities

Homework

Exploring the Terminal

← Builds on reading user input→ Leads to reading and writing files, redirection and pipes

redirection and pipes

< and > connect a program to files; a pipe `\

Also: <, >, |, 2>, 2>&1, pipe

Introduced: 5. Send a file in, and send the result somewhere (redirecting with < and >) Exploring the Terminal · Lab Activities

Help Pages

Exploring the Terminal

← Builds on Unix command line, streams

merge conflicts

When your changes and GitHub's touch the same lines, git writes both versions into the file; you edit, delete the markers, commit.

Also: conflict markers, <<<<<<< HEAD, Automatic merge failed, git merge --abort, git pull fails

Introduced: Merge Conflicts Git and GitHub

Help Pages

← Builds on git and GitHub

clang-format

clang-format -i *.cpp *.hpp reformats your code to the Google-based style; it fixes layout, not every cpplint complaint.

Also: formatter, auto-format, .clang-format, clang-format -i

Introduced: Formatting Your Code Check Your Submission · HW 6

Homework

← Builds on style and elegance↔ See also cpplint

the CS 70 testing library

affirm_expected, affirm and affirm_throws log failures with line numbers and keep going; TestingLogger::summarize reports.

Also: affirm, affirm_expected, affirm_throws, TestingLogger, log.summarize, test suite

Introduced: Writing Tests Using the CS 70 TestingLogger Library

Help Pages

  • affirm_expected (affirm_expected) Writing Tests Using the CS 70 TestingLogger Library
  • affirm (affirm) Writing Tests Using the CS 70 TestingLogger Library
  • affirm_throws (affirm_throws) Writing Tests Using the CS 70 TestingLogger Library
  • Wrapping Up with log.summarize() (log.summarize() and what main returns) Writing Tests Using the CS 70 TestingLogger Library

← Builds on testing

gdb

Run your program under a debugger: stop at breakpoints, step line by line (next, step), look at variables and the call stack (bt, f, p).

Also: GNU debugger, breakpoint, step, next, bt, run under a debugger

Introduced: Using GDB (The GNU Debugger) Using GDB

Help Pages

← Builds on debugging⇄ Contrast with Valgrind→ Leads to reading a backtrace

reading a backtrace

The chain of calls that led to a crash; skip the library frames and find the first function you wrote.

Also: stack trace, call stack, bt, where did it crash

Introduced: A CS 70 Grutoring Scenario Debugging Your Code

Help Pages

← Builds on the stack, gdb

sanitizers

Compile with -fsanitize=undefined,address,bounds and the program checks itself as it runs, catching bugs like out-of-bounds access.

Also: -fsanitize, AddressSanitizer, UBSan, ASan, bounds checking

Introduced: Step 8, Using the Sanitizer Arrays · Lab Activities

← Builds on undefined behavior⇄ Contrast with Valgrind

stubs

A stub has the right signature but throws "not yet implemented", so everything compiles and tests can run while you fill functions in.

Also: stub, function stub, not implemented, [[maybe_unused]], unused parameter, std::logic_error

Introduced: Create Stubs for Public Member Functions Stubs and Interface · HW 6

Homework

Help Pages

↔ See also compiler errors, testing, the development process

the development process

Plan with a picture, write tests first, implement, then test and fix; the planning image is checked for completeness, not correctness.

Also: TDD, test-driven development, planning image, tests first, incremental development, the four steps

Introduced: The Plan: Three Careful Steps Dynamic CoordVector · HW 4

Homework

← Builds on testing↔ See also stubs

(When logged in, completion status appears here.)