Multi-Paradigm Programming in C++ Exam Review and Guidelines

E81 CSE 428S: Multi-Paradigm Programming in C++ Fall 2024 Exam 1 Review Adam Mitz mitzah@wustl.edu 1

Exam Time and Location 4:30-5:50 PM Tuesday, November 26 in Brauer Hall 12 (not Urbauer 222) CSE 428S Multi-Paradigm Programming in C++ 2

Studios Reminder: Studios 12-19 are due by Monday Nov. 25th, at 11:59PM One submission per team in Canvas, please If you have a studio marked Incomplete please address the comment and resubmit! Let me know by email ASAP if you need an extension, and the reason for that request CSE 428S Multi-Paradigm Programming in C++ 3

Exam Format Mostly short answer Some matching of terms Largely intended to test your understanding of concepts and language and library features What does this do? When would you use this? Why is it important? CSE 428S Multi-Paradigm Programming in C++ 4

Materials Allowed Open book, open notes I will bring an extra copy of the textbook What is allowed: Any handwritten or printed notes The course textbook What is not allowed: Electronics: laptops, tablets, phones, etc. Recommendation: write a 1-2 sided notes page! Writing it will help you study Easier to access during exam than printing all notes! CSE 428S Multi-Paradigm Programming in C++ 5

General Features of IO Streams C++ IO streams provide many standard IO features E.g., the cin, cout, and cerr streams wrap standard input (Linux fd 0), output (Linux fd 1) and error (Linux fd 2) Cannot copy or assign IO stream objects! Copy assignment operators and copy constructors are deleted Can test various properties of an IO stream Encoded as condition states of the stream The good() member function returns true if in a valid state Can use iostream object itself as a condition (note the shift operator returns a reference to the stream): if (ifs >> j) Can manage ostreams internal output buffers I.e., each of them stores data in a buffer, pushing data from the buffer to the destination string/file may not be immediate The flush IO manipulator forces data to move from buffer CSE 428S Multi-Paradigm Programming in C++ 6

File Input and Output Streams Restrict read/write privileges by the stream type Use fstream to read and write to a file, use ifstream for read only access to a file, use ofstreamif you ll only write to it Can initialize the stream with a file name I.e., pass a C-style or C++-style string to its constructor The stream will immediately (attempt to) open the file Can also default construct a file stream And then call its open() member function with a file name No matter how a file was opened by a stream, you can test whether it s open via the is_open() member function A file stream s destructor closes the file if it s open Though you can also call stream s close() member function directly (e.g., to then open up a different file in the stream) CSE 428S Multi-Paradigm Programming in C++ 7

String Input and Output Streams A lot of IO formatting can be aided by putting data into and pulling it out of C++ style strings E.g., assembling a roster of students in a course into a single string with line breaks, and then shifting the string into cout Again, can use the stream type to restrict read/write access: stringstream vs. istringstream vs. ostringstream Can insert multiple types of data into a string and then output the string to a file, to cout, to cerr, E.g., a great way to form and then emit usage or error messages from the error codes, argc and argv, etc. String streams also can help check formatting e.g., for lines from a file that contain numbers and text Can parse the contents of the string, then shift floating point numbers into float variables, integers into int variables, etc. CSE 428S Multi-Paradigm Programming in C++ 8

More about IO Manipulators Manipulators may change the state of an IO stream E.g., boolalpha causes bool values to print as true and false (alphabetic strings) instead of 1 and 0 (numeric values) Can change the default output format for numbers E.g., default is decimal notation, but can use hex or octal Can also control floating point formatting (e.g., precision) Line formatting can be done with manipulators too! E.g., setw to set column width, left or right to align output CSE 428S Multi-Paradigm Programming in C++ 9

Type Aliases Complex type expressions obscure program s intent in addition to being tedious and error-prone to type E.g., vector<CardSet<PinochleRank, Suit>>::iterator Can use type aliases to clarify what is intended Via descriptively named types that convey their meaning E.g., pinocle_hand_iterator or pinocle_meld_iterator Watch out for issues related to const with aliasing I.e., typedef char* pcstring; encapsulates the type: const pcstring p; says p (not what it points to) is const See LLM pp. 63 for terminology: top-level const concerns whether or not a pointer can be modified, low-level const concerns whether or not what it points to can be modified CSE 428S Multi-Paradigm Programming in C++ 10

