1 Goals for today’s reviewCSE 332 Midterm Review Goals for today’s review Review and summary of material in course so far A chance to clarify and review key concepts/examples Discuss details about the midterm exam Thursday March 23rd, 7-9 PM. Room details on Piazza Notes on only 1 side of an 8.5”x11” page will be allowed All electronics must be off, including cell phones, etc. Recommendations for exam preparation Catch up on any studios/readings you’ve not done Write up your notes page as you study Ask questions here as you have them today
2 What Goes Into a C++ Program?Declarations: data types, function signatures, classes Allows the compiler to check for type safety, correct syntax Usually kept in “header” (.h) files Included as needed by other files (to keep compiler happy) class Simple { typedef unsigned int UINT32; public: Simple (int i); int usage (char * program_name); void print_i (); private: struct Point2D { int i_; double x_; }; double y_; }; Definitions: static variable initialization, function implementation The part that turns into an executable program Usually kept in “source” (.cpp) files void Simple::print_i () { cout << “i_ is ” << i_ << endl; } Directives: tell compiler (or precompiler) to do something More on this later
3 Lifecycle of a C++ Programxterm An “IDE” window console/terminal/window Makefile WebCAT make turnin/checkin “make” utility Runtime/utility libraries (binary) .lib .a .dll .so Eclipse compile link Visual Studio C++ source code Programmer (you) debugger precompiler gcc, etc. link compiler linker executable program compiler object code (binary, one per compilation unit) .o
4 What’s a Pointer? A variable holding an address Can be untypedOf what it “points to” in memory Can be untyped E.g., void * v; // points to anything However, usually they’re typed Checked by compiler Can only be assigned addresses of variables of type to which it can point E.g., int * p; // only points to int Can point to nothing E.g., p = 0; // or p = nullptr; (C++11) Can change where it points As long as pointer itself isn’t const E.g., p = &i; // now points to i int i 7 0x7fffdad0 int *p
5 What’s a Reference? Also a variable holding an addressOf what it “refers to” in memory But with a nicer interface A more direct alias for the object Hides indirection from programmers Must be typed Checked by compiler Again can only refer to the type with which it was declared E.g., int & r =i; // refers to int i Always refers to (same) something Must initialize to refer to a variable Can’t change what it aliases int i 7 0x7fffdad0 int & r
6 Const Pointers and Pointers to ConstRead declarations right to left Make promises via the const keyword in pointer declaration: not to change where the pointer points not to change value at the location to which it points Can (only) change Where w points and the value at the location to which it points The value at the location to which x points Where y points A pointer to non-const cannot point to a const variable neither w nor x can point to i any of them can point to j int main (int argc, char **argv) { const int i = 0; int j = 1; int k = 2; // pointer to int int * w = & j; // (array names are like const // pointers to their 0th position) // const pointer to int int * const x = & j; // pointer to const int const int * y = & i; // const pointer to const int const int * const z = & j; }
7 Rules for Pointer ArithmeticYou can subtract (but not add, multiply, etc.) pointers Gives an integer with the distance between them You can add/subtract an integer to/from a pointer E.g., p+(q-p)/2 is allowed but (p+q)/2 gives an error Note relationship between array and pointer arithmetic Given pointer p and integer n, the expressions p[n] and *(p+n) are both allowed and mean the same thing int main (int argc, char **argv) { int arr [3] = {0, 1, 2}; int * p = & arr[0]; int * q = p + 1; return 0; } int arr [3] 1 2 0xefffdad0 0xefffdad0 int *p int *q
8 Expressions: Operators and OperandsOperators obey arity, associativity, and precedence int result = 2 * 3 + 5; // assigns 11 Operators are often overloaded for different types string name = first + last; // concatenation An lvalue gives a location; an rvalue gives a value Left hand side of an assignment must be an lvalue Prefix increment and decrement take and produce lvalues Posfix versions (and &) take lvalues, produce rvalues Beware accidentally using the “future equivalence” operator, e.g., if (i = j) instead of if (i == j) Avoid type conversions if you can, and only use named casts (if you must explicitly convert types)
9 C++ Statements In C++ statements are basic units of executionEach ends with ; (can use expressions to compute values) Statements introduce scopes, e.g., of (temporary) variables A (useful) statement usually has a side effect Stores a value for future use: j = i + 5; Performs input or output: cout << j << endl; Directs control flow: if (j > 0) {…} else {…} Interrupts control flow: throw out_of_range; Resumes control flow: catch (RangeError &re) {…} goto considered too low-level Usually better to use break or continue If you have to use goto, you must comment why
10 C++ Exceptions Interrupt Control FlowNormal program control flow is halted At the point where an exception is thrown The program call stack “unwinds” Stack frame of each function in call chain “pops” Variables in each popped frame are destroyed This goes on until a matching try/catch scope is reached Control passes to first matching catch block Can handle the exception and continue from there Can free some resources and re-throw exception
11 Details About Catching Exceptions in C++Control jumps to first matching catch block Order matters if multiple possible matches Especially with inheritance-related exception classes Put more specific catch blocks before more general ones Put catch blocks for more derived exception classes before catch blocks for their respective base classes try { // can throw exceptions } catch (Derived &d) { // Do something } catch (Base &d) { // Do something else } catch (...) { // Catch everything else }
12 More About Catching Exceptions in C++“Catch-all” handler, catches any type Often should at least free resources, generate an error message, etc. May rethrow exception for another handler to catch and do more throw; As of C++11 standard, rethrows a caught exception (very useful in Catch-all handlers ) try { // can throw exceptions } catch (Derived &d) { // Do something } catch (Base &d) { // Do something else } catch (...) { // Catch anything else, // do as much as you can throw; // rethrows it }
13 How Function Calls WorkA function call uses the “program call stack” Stack frame is “pushed” when the call is made Execution jumps to the function’s code block Function’s code block is executed Execution returns to just after where call was made Stack frame is “popped” (variables in it destroyed) This incurs a (small) performance cost Copying arguments, other info into the stack frame Stack frame management Copying function result back out of the stack frame
14 Pass By Value void foo () { int i = 7; baz (i); } void baz (int j)local variable i (stays 7) Think of this as declaration with initialization, along the lines of: int j = what baz was passed; parameter variable j (initialized with the value passed to baz, and then is assigned the value 3) 7 → 3
15 Pass By Reference void foo () { int i = 7; baz (i); }again declaration with initialization int & j = what baz was passed; void foo () { int i = 7; baz (i); } void baz (int & j) j = 3; 7 → 3 local variable i j is initialized to refer to the variable that was passed to baz: when j is assigned 3, the passed variable is assigned 3. 7 → 3 argument variable j
16 Structure of a Simple C++ Class Declarationclass Date { public: // member functions, visible outside the class Date (); // default constructor Date (const Date &); // copy constructor Date (int d, int m, int y); // another constructor virtual ~Date (); // (virtual) destructor Date & operator= (const Date &); // assignment operator int d () const; int m () const; int y () const; // accessors void d (int); void m (int); void y (int); // mutators string yyyymmdd () const; // generate a formatted string private: // member variables, visible only within functions above int d_; int m_; int y_; }; The compiler defines these 4 if you don’t* operators can be member functions as well *Compiler omits default constructor if any constructor is declared
17 Constructors A constructor has the same name as its classclass Date { public: Date (); Date (const Date &); Date (int d, int m, int y); // ... private: int d_, m_, y_; }; // default constructor Date::Date () : d_(0), m_(0), y_(0) {} // copy constructor Date::Date (const Date &d) : d_(d.d_), m_(d.m_), y_(d.y_) // another constructor Date::Date (int d, int m, int y) : d_(d), m_(m), y_(y) A constructor has the same name as its class Establishes invariants for the class instances (objects) Properties that always hold Like, no memory leaks Passed parameters are used in the base class /member initialization list You must initialize const and reference members there Members are constructed in the order they were declared List should follow that order Set up invariants before the constructor body is run Help avoid/fix constructor failure More on this topic later base class / member initialization list constructor body
18 Access Control Declaring access control scopes within a classprivate: visible only within the class protected: also visible within derived classes (more later) public: visible everywhere Access control in a class is private by default but, it’s better style to label access control explicitly A struct is the same as a class, except Access control for a struct is public by default Usually used for things that are “mostly data” E.g., if initialization and deep copy only, may suggest using a struct Versus classes, which are expected to have both data and some form of non-trivial behavior E.g., if reference counting, etc. probably want to use a class
19 Friend Declarations Offer a limited way to open up class encapsulationC++ allows a class to declare its “friends” Give access to specific classes or functions A “controlled violation of encapsulation” Keyword friend is used in class declaration Properties of the friend relation in C++ Friendship gives complete access Friend methods/functions behave like class members public, protected, private scopes are all accessible by friends Friendship is asymmetric and voluntary A class gets to say what friends it has (giving permission to them) But one cannot “force friendship” on a class from outside it Friendship is not inherited Specific friend relationships must be declared by each class “Your parents’ friends are not necessarily your friends”
20 Friends Example Class declares operator<< as a friend// in Foo.h class Foo { friend ostream &operator<<(ostream &out, const Foo &f); public: Foo(int) {} ~Foo() {} private: int baz; }; ostream &operator<<(ostream &out, const Foo &f); // in Foo.cpp ostream &operator<<(ostream &out, const Foo &f) { out << f.baz; // f.baz is private so need to be friended return out; } Class declares operator<< as a friend Notice operator<< is not a member of class Foo Gives it access to member variable baz Can now print Foo like a built-in type Foo foo; cout << foo << endl;
21 Flushing Streams (and Stream Manipulators)An output stream may hold onto data for a while, internally E.g., writing chunks of text rather than a character at a time is efficient When it writes data out (e.g., to a file, the terminal window, etc.) is entirely up to the stream, unless you tell it to flush out its buffers If a program crashes, any un-flushed stream data is lost Terminal output & files are as of last flush, not as of where it crashed So, flushing streams reasonably often is an excellent debugging trick Can tie an input stream directly to an output stream Output stream is then flushed by call to input stream extraction operator E.g., my_istream.tie(&my_ostream); cout is already tied to cin (useful for prompting the user, getting input) Also can flush streams directly using stream manipulators E.g., cout << flush; or cout << endl; or cout << unitbuf; Other stream manipulators are useful for formatting streams Field layout: setwidth, setprecision, etc. Display notation: oct, hex, dec, boolalpha, noboolalpha, scientific, etc.
22 A Few More Details About StreamsCannot copy or assign stream objects Copy construction or assignment syntax using them results in a compile-time error Extraction operator consumes data from input stream “Destructive read” that reads a different element each time Use a variable if you want to read same value repeatedly Need to test streams’ condition states E.g., calling the is_open method on a file stream E.g., use the stream object in a while or if test Insertion and extraction operators return a reference to a stream object, so can test them too File stream destructor calls close automatically
23 Containers’ IteratorsIterators generalize different uses of pointers Most importantly, define left-inclusive intervals over the ranges of elements in a container [begin, end) Interface between algorithms and data structures Algorithm manipulates iterators, not containers An iterator’s value can represent 3 kinds of states: dereferencable (points to a valid location in a range) past the end (points just past last valid location in a range) singular (points to nothing) What’s an example of a pointer in each of these states? Can construct, compare, copy, and assign iterators so that native and library types can inter-operate
24 Properties of Iterator Intervalsvalid intervals can be traversed safely with an iterator An empty range [p,p) is valid If [first, last) is valid and non-empty, then [first+1, last) is also valid Proof: iterative induction on the interval If[first, last) is valid and position mid is reachable from first and last is reachable from mid then [first, mid) and [mid, last) are also valid If [first, mid) and [mid, last) are valid, then [first, last) is valid Proof: divide and conquer induction on the interval
25 The vector Container Implements a dynamically sized array of elementsElements are (almost certainly) contiguous in memory Random access and can iterate forward or backward Can only grow at back of vector (reallocates as needed) Many operations are constant time, such as whether or not the container is empty, how many elements it currently holds, etc. Pushing at the back is “amortized” constant time (occasional reallocations averaged over all pushes)
26 The list Container Implements a doubly linked list of elementsElements do not have to be contiguous in memory No random access, but can iterate forward or backward Can grow at front or back of list
27 Linear Search with Generic IteratorsGeneric find algorithm (Austern pp. 13): template
28 Key Ideas: Concepts and ModelsA concept gives a set of type requirements Classify/categorize types (e.g., random access iterators) Tells whether or not a type can or cannot be used with a particular algorithm (get a compiler error if it cannot) E.g., in the examples from last time, we could not use a linked list iterator in find1 or even find2, but we can use one in find Any specific type that meets the requirements is a model of that concept E.g., list
29 Concepts and Models, ContinuedWhat very basic concept does the last statement of find, (the line return first;) assume? Asked another way, what must be able to happen to first when it’s returned from function find? Same requirement imposed by by-value iterator parameters What other capabilities are required of the Iterator and T type parameters by the STL find algorithm ? template
30 Matching an Algorithm to the Iterators it NeedsCategory/ Operation Output Input Forward Bidirectional Random Access Read =*p (r-value) -> [] Write *p= (l-value) Iteration ++ ++ -- = -= Comparison == != == != < > <= >= What STL iterator category does find require?
31 Iterator Concept Hierarchy“destructive” read at head of stream (istream) “transient” write to stream (ostream) read or write a value (one-shot) Input Iterator Output Iterator Singly-inked-list style access (forward_list) value persists after read/write values have locations can express distance between two iterators Forward Iterator Bi-linked-list style access (list) Bidirectional Iterator is-a (refines) Array/buffer style access (vector, deque) Random Access Iterator
32 Can Extend STL Algorithms with Callable ObjectsMake the algorithms even more general Can be used parameterize policy E.g., the order produced by a sorting algorithm E.g., the order maintained by an associative containe Each callable object does a single, specific operation E.g., returns true if first value is less than second value Algorithms often have overloaded versions E.g., sort that takes two iterators (uses operator<) E.g., sort that takes two iterators and a binary predicate, uses the binary predicate to compare elements in range
33 Associative Containersunordered_multimap map C 2 set C C 3 B 2 A B 7 C 2 D 7 B D A 3 multimap A multiset C 2 C unordered_map B 2 D 7 B D A B 7 C 2 A 3 C 5 A C Associative containers support efficient key lookup vs. sequence containers, which lookup by position Associative containers differ in 3 design dimensions Ordered vs. unordered (tree vs. hash structured) We’ll look at ordered containers today, unordered next time Set vs. map (just the key or the key and a mapped type) Unique vs. multiple instances of a key unordered_multiset C A B C unordered_set A B C
34 Key Types, Comparators, Strict Weak OrderingLike sort algorithm, can modify container’s order … … with any callable object that can be used correctly for sort Must establish a strict weak ordering over elements Two keys cannot both be less than each other (inequality), so comparison operator must return false if they are equal If a < b and b < c then a < c (transitivity of inequality) If !(a < b) and ! (b < a) then a == b (equivalence) If a == b and b == c then a == c (transitivity of eqivalence) Type of the callable object is used in container type Cool example in LLM pp. 426 using decltype for a function Could do this by declaring your own pointer to function type But much easier to let compiler’s type inference figure it out for you
35 Associative Containers’ Associated TypesAssociative containers declare additional types A key_type gives the type of keys the container holds A value_type gives the type of values the container holds A mapped_type gives type associated with key (maps only) Examples for sets (key and value types are the same) Associated type set
36 Associative Containers’ Operators and MethodsChoose carefully which operators you use E.g., , m.insert(map
37 Thu Mar. 23, 7-9 PM. Makeup exam Fri Mar. 24, 7-9 AMCSE 332 Midterm Thu Mar. 23, 7-9 PM. Makeup exam Fri Mar. 24, 7-9 AM Room location to come on Piazza Exam will start promptly, please arrive early and it’s probably a good idea to find the room before then Only 1 side of an 8.5”x11” page of notes allowed All electronics must be off, including any cell phones, music players, tablets, laptops, etc. Recommendations for exam preparation Catch up on any studio exercises you’ve not done Catch up on any of the readings you’ve not done Write up your notes page as you study