Class Format

• Each week you'll have lesson material to go through at your own pace.
• In class, you'll work on homework and check in with the professors.
• During each class meeting, fill out a check in form to get credit for the day.
• You may attend class on Zoom if it's best if you don't attend in person (e.g., if you have symptoms of illness).

Homework

• Except for the first one, you'll have a partner for all homework assignments.
• Each partnership will have one 24-hour extension to apply to a homework deadline.
• We want you to support and learn from your classmates: be careful to preserve each other's learning processes.

Proficiency Checks

• Each week there are four proficiency checks, each focused on a single learning objective.
• Take proficiency checks in exam-like conditions.
• There will be opportunities to retry proficiency checks where you did not demonstrate proficiency the first time.
• During finals week there will be a final try at all remaining proficiency checks (with the possibility of partial credit).

Getting the Most Out of CS 70

• We are here to help! Please reach out to the course staff—and to each other—early and often!

CS 70 Memory Diagrams

• We use memory diagrams to help trace the correctness of C++ code.
• In our diagrams, we draw a variable's
  • value "inside the box" since it exists at runtime.
  • name, type, and location "outside the box" because they are useful for tracing the code, but they are not explicitly represented in memory at runtime.
• Our model abstracts away other details of specific computers (such as registers, the specific size of different numeric types, and the real naming conventions for memory slots) because those details vary from one computer to another, and are not helpful for modeling correctness.

C++ Guiding Principles

• Programming languages are designed by particular people, for particular purposes, in particular contexts.
• We discussed two principles that are important for explaining some of the design choices in C++ and let us reason about how the language behaves.
  • The Zero-Overhead Principle: Don't slow programs down “needlessly”.
    • Providing a lanuage feature should never slow down a program that doesn't use that feature.
    • Generally do things in the quickest possible way (even at the expense of safety or convenience).
  • The “Power to the People” Principle: Provide language features that allow expert programmers to do things in unsual ways.
    • Sometimes beginners accidentally use featues intended for experts!
• Both of these features mean we should not ignore compiler warnings when it notices we're doing something questionable!

Object Lifetime

• Every variable goes through the same 5 phases of object lifetime.
• The space for a local variable is allocated at the opening curly brace of the function where it's declared.
• The value of a variable is initialized on the line with its declaration.
• Once a variable's value is initialized, it is in use. For primitive values, that primarily means that its name is in scope, which means the name can be used in other expressions.
• The value of a variable is destroyed at the closing curly brace of the declaring block.
• Once a variable's value is destroyed, it is no longer in use. For primitive values, that primarily means that its name is out of scope, which means that the name cannot be used in other expressions.
• The space for a local variable is deallocated at the closing curly brace of the function where it's declared.

Numeric Types

• Numeric values in C++ can either be floating point (able to hold non-integer parts, like decimals) or integers (only able to hold integer values).
• Integer values in C++ can either be signed (able to hold positive and negative values) or unsigned (only able to hold non-negative values).
• Types like booleans and characters are numeric types in C++. A boolean, for example, is an integer type that is guaranteed to be able to hold two values.

Numeric Promotion and Conversion

• If a floating point is used where an integer type is needed, that is always conversion since the non-integer part of the value may be lost.
• If an integer type is used where a floating point is needed, that is always conversion since there may not be enough bits allocated to storing the integer part of the value.
• If a signed value is used where unsigned type is needed, that is always conversion since negative values cannot be correctly represented.
• If an unsigned value is used as a signed type of the same size is needed, that is always conversion since there may not be enough bits allocated to storing the magnitude of the value.
• If a value from a larger numeric type is used where a smaller numeric type is needed, that is always conversion since there may not be enough bits to store the value.
• If a value from a smaller numeric type is used as a larger numeric type of the same signedness is needed, that is always promotion since there will definitely be enough bits to store the value.

Compilation

• All of the C++ code we write will go through the following steps:
  • First, the compiler changes source code in to assembly code.
  • Next, the assembler changes the assembly code into object code.
  • Finally, the linker changes the object code into machine code.
• The compiler deals with all of the parts of variables that are not actually stored in memory at run time.
  • Specifically, that means that errors related to a variable's type or name will be caught at compile time!
• The (simplest) commands to compile a source file myprogram.cpp into an executable named myprogram and then run that program are
  • clang++ -c myprogram.cpp (compilation and assembly)
  • clang++ myprogram.o -o myprogram (linking)
  • ./myprogram (running the program)
• (In the homework we will typically have additional command-line options.)

Version Control

• A version control tool lets us keep track of all the different versions of our files, without having them clutter up our workspace.
• The version-control tool you will use this semester is called git.
• We also use a website called GitHub to have a shared, web-accessible place to put copies of everyone's repositories.

Pair Programming

• Pair programming is a skill. Like any skill, it requires practice and intention to get better.
• Our job this semester, collectively, is to support each other in developing that skill!

Arrays of Primitives

• Arrays are
  • Fixed-size — Once they're created, we can't change their size.
  • Homogenous — All of the elements in them have to be the same type.
  • Contiguous — If we looked at an array in memory, we'd see all of the elements side by side.
  • Ordered — We can talk about what the first, third, or forty-second element of the array is.
• Arrays allow constant-time access: We can jump straight to an arbitrary element of the array.
• In terms of object lifetime, arrays act just like individual variables. The compiler needs to know ahead of time how big the array will be, so that it can write the instructions to allocate enough space to store the array.
  • Declare and initialize an array: int arr[3]{1, 2, 3};
  • Usage: To access the item at index i: arr[i]
    • arr[i] is translated to *(arr + i)
    • *x means the value in memory at the address given by x
    • arr + i means the address at an offset of i from the address given by arr
    • So *(arr + i) means the value in memory at the address of the item at offset i from the start of the array.
  • Destruction and deallocation:
    • When the array is destroyed, each item is destroyed.
    • When the array is deallocated, all items are deallocated.
• Accessing an array out-of-bounds causes undefined behavior.
  • Undefined behavior means your program has gone off the rails, anything could happen, from something catastrophic to everything seeming to work.
  • You should never write a program that you know has undefined behavior just because nothing bad happened when you tested it.
• Typical C++ compilers generate code that does things the fastest and easiest way, without any special safety checks.
  • That includes finding the place in memory where we're claiming an item should be and interpreting the bits at that location as being of the appropriate type (that you asked for).
  • Accessing an array out-of-bounds can cause strange behavior. While, in principle, anything can happen when code causes undefined behavior, the strange behaviors you might see can vary between systems. But you can learn to recognize problematic behaviors, especially on the systems you use for coding and testing.
• Accessing memory that is way out-of-bounds can cause your program to crash.
  • The operating system will not allow your program to access memory outside of its allotted region.
  • This error is called a segmentation fault (segfault for short).

Code Style

• The goal of our code should always be to explain our thinking to other people who read the code.
• Similar things should look similar and different things should look different.

Testing

• When we write tests for our code, our goal should be to reveal bugs, not just demonstrate that our code "works".
• When you write tests, think about what edge cases you need to consider to make sure that your implementation is correct.
• If you make a mistake in your own code that results in "wrong" behavior, write a test for it! While we encourage test-first development, you can always add to your tests to make them more thorough as you develop a deeper understanding of where the tricky parts are in a particular coding task.

• We split our code into multiple files to avoid code duplication.
• A multifile program contains:
  • One or more source files (.cpp), exactly one of which has a main function.
  • One or more header files (.hpp), which declare functions that are defined in the source files (.cpp).

• Make sure that every header file (.hpp) has an include guard.

  #ifndef FILENAME_HPP_INCLUDED
  #define FILENAME_HPP_INCLUDED
  
  ...stuff...
  
  #endif
  

  • Include guards prevent multiple definitions when a header file is included more than once in the same source file.
  • Each preprocessor macro we use for an include guard must be unique (otherwise multiple files will be trying to use the same guard and only one of them will be seen), which is why we usually use the filename as part of the name.

• Make sure that each file uses #include to include any header files (.hpp) that declare things it uses.

  • That often includes a source file's own header file!
  • Sometimes header files need to include other header files!
  • Use #include "filename" for your local files from the current directory.
  • Use #include <filename> for system include files
• To compile your project:
  • Compile each source file (.cpp) into an object file (.o) using clang++ -c filename.cpp.
    • In practice, you'll probably want other flags too, such as -std=c++17, -g and -Wall -Wextra -pedantic.
    • (Remember from last week that this phase includes preprocessing, compiling the source file into assembly code, and then assembling the assembly code into machine code.)
  • Link object files (.o) together into an executable using clang++ -o executableName file1.o file2.o ...
• To recompile:
  • If a source file (.cpp) changes, recompile it into an object file (.o) and relink as necessary.
  • If a header file (.hpp) changes, recompile all source files that include it or that include a file that includes it, and so on.
• Rules of thumb:
  • Don't compile a header file (.hpp).
  • Don't #include a source file (.cpp).

• A variable with a reference type (e.g., int&) is just another name for an existing variable (in this case an int).
• An important use of references is as function parameters:
  • Allows the function to alter data outside of its stack frame.
  • Prevents unnecessary copy operations.
• The const keyword specifies that changes are prohibited (i.e., we have read-only access to the data).
  • The const keyword affects what we are allowed to do via a particular name, not what others might be able to do via a different name, so the same piece of data can have const names that cannot be used to change it and non-const names that can.
  • You cannot initialize a non-const reference (e.g., of type int&) with a const name (e.g., of type const int). That would circumvent the const restriction!
  • A const-reference function parameter is a good way to avoid needless copying but still promise not to change the given argument.

Recap Video

There was a fair amount to digest in this lesson. As a review, and because sometimes it's helpful to see things presented a different way, here's a video that goes over what we've covered in this lesson. If you feel like you've already mastered the material, you can skip it.

Key Points

• Classes are conceptually similar to what you've seen before, but have syntactic/terminological differences.
• Instead of “instance variables” and “methods” we say “member variables” or “data members” and “member functions” (“members” to refer to them all together).
• Declarations/definitions
  • The class definition goes in the header file (.hpp). It declares all of the class members.
    • In CS 70 convention we name all member variables with a trailing underscore (e.g., age_).
  • The member-function definitions go in the source file (.cpp). They specify the instructions for each function.
  • When we define a member function we have to specify which class it belongs to using the scope-resolution operator (::):
    • For example, void Cow::moo(int numMoos);.
• A member function can be declared const.
  • A const member function promises not to change the values of member variables.
  • If you have a const object, you can only call const member functions on it.
• We looked at two different kinds of constructors:
  1. Parameterized constructors take parameters and must be invoked explicitly (e.g., Cow bessie{3, 12}).
  2. Default constructors take no parameters and are implicitly invoked for default initialization (e.g., Sheep fluffy;).
• You can disable the use of a default constructor using the delete keyword (e.g., Cow() = delete;).
• In a constructor, the member-initialization list specifies how to initialize each member variable.
  • For example, Cow(int numSpots, int age) : numSpots_{numSpots}, age_{age}.
  • In CS 70, you must use a member-initialization list whenever possible. (The only exception is initializing a primitive array when you want a copy of another array—for that case, you need to loop over the elements of the array you're copying to populate your new array.)
• A class definition ends in a semicolon (;).
  • A class definition ends in a semicolon.
  • A class definition ends in a semicolon.

• Object lifetime on the stack: when?
  • Allocation: at the opening { of the function
  • Initialization: at the declaring line
  • Use: between initialization and destruction
  • Destruction: at the closing } of the declaring block
  • Deallocation: at the closing } of the function
• Default initialization/construction
  • int x;
  • Cow mabel;
  • Cow bessie{};
  • For an object, invokes the default (parameterless) constructor
• Copy initialization/construction
  • Creates a new object that is a copy of an exiting object
  • int x = y;
  • int a{b};
  • Cow mabel = adeline;
  • Cow bessie{fennel};
  • For an object, invokes the default constructor (which takes a reference to an object of the same type)
  • Also used to initialize function parameters and return values
• Assignment operator
  • Changes an existing object to be a duplicate of another existing object
  • s = t;
  • cadewyn = ethyl;
  • For an object, invokes the assignment operator, a special member function called operator=.
• Destructor
  • A special member function that is automatically invoked when an object is destroyed
  • For class Cow, the destructor is named ~Cow
  • Typically used to “clean up” or release any resources the object is holding onto
• The compiler can synthesize or disable these functions:
  • Cow(); // Means that the programmer will define the default constructor
  • Cow() = default; // Means that we will use the compiler's synthesized default constructor
  • Cow() = delete; // Means that this class does not have a default constructor
  • Same for default constructor, copy constructor, assignment operator, and destructor (but don't disable the destructor!!)
• For arrays, the same as above, only \( N \) times, where \( N \) is the size of the array.
• For references, initialization and destruction mark the usage period of the name
  • We don't model any allocation or deallocation for references
• For data members of a class
  • Allocation happens when the object is allocated
  • Initialization happens before the opening { of the constructor (so use the member-initialization list!)
  • Destruction happens at the closing } of the destructor
  • Deallocation happens when the object is deallocated

Pointers in General

• Pointers are a kind of value that represents the memory address of a value of a particular type.
  • Example: int* x means that x will hold a pointer to an int. A pointer to an int (a.k.a. "int pointer") is the address of a piece of memory that purports to contain an int.
  • We can access the data a pointer points to by following it using the indirection operator: *x is another name for the data that x points to.
    • Note: Sometimes people with a C background say "dereference" instead of "follow" (and call * "the dereference operator"). That term is a bit less clear, especially given that it has nothing to do with C++ references. We're trying hard to stick to the C++ terminology in this class (although we might slip up occasionally!).
  • We can read types involving pointers (and more) using the inside-out rule.
• Pointers are primitive types in C++.
  • There are infinitely many pointer types, because for every (non-reference) type, we can add a * to the end of the type to create a pointer for that type.
  • Pointers support const for setting read-only status. We can use const on the pointer itself, the value the pointer points to, or both.
  • If we let a pointer be default initialized, it will point to an indeterminate value. (From a "did you follow the rules" perspective, a default-initialized pointer is invalid and inappropriate to follow; doing so leads to undefined behavior.)
• Pointers are useful!
  • We can pass arrays into functions using pointers, with either
    • A first-element pointer and a size; or
    • A first-element pointer and a past-the-end pointer (which is C++'s preferred way).
  • We can also use pointers to avoid moving or copying data, by rearranging the pointers-to-data rather than rearranging the data itself.
• Every piece of data has a memory address.
  • We can get the address of a variable using the address-of operator: &.
  • Example: if we have int x, then &x is the address of x.
  • (Not to be confused with & as part of a type: int& r is a reference to an int, not the address of the int.)
  • We almost never need to use the address-of operator.

Pointers and Instances of Classes

• In a member function, this is a pointer to the object that the member function was invoked on.
  • We almost never need to use this; when we do, it's usually as *this.
• If we have a pointer to an instance of a class, there are two ways to access the members of the object:
  • Follow the pointer, then access: (*myObj).myMemberFunction();
  • Follow and access together (preferred): myObj->myMemberFunction();

• The heap is a region of memory for things that we explicitly allocate and deallocate when we want to.
  • The new keyword allocates space, initializes the data, and returns the address of the new data.
    • Allocate one thing: int* p = new int{42};.
    • Allocate an array of things: int* arr = new int[42]; // arr is a pointer to the first element.
  • The delete keyword takes the address of something on the heap, destroys the data, and deallocates that chunk of memory.
    • Delete one thing: delete p;.
    • Delete an array of things: delete[] arr;.
    • All variants of delete can only be given pointers to heap memory that came from new. You can't delete anything else (other memory, parts of things, etc.).
  • Every call to new should have a matching call to delete later on.
    • Non-arrays allocated with new should have be deallocated with delete
    • Arrays allocated with new ... [] should be deallocated with delete[] ....
    • Don't call the wrong one!
• Types of allocation:
  • Static allocation: memory that is allocated for the entire duration of the program (e.g. a static member variable).
  • Automatic allocation: memory allocated on the stack (because it is allocated/deallocated automatically when functions begin/end).
  • Dynamic allocation: memory allocated on the heap (because the size of the allocation is "dynamically" determined at runtime as opposed to compile time).
• A memory leak is when something is allocated on the heap and becomes inaccessible (all pointers/references to it are destroyed).
  • In our memory model, leaks look like data on the heap with no valid name.
  • Once memory has been leaked, the program can't deallocate it!
  • Prevent memory leaks:
    • For every new that occurs during the program, there must also be exactly one delete.
    • When you use new, consider also writing the corresponding delete statement wherever it will need to be.
• Other common memory-management errors:
  • Double delete: Trying to delete the same data twice.
    • Most commonly caused by using delete on two pointers that both point to the same data.
  • Dangling pointer: Following a pointer to memory that has been deallocated.
    • Most commonly caused by continuing to use a pointer after the thing it points to has been deleted.

• Sometimes a class needs to manage memory on the heap.
  • We allocate that memory using new, either in its constructor(s) or in other member functions. The new operation
    • Allocates memory on the heap (requesting it from the system's heap manager).
    • Constructs the object (or objects) in that space.
    • Returns a pointer to the memory. We'll need to eventually give this pointer to the appropriate delete.
  • Our classes own their resources, therefore the class also owns the memory it allocates on the heap—in other words, it's responsible for that memory.
    • In our classes, ownership is exclusive. If two objects both think they own the same data, it's a bug.
• A class's destructor must release all memory in the heap that the object is responsible for.
  • The synthesized destructor will simply destroy each data member of an instance of a class.
  • If a data member is a pointer that is storing the location of memory on the heap, that memory will not be destroyed and deallocated when the pointer is destroyed.
  • Failing to deallocate heap memory that our object is responsible for can cause memory leaks, where an object is gone, but the dynamically allocated data that it owned is still occupying memory but is inaccessible.
  • We release heap memory via a delete statement, which
    • Takes a pointer (that came from new).
    • Destroys the object at that memory address.
    • Deallocates the memory (giving it back to the system's heap manager).
• A class's copy constructor should be sure to create a deep copy by allocating new heap memory for a new instance of a class.
  • The synthesized copy constructor will simply copy initialize or construct each data member (shallow copy).
  • If one of the data members is a pointer to heap memory, then two objects will both point to the same heap memory!
  • This situation can cause all kinds of trouble, including double-delete errors, if they both objects try to delete that memory.
• A class's assignment operator should be sure to clean up "old" memory in an instance of a class, then allocate new heap memory for the new configuration of the class instance.
  • The copy-and-swap idiom is a clever/elegant way to do this.
  • A less elegant but more direct way is to first use code from the destructor, then use code from the copy constructor.
• Alternatively, if we don't think a copy constructor or assignment operator is needed, we can instead choose not to provide them. (Or, during development we can disable them, and then write them last once everything else is done.)

• There are lvalues and rvalues:
  • In x = y + z, x is an lvalue and y + z is an rvalue.
  • lvalues have an obvious memory location and significant lifetime; they often have a name.
  • rvalues are temporary values that exist for the duration of one line of code; they often don't have names.
• Every function call that returns a value is actually initializing a new object in memory
• The compiler allocates temporary objects (rvalues) as needed (e.g., to hold intermediate results in nested expressions).
• Functions can return references.
• We can overload functions (i.e., define multiple functions with the same name that operate on different sets of arguments).
  • C++ uses the types of the arguments of the function to figure out which function we mean to call. If selecting the best function for a particular set of arguments is ambiguous, it's an compile-time error.
  • We can implement our own versions of C++'s existing operators for our own types, so we can make our types feel “built in”.

Iterators

• An iterator is an object that represents a “location” in a collection (a.k.a. container).

  • It can get/set the item at that location, and move forward to the next location.
  • Provides a unified interface for iteration in lots of data structures.
  • Allows a data structure to define the best way to iterate through its items.

• Other languages also have iterators, so they are a general concept; not C++ specific.

• C++'s iterators are inspired by the begin/past-the-end scheme for iterating over an array.

• In the C++ standard library, a container provides the following functions:

  • begin—returns an iterator to the first item, and
  • end—returns an iterator "one past" the last item.
    • We use the end iterator to know when we've gone too far in a loop!
  • It must be the case that…
    • If i is an iterator to the last item in c, then ++i == c.end(), and
    • A container c is empty if and only if c.begin() == c.end().

• In the C++ standard library, an iterator offers the following operations:

• *iter — returns a reference to the item at the iterator's location.

  • ++iter — advances the iterator to the next location.
  • iter != otherIter — returns true if the two iterators are not at the same location.

• "Iterator" is not another word for "pointer".

  • Both iterators and pointers abstractly represent a concept of “location” and allow access to the data at a location.
  • A pointer is the iterator type for a primitive array.
  • An iterator might have a pointer as a member to help it do its job.
  • But an iterator object has data and member functions, whereas a pointer is just a primitive type representing a memory address.

• Common idioms for looping through a collection using an iterator:

  for (std::vector<int>::iterator iter = vec.begin(); iter != vec.end(); ++iter) {
      std::cout << *iter << std::endl;
  }
  

  or

  for (auto iter = vec.begin(); iter != vec.end(); ++iter) {
      std::cout << *iter << std::endl;
  }
  

  or

  for (int x : vec) {
      std::cout << x << std::endl;
  }
  

• Read-only iterators are a distinct type where operator* returns a const reference rather than a non-const reference. They're usually called const_iterator rather than iterator.

C++'s Sequence Containers

We also learned about std::vector and std::list in C++'s standard library. They are both examples of sequence containers (a.k.a. lists), and they're both generic in that they can hold a type of our choosing.

• std::list<T> is a doubly linked list with list items of type T.
• std::vector<T> is an array-backed list with array elements items of type T and automatic resizing.

Both are full-featured list objects, with useful member functions well-suited to their underlying representations (a.k.a. encodings).

Empirical timing

• Tells you how long a program actually took, which is great.
• But the findings are specific to the experimental conditions (compiler options, computer, inputs tested, etc.).
• So we have to be careful how we extrapolate the findings to other conditions.

Operation counting

• Give the number of times a particular operation (or set of operations) occur as a function of some aspect of the input.
• Abstracts away all system-level issues (compiler, CPU, etc.)
• Allows us to weigh trade-offs in constant factors and lower-order terms.
• Requires us to make choices about what to count and what to account for in the input.
• Can be unnecessarily tedious/detailed for some questions.

Asymptotic analysis

• Answers the question “How well does this algorithm scale?” (e.g., what happens if we double the input size)
  • Technically, is focused on how the cost grows as the size of the input goes to infinity.
    • As a result we ignore constant factors and lower-order terms.
    • In practice conclusions about how costs grow are usually applicable to merely “large” sizes, not just infinite ones.
• Must useful when costs are fundamentally different (e.g., \(\Theta(n\) vs \(\Theta(n^2\)) rather than when they appear the same.
• \(f(n) \in \Theta(g(n))\) means that \(f\) and \(g\) are asymptotically similar.
  • \(f(n) \in \Theta(g(n))\) if and only if 0 < \(\lim_{n\rightarrow \infty} \frac{f(n)}{g(n)} < \infty\)
• Usually we compare a cost function to simple reference functions, sometimes called orders of complexity:
  • \(\Theta(1)\) — constant time
  • \(\Theta(\log n)\) — logarithmic time
  • \(\Theta(n)\) — linear time
  • \(\Theta(n \log n)\) — linearithmic time
  • \(\Theta(n^2)\) — quadratic time
  • etc.
• \(f(n) \in \textrm{O}(g(n))\) means that \(f\) is "no worse than" \(g\) in an asymptotic sense.
  • \(f(n) \in \textrm{O}(g(n))\) if and only if \(\lim_{n\rightarrow \infty} \frac{f(n)}{g(n)} < \infty\)
  • Example usage:
    • "In the worst case the complexity is \(\Theta(n)\) and in the best case it is \(\Theta(1)\), so the complexity is \(O(n)\)."
• The asymptotic notation family:
  • \(f(n) \in \textrm{o}(g(n))\), kind of like \(x < y\).
  • \(f(n) \in \textrm{O}(g(n))\), kind of like \(x \le y\).
  • \(f(n) \in \Theta(g(n))\), kind of like \(x = y\).
  • \(f(n) \in \Omega(g(n))\), kind of like \(x \ge y\).
  • \(f(n) \in \omega(g(n))\), kind of like \(x > y\).

Best case analysis

• What is the smallest number of operations for an input of size \(n\)?

Worst case analysis

• What is the largest number of operations for an input of size \(n\)?

Expected case analysis

• What is a "typical" number of operations?
• Three steps:
  • Break the outcomes into cases so that each case has the same complexity
  • Assign probabilities to the cases
    • Usually we assume a probability model that we think will help us understand the algorithm in practice.
    • A very common probability model is the "uniform probability" model which assumes every case is equally likely.
  • Find the expected complexity
    • A weighted sum of the complexities of the cases, weighted by probability.
    • \(\sum_{k} Pr(\textrm{Case}\ k)\textit{Cost}(\textrm{Case}\ k)\)

Levels of a Data-Structure Specification

• Interface: the operations it offers
• In C++, the public members of a class
  • Encoding: the data the structure uses to do its job
    • In C++, the private members of a class
  • Implementation: the actual procedures that manipulate the data to satisfy the interface promises
    • In C++, the member-variable definitions of a class

Multiple Encodings for the List Interface

• Array-backed lists
  • Contents stored in an array, which resizes as necessary
  • Good at random access
  • Bad at inserting/removing at or near the start of the list
• Linked lists
  • Contents in list nodes, linked in a chain
  • Good at inserting/removing at beginning
  • Bad at random access

Iterators

Iterator Misuse: Obey These Rules

• Don't use * on a past-the-end iterator.
• Don't use ++ on a past-the-end iterator.
• Don't use -- on an iterator at the beginning (there is no such thing as a before-the-beginning iterator).
• Don't do anything to an iterator that isn't valid other than destroy it or assign a new value to it.
• Don't compare iterators from different origins.

Valid and Invalid Iterators

The interface for a data structure gives rules for when iterators will stay valid and when they will cease to be valid.

• Universally applicable reasons an iterator would be valid but not refer to an item (we can't call ++ or * on these iterators, but we can test them against other iterators from the same origin):

  • The iterator was default constructed, rather than initialized with a valid value.
  • The iterator is past the end.

• Universally applicable reasons an iterator would be not be valid:

  • The underlying container is destroyed/deallocated.

• Container-specific iterator validity rules

  • For containers with an erase member function, eraseing the item referred to by an iterator means that the iterator passed to erase is no longer valid, and also that any and all other iterators referring to the erased location are no longer valid.
  • Sequence data structures based on arrays typically don't promise that iterators will continue to be valid after an item is added or removed (so the data structure can resize the array, which moves all of its data to somewhere else in memory when it copies the array).
  • In contrast, sequence data structures based on linked lists typically do preserve iterators as much as possible, except for iterators that refer to items that have been removed.