The auto Type Specifier The auto type specifier can be used effectively to declare types involving complex type expressions Lets us avoid writing tedious and error-prone syntax Also may help to deduce types that depend on other types E.g., auto op1 = compose(sn, cs); Avoid using the auto type specifier unnecessarily May obscure key semantics of the types involved E.g., if chaining many type parameters in template code, only use it when an explicit type declaration would be unwieldy Also, again watch out for issues related to const Declarations that use the auto type specifier may ignore top-level const and only preserve low-level const CSE 428S Multi-Paradigm Programming in C++ 11

The decltype Type Specifier The decltype type specifier lets you use an existing type to declare another type E.g., decltype(i) j; declares a variable j that is of the same type as another (existing) variable i Gives similar flexibility to when you would use auto But preserves top-level const as well as low-level const However, decltype should only be used selectively as well Applying decltype to an expression May yield a reference type that then must be initialized E.g., if you put the name of a variable inside of parentheses E.g., decltype((i)) k; // won t compile CSE 428S Multi-Paradigm Programming in C++ 12

Run-Time Type Identification (RTTI) The dynamic_cast operator Forces a run-time type conversion involving a pointer or reference type to a class type (usually with virtual members) A static_cast should be used for other types, e.g., to convert a value from an enum class to an int The typeid operator Obtains the type of a variable or expression Lets you do run-time if-else logic over the types involved CSE 428S Multi-Paradigm Programming in C++ 13

Template Type Parameter Conversions The compiler uses the arguments in a call to a function template to determine the parameter types May be able to establish an exact match E.g., int i = 7; int j = 2; std::swap(i, j); Can also exploit some specific type conversions From a pointer (or reference) to a non-const variable to a pointer (or reference) to a const version of that type An array type to pointer-to-array-element type or a function type to the corresponding pointer-to-function type Having two different parameter types may help Allows different types (e.g., int, long) to be compared, etc. Then, normal conversions can apply to those types if either type can be converted to the other type CSE 428S Multi-Paradigm Programming in C++ 14

Function Pointers and References Can deduce template arguments from function pointer If there is a unique match that will happen automatically Or, give explicit template arguments for overloaded signatures Also can deduce template arguments from references For lvalue references (T&), constness is same as the argument For rvalue references (T&&), non-const type is deduced from an rvalue argument since rvalues are already inherently const References to references collapse to just references: T& &, T&& &, and T& && all collapse to T&; T&& && collapses to T&& Watch out for unexpected effects for rvalue references It is often best to provide an overload that takes an rvalue reference and another that takes a reference to a const lvalue CSE 428S Multi-Paradigm Programming in C++ 15

Implementation of std::move (per LLM) // based on code example from LLM pp. 690 template <typename T> typename remove_reference<T>::type&& moveit(T&& t) { return static_cast<typename remove_reference<T>::type&&>(t); } If an lvalue is passed in, move is instantiated to take a reference to an lvalue and return an rvalue reference to it (ok to static_cast lvalue to rvalue reference) Which then means the lvalue s implementation may be stolen by a move constructor or move assignment operator Generally not safe to use the lvalue after that until it has been re-assigned a value (which gives it a valid implementation) Otherwise, if an rvalue is passed to move, it is instantiated to take and return an rvalue reference (the static_cast does nothing) CSE 428S Multi-Paradigm Programming in C++ 16

Overloading with Function Templates Overloading of functions may take multiple forms Between non-template functions and operators of same name, including member vs. non-member functions and operators Between template versions and template or non-template versions of functions and operators with the same name Function matching rules are applied [LLM Section 6.4] Successful argument deduction instantiates a viable overload Candidate overloads are ranked by conversions needed If a single non-template overload is best, ignores templates Ambiguity may arise among viable overloads E.g., multiple non-template candidates could be used May give an error if the ambiguity cannot be resolved May only warn if best-matching can distinguish them CSE 428S Multi-Paradigm Programming in C++ 17

Resolving Function Template Overloads Special rules help to resolve multiple viable templates The more specialized template is selected when possible Different type conversions also may affect overloading E.g., converting char* to std::string may allow a different overload to be used than if the pointer was passed directly (especially in templates where T* is more specialized than T) Non-template functions are preferred over templates Template used only if no non-template function matches exactly E.g., if function template matches exactly but all non-template functions require type conversions in order to match Scopes also matter when resolving overloads Namespaces can be used to avoid ambiguity, or to selectively choose an overload via the scoping (::) operator However, if a conversion is hidden within a namespace (isn t visible in the current scope) that may preclude an overload CSE 428S Multi-Paradigm Programming in C++ 18

Variadic Templates Parameter Packs A variadic template has varying numbers of parameters An ellipsis (...) indicates the portion that may vary Those features may be useful for printing values, calling functions, etc. in a highly generic manner Function templates also may have varying numbers of function parameters as well as of type parameters So, all of the overloads to print out an arbitrary sequence of types to a stream could be passed as function arguments Variadic function templates are often written recursively with a non-variadic version of the function template used to halt it A non-variadic version is by definition more specialized than a variadic version and so will match better (if it is in scope) Lists of varying parameters are called parameter packs Template parameter packs specify varying template parameters Function parameter packs specify varying function parameters E.g., template <typename T, typename... TemplatePack> T foo(const TemplatePack&... function_pack); Operator sizeof... returns how many elements are in a pack CSE 428S Multi-Paradigm Programming in C++ 19

Parameter Pack Expansion and Forwarding Parameter pack expansions help manage the elements E.g., a type pattern (e.g., reference to const) can be applied as in R foo(const T& t, const TpltPack&... fnc_pack); E.g., arguments can be passed to a subsequent recursive invocation of the function as in return foo(fnc_pack...); Can also apply a function, a type transformation, or other more sophisticated patterns to each element in the pack, e.g., print(os, bytecount(rest)...); // count bytes passed Can forward parameters packs to preserve their format This can help to avoid accidental conversions due to template argument deduction, and/or implicit type transformations This is especially important for templates that mix rvalue/lvalue references, and/or use type transformation library templates E.g., when declaring and defining functionality like a new container type with emplace_back, etc. CSE 428S Multi-Paradigm Programming in C++ 20

Function Template Specializations A function template specialization narrows one or more of the sets of types that can be used to instantiate it The specialization is chosen over the template it specializes if the types that are used to instantiate it match both of them E.g.,template <> void print(ostream&, const string&); Specializations instantiate (vs. overload) templates But, specializations may themselves introduce ambiguity E.g., whether a full specialization (like above) pertains to variadic or non-variadic template versions (previous studio) Using an overload instead of a specialization may resolve ambiguity, especially with multiple related templates involved Can customize the implementation of a specialization E.g., to print a pointer s address as well as the value it points to Also widely used in standard library algorithms, containers, e.g., versions for random access iterators vs. forward iterators CSE 428S Multi-Paradigm Programming in C++ 21

Class Template Specializations Class templates may be partially specialized E.g., remove_reference<T> class template takes any type but remove_reference<T&> specializes it to take only lvalue refs E.g., remove_reference<T> class template takes any type but remove_reference<T&&> specializes it to take only rvalue refs Both of those specializations narrow the set of accepted types, and as they are more specialized are chosen for those subsets Can also specialize class members vs. the class itself This can focus customization of implementation on the parts of a class that are potentially type-specific but then allow the rest of the class to remain more generic E.g., you could specialize operator< so that for pointer types it compares what is pointed to rather than their addresses E.g., you could specialize operator< further so that for pointer to character types (C-style strings) it does strcmp CSE 428S Multi-Paradigm Programming in C++ 22

Containers Provide Their Own Iterators Containers declare associated iterator types // try to use const_iterators whenever you can vector<int>::iterator i; // iterator over non-const vector<int>::const_iterator ci; // iterator over const Also give iterator accessor/factory methods for beginning of and just past the end of range // v is previously declared as vector<int> v; auto ci2 = v.cbegin(); // use a const_iterator while (ci2 != v.cend()) { // compare to const_iterator cout << *ci2 << endl; // does not modify v ++ci2; }

More About Container Iterators Their iterators generalize different uses of pointers Most importantly, they 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: dereferenceable(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 fundamental and library types can inter-operate

Properties of Iterator Intervals valid 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 both [first, mid) and [mid, last) are valid, then [first, last) is valid Proof: divide and conquer induction on the interval Corrolary: if [first, last) is valid and position mid is safelyreachable from first, and last is safely reachable from mid, then both [first, mid) and [mid, last) are also valid

Some Standard Sequential Containers The std::deque class template Double ended queue that can grow efficiently at either end E.g., using its push/emplace_front/back member functions Provides fast random access indexing (in constant time) The std::vector class template Behaves like an array but can grow efficiently at the back E.g., using its push_back or emplace_back member functions Provides fast random access indexing (in constant time) The std::list class template Doubly-linked list, can grow/shrink efficiently at any position E.g., using its insert/emplace/delete member functions Provides iteration in either direction, but not indexing The std::forward_list class template Singly-linked list, can grow/shrink efficiently at any position E.g., using its insert/emplace/delete member functions Provides forward iteration, not indexing or backward iteration CSE 428S Multi-Paradigm Programming in C++ 26

Container Type Requirements/Operations Sequential containers impose only a few requirements on the types they contain (often to maintain efficiency) E.g., types in a container must support default initialization or construction to make (re-)sizing a container possible and efficient The operations provided by a container and its iterators are specific to the container s complexity/efficiency requirements E.g., random access iterators for std::vector and std::deque support +=, ++, and -- operators with constant time complexity E.g., bidirectional iterators for std::list support ++ and -- operators with constant time complexity, but +=isn t supported E.g., forward iterators for std::forward_list support ++ with constant time complexity, but don t support either -- or += C++ library containers iterator ranges are left-inclusive An iterator range is from first up to but not including last Also shown as [first, last) to indicate closed-open semantics Allows easy representation of empty ranges (first == last) and past-the-end iterators for things like strings, iostreams, etc. CSE 428S Multi-Paradigm Programming in C++ 27

Key Ideas: Concepts and Models A concept collects a set of type requirements Classifies/categorizes types (e.g., random access iterators) Tells whether or not a type can be used with a particular algorithm (you will 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<char>::iterator vs. char*in find Different abstractions (bi-linked list iterator vs. char pointer) No inheritance-based relationships are necessary But both model iterator concept necessary for find

Concepts and Models, Continued What 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 <typename Iterator, typename T> Iterator find(Iterator first, Iterator last, const T& value) { while (first != last && *first != value) ++first; return first; }

Match Algorithm to the Iterators it Needs Random Access Category/ Operation Output Input Forward Bidirectional =*p (r-value) =*p (r-value) =*p (r-value) =*p (r-value) Read -> [] Access -> -> -> *p= (l-value) *p= (l-value) *p= (l-value) *p= (l-value) Write ++ -- + - += -= Iteration ++ ++ ++ ++ -- == != < > <= >= Comparison == != == != == != What STL iterator category does findrequire?

Iterator Concept Hierarchy transient write to stream (ostream) destructive read at head of stream (istream) read or write a value (one-shot) Input Iterator Output Iterator is-a (refines) Singly-inked-list style access (forward_list) value persists after read/write values have locations can express distance between random access iterators Forward Iterator is-a (refines) Bi-linked-list style access (list) Bidirectional Iterator is-a (refines) Array/buffer style access (vector, deque) Random Access Iterator

What if Algorithm Has Multiple Versions? // Based on Austern, pp. 38, 39 template <class Iter, class Distance> void jump (Iter i, Distance d, fwd) { while (d>0) {--d; ++i;} // O(d) } concrete tag (empty struct type) Static dispatching Implementations provide different signatures Iterator type is evaluated at compile-time Links to the best implementation template <class Iter, class Distance> void jump (Iter i, Distance d, rand) { i += d; // O(1) } concrete tag (empty struct type) Notice how type tags are used template <class Iter, class Distance> void jump (Iter i, Distance d) { jump (i, d, iterator_traits<Iter>:: iterator_category() ) } default constructor (explicit call syntax)

Iterator Traits and Category Type Tags struct input {}; // empty structs for type tags struct output {}; struct fwd : public input {}; // note inheritance struct bidir : public fwd {}; struct rand : public bidir {}; (actually, random_access_iterator_tag) Need a few concrete types to use as tags Use empty structs E.g., input, output, fwd, bidir, and rand template <typename I> struct iterator_traits { ... typedef typename I::iterator_category iterator_category; }; Tags provide yet another associated type for iterators Iterator category Made available by using the traits idiom template <typename T> struct iterator_traits<T*> { ... typedef rand iterator_category; }; template <typename T> struct iterator_traits<const T*> { ... typedef rand iterator_category; };

Associative Containers Associated Types Associative 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) For sets key and value types are the same Associated type set<int>::key_type is int, as is set<int>::value_type Examples for maps (note key becomes const in value) Associated type map<int, string>::key_type is int Type map<int, string>::mapped_type is string Associated type map<int, string>::value_type is pair<const int, string>

Iteration Through Associative Containers set map C C 2 iter2 B B 2 D D 7 A A 3 multiset multimap C C 2 iter1 B B 2 D D 7 A A 3 C C 5 Iteration is bi-directional Can increment (e.g., ++iter1) or decrement (e.g., --iter1) Dereferencing gives read-only access to keys E.g., *iter1 = D ; or iter2->first = D ; are not allowed But, can gain read-write access to map s value E.g., iter2->second = 7; is allowed

Adding Elements to a Map or Set set (before) map (before) E D 2 D B 2 E 7 B A 3 set (after) map (after) D D 2 B B 2 E E 7 A 3 C C 5 Insert returns a pair (may also rebalance the tree) First part is an iterator to element, second is true on success Multi{map,set} insert just returns iterator to inserted element For maps, insert takes a pair (several possible ways) E.g., m.insert({ C , 5}); // list initialization E.g., m.insert(make_pair( C , 5)); E.g., m.insert(pair<string, int>( C , 5)); E.g., m.insert(map<string, int>::value_type( C , 5));

Unordered Containers (UCs) unordered_set unordered_multiset unordered_map unordered_multimap A B C A 0 B 7 C 2 C 3 C A 0 B 7 C 2 A B C UCs use == to compare (instead of < to order) elements Types in unordered containers must be equality comparable When you write your own structs/classes, overload == vs. < UCs store elements in indexed buckets instead of a tree Useful for types that don t have an obvious ordering relation over their values UCs use hash functions to put and find elements in buckets May improve performance in some cases (if performance profiling suggests so) Declare UCs with pluggable hash functions via callable objects, decltype, etc.

Organization of the Algorithm Libraries The <algorithm> header file contains Non-modifying sequence operations Do some calculation but don t change sequence itself Examples include count, count_if Mutating sequence operations Modify the order or values of the sequence elements Examples include copy, random_shuffle Sorting and related operations Modify the order in which elements appear in a sequence Examples include sort, next_permutation The <numeric> header file contains General numeric operations Scalar and matrix algebra, especially used with vector<T> Examples include accumulate, inner_product

Materials Allowed Open book, open notes I will bring an extra copy of the textbook What is allowed: Any handwritten or printed notes The course textbook What is not allowed: Electronics: laptops, tablets, phones, etc. Recommendation: write a 1-2 sided notes page! Writing it will help you study Easier to access during exam than printing all notes! CSE 428S Multi-Paradigm Programming in C++ 39

Exam Format Mostly short answer Some matching of terms Largely intended to test your understanding of concepts and language and library features What does this do? When would you use this? Why is it important? CSE 428S Multi-Paradigm Programming in C++ 40

Studios Reminder: Studios 12-19 are due by Monday Nov. 25, at 11:59PM One submission per team in Canvas, please If you have a studio marked Incomplete please address the comment and resubmit! Let me know by email ASAP if you need an extension, and the reason for that request CSE 428S Multi-Paradigm Programming in C++ 41

Exam Time and Location 4:30-5:50 PM Tuesday, November 26 in Brauer Hall 12 (not Urbauer 222) CSE 428S Multi-Paradigm Programming in C++ 42

Good Luck! That said, please also remember that Fortune favors the prepared mind. Louis Pasteur Any questions? CSE 428S Multi-Paradigm Programming in C++ 43