Information and Computer Science 45C — Week 8 Integrated Reading Notes

Table of Contents

• 1. Weekly Learning Objectives
• 2. The C++ Standard Library
• 3. The STL Framework — General Concepts
• 4. Containers: Categories Overview
• 5. Sequence Containers
• 6. Associative Containers
• 7. Container Adapters
• 8. Matching Tasks to Containers (Klefstad Activity)
• 9. STL Iterators
• 10. Iterator Categories
• 11. STL Algorithms
• 12. Iterator Adapters
• 13. Function Objects in Algorithms
• 14. Ranges (C++20)
• 15. I/O Streams — The iostream Library
• 16. Input with istream
• 17. Output with ostream and ios
• 18. Container Cross-Comparison Reference
• 19. Week 8 Comprehensive Cheat Sheet
• 20. Top Five Takeaways for Week 8

UCI ICS 45C: Programming in C++ (35770)
These notes integrate the Week 8 reading material: LearnCpp 21.1 (the standard library), 21.2 (STL containers overview), 21.3 (STL iterators overview), 21.4 (STL algorithms overview), 28.1 (input and output streams), 28.2 (input with istream), and 28.3 (output with ostream and ios); cppreference reference pages for std::vector, std::set, and std::map; and Klefstad's Topic 8 PPT — STL containers, iterators, algorithms, insert/stream/reverse iterator adapters, container adapters, function objects, and ranges. Content is organized by topic, not by source.
Note on cross-week PPT content: Slides 26–27 of Topic 8 PPT cover the standard C++ exception hierarchy (std::bad_alloc, std::logic_error, std::runtime_error, etc.). The exception-handling material is part of the Week 7 reading list (LearnCpp 27.x), so those slides are not duplicated here — they were already integrated into the Week 7 notes (sections 9–14). If you want a one-line recap of the standard exception hierarchy, see section 19.5 of the Week 7 cheat sheet.

1. Weekly Learning Objectives

Bird's-eye view of the three conceptual blocks of Week 8

1.1 The Standard Template Library — STL (chapters 21.1–21.4)

• Understand: what the C++ Standard Library is and why it exists
• Master: the three-way decomposition of the STL — containers, iterators, algorithms — and how they compose
• Distinguish: sequence containers (vector, deque, list, array, forward_list, string) vs. associative containers (set, map, multiset, multimap, unordered variants) vs. container adapters (stack, queue, priority_queue)
• Master: choosing the right container for a task (sequence vs. associative; ordered vs. unordered; element-only vs. key/value)
• Master: the iterator abstraction — begin(), end(), *, ++, ==, the half-open range [begin, end)
• Understand: iterator categories (input, output, forward, bidirectional, random-access, contiguous) and why they exist
• Master: common algorithms — sort, find, min_element, max_element, reverse, accumulate, transform, for_each, copy
• Master: iterator adapters — back_inserter, front_inserter, inserter, istream_iterator, ostream_iterator, reverse iterators
• Understand: function objects (free functions, function pointers, lambdas) as algorithm arguments
• Be aware of: C++20 ranges as a higher-level alternative to passing begin/end pairs

1.2 I/O Streams (chapters 28.1–28.3)

• Understand: a stream is a sequence of bytes that can be read or written sequentially
• Master: the class hierarchy — ios, istream, ostream, iostream, the predefined cin/cout/cerr/clog
• Master: the extraction operator (>>) for input and the insertion operator (<<) for output, including whitespace-skipping behavior
• Master: input techniques: setw() to limit reads, get() / getline() (member and free), gcount(), peek(), unget(), putback(), ignore()
• Master: output formatting via flags (setf/unsetf) and manipulators (std::hex, std::fixed, std::setprecision, std::setw, std::setfill, std::left/std::right)
• Distinguish: flags that belong to format groups (only one flag in the group can be active at a time)

1.3 Bridge: Iterators connect everything

• The single big idea of the STL: algorithms operate on iterator ranges, not containers. Once a container supplies a pair of iterators, every algorithm in <algorithm> works on it.
• Stream iterators turn cin/cout/ifstream/ofstream into iterator ranges — so the same algorithms work on files and keyboards.

2. The C++ Standard Library

Corresponds to LearnCpp 21.1

2.1 What is the Standard Library?

The C++ Standard Library is a collection of templated classes that provide reusable containers, algorithms, and iterators. The vast majority of typical programs — loops, strings, arrays, sorting, lookup — can be built from these pieces without rewriting them.

Why use it:

• The code is already written, debugged, and reasonably efficient
• It is standardized: the same std::vector behaves identically across compilers and platforms
• It removes a whole class of bugs that plague hand-written non-class versions of containers

Why people fear it:

• It is large and everything is templated, so error messages can be intimidating
• Best to learn it in bite-sized pieces — use what you need, ignore the rest

💡 Key Insight (LearnCpp 21.1)
The Standard Library is not an extension to the C++ language — it lives in the std namespace. From C++'s point of view, you and std::vector are on equal footing: anyone who follows the conventions can write a container that algorithms can operate on. This is what makes STL extensible by users.

2.2 The STL: a subset of the Standard Library

The phrase STL (Standard Template Library) is sometimes used as a synonym for "the Standard Library," but historically the STL is the container/iterator/algorithm framework specifically, designed largely by Alexander Stepanov. Other parts of the Standard Library — <iostream>, <chrono>, <filesystem>, <regex>, etc. — are not strictly STL.

In this course, "STL" almost always means the container/iterator/algorithm portion.

3. The STL Framework — General Concepts

Corresponds to Topic 8 PPT slides 1–2

3.1 The Three Pillars

Klefstad's slide states the design philosophy crisply:

The STL is a framework for defining composable library pieces:

• containers — hold things (stack, lists, maps, etc.)
• iterators — connect each algorithm to each container
• algorithms — do things (min, sort, etc.)

Imagine an M×N grid:

• M rows = M algorithms
• N columns = N containers
• Without iterators, every cell needs its own implementation → M × N versions
• With iterators, each algorithm is written once in terms of iterators, and each container exposes iterators once → only M + N pieces

That is why the STL scales.

3.2 Supporting Components

Two more pieces round out the framework:

• Function objects — anything callable that algorithms can use as a parameter. This includes ordinary functions, function pointers, function-pointer-like classes (struct with operator()), and lambdas (Week 7). They make algorithms flexible without needing thousands of overloads.
• Standard exceptions — for STL error handling (already covered in Week 7). These provide a uniform way for STL operations to report errors (std::out_of_range, std::bad_alloc, etc.).

3.3 Extending the STL

The STL is extensible by users who obey the conventions:

• Write a container that exposes begin() / end() and an iterator class with the appropriate operators → every STL algorithm now works on your container.
• Write a function object that conforms to the algorithm's expected signature → it can be passed to any algorithm that takes a callable.

You already practiced this idea in HW6 (the Picture linked list with custom iterator-style traversal).

4. Containers: Categories Overview

Corresponds to LearnCpp 21.2 + Topic 8 PPT slide 3

4.1 The Three Container Families

4.2 The Klefstad Implementation Distinction (PPT slide 3)

Klefstad emphasizes the two implementation strategies behind the containers:

• Array-based — contiguous memory, fast random access (HW1 Stack, HW4 String)
• Linked-structure-based — nodes with pointers, fast insertion in the middle (HW5 String, HW6 Picture)

This matters: when picking a container, the underlying data structure determines the complexity of each operation. A vector and a list both store a sequence, but vector[i] is O(1) while list[i] doesn't even exist (you must walk node by node — O(n)).

4.3 Python Comparison

⚠️ Pitfall
Python's list is C++'s std::vector, not C++'s std::list. The names are misleading — C++ std::list is a doubly linked list with no random-access [] operator.

5. Sequence Containers

Corresponds to LearnCpp 21.2 (sequence containers section) + Topic 8 PPT slide 6

Sequence containers all preserve the order you insert in. The choice between them comes down to which operations need to be fast and which can be slow.

5.1 std::vector

A dynamically resizable array stored in contiguous memory. The single most-used container in modern C++.

Defining characteristics:

• Contiguous memory layout (so &v[0] points to a real C-style array)
• Random access in O(1) via operator[] and at()
• Append/pop at the back is O(1) amortized: push_back(), pop_back(), back()
• Insertion or removal in the middle is O(n) (everything after must shift)
• Grows automatically when full (often doubles capacity)

LearnCpp 21.2 example:

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> vect;
    for (int count=0; count < 6; ++count)
        vect.push_back(10 - count);   // insert at end

    for (int index=0; index < vect.size(); ++index)
        std::cout << vect[index] << ' ';
    std::cout << '\n';
}
// Output: 10 9 8 7 6 5

Klefstad PPT slide 6 (with explicit O(1) emphasis):

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v;   // or vector<int> v2(100, 0);  with 100 elements init to zero
    for (int i = 0; i < 100; ++i)  // fill v
        v.push_back(i);            // appends to end of v
    for (int i = 0; i < v.size(); ++i)   // print v
        cout << v[i] << endl;
    for (; v.size() > 0; v.pop_back())   // drain v from the back
        cout << v.back() << endl;
}

💡 PPT Note — "elements are kept in a dynamic array — like Python list"

• push_back(), pop_back(), back() are all O(1)
• v[i] is fast (random access)

Constructors worth knowing:

std::vector<int> v1;                  // empty
std::vector<int> v2(100);             // 100 default-initialized ints (= 0)
std::vector<int> v3(100, 7);          // 100 copies of 7
std::vector<int> v4{1, 2, 3, 4};      // initializer-list: exactly these 4 elements
std::vector<int> v5(v1.begin(), v1.end()); // copy from a range

⚠️ Confusion alert — std::vector<int> v(100) makes a vector of 100 zeros, while std::vector<int> v{100} makes a vector containing one element with value 100. The brace-list constructor always wins when it can match.

5.1.1 size vs capacity (cppreference)

A vector tracks two different quantities:

size <= capacity always. The gap exists because growth is amortized O(1): when the vector runs out of capacity, it allocates a bigger buffer (typically doubling), copies/moves the existing elements over, and frees the old buffer. Reallocation is expensive, so the vector overshoots — pre-allocating extra room means subsequent push_backs are free.

💡 cppreference exact wording (paraphrased) — "Vectors usually occupy more space than static arrays, because more memory is allocated to handle future growth. This way a vector does not need to reallocate each time an element is inserted, but only when the additional memory is exhausted."

Two performance-relevant member functions:

v.reserve(1000);     // bumps capacity to ≥ 1000 without changing size
                     // — use when you know roughly how many push_backs are coming
v.shrink_to_fit();   // requests that capacity shrink to size
                     // — non-binding; implementation may ignore it

⚠️ Best practice — Use reserve() before a big loop of push_backs when you know (or can estimate) the final size. It eliminates all reallocations and the associated iterator/pointer invalidations.

5.1.2 Complexity Summary (cppreference)

5.1.3 Member Function Map (cppreference)

💡 at() vs operator[] — Both index into the vector. The difference: v.at(i) throws std::out_of_range if i is invalid; v[i] is undefined behavior for invalid i. Use at() when you can't guarantee the index is valid; use [] in tight inner loops.

💡 push_back vs emplace_back — push_back(x) takes an already-constructed object and copies (or moves) it in. emplace_back(args...) forwards the args to the element's constructor, constructing it in place with no temporary. For trivially-copyable types like int, no difference. For expensive types (a std::string or your own class), emplace_back saves a move.

5.1.4 Iterator Invalidation (cppreference — critical knowledge)

This is the single most important table to memorize about std::vector. Modifying a vector can invalidate iterators (and pointers/references) into it — using one after invalidation is undefined behavior.

⚠️ The classic bug

for (auto it = v.begin(); it != v.end(); ++it)
    if (*it == bad)
        v.erase(it);    // ⚠️ it is invalidated after erase!

Fix with the erase-return idiom: it = v.erase(it); (and don't ++it in the increment when you erased). Or use std::erase / std::erase_if (C++20).

5.1.5 The vector<bool> Specialization (cppreference)

⚠️ The standard library provides a specialization of std::vector for the type bool, which may be optimized for space efficiency. This is not a real vector of bool — it's packed bits, and v[i] returns a proxy object, not a real bool&. Many things that work on vector<int> don't compile on vector<bool> (you can't take a bool* to an element, you can't use it with some generic algorithms).

If you need a sequence of booleans that behaves like a regular vector, use std::vector<char> or std::deque<bool>. If you need a bitset, std::bitset<N> (fixed-size) or std::vector<bool> (dynamic) is fine — just know what you're getting.

5.1.6 cppreference Worked Example

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = {8, 4, 5, 9};
    v.push_back(6);
    v.push_back(9);
    v[2] = -1;              // overwrite element at position 2

    for (int n : v)
        std::cout << n << ' ';
    std::cout << '\n';
}
// Output: 8 4 -1 9 6 9

5.2 std::deque (double-ended queue, pronounced "deck")

A dynamic array-like container that supports fast push/pop at both ends.

Defining characteristics:

• O(1) push/pop at both front and back
• Random access via operator[] is O(1) but slower than vector (the storage is typically a sequence of fixed-size blocks, not one contiguous chunk)
• Insertion/removal in the middle is O(n)

#include <iostream>
#include <deque>

int main()
{
    std::deque<int> deq;
    for (int count=0; count < 3; ++count)
    {
        deq.push_back(count);       // insert at back
        deq.push_front(10 - count); // insert at front
    }

    for (int index=0; index < deq.size(); ++index)
        std::cout << deq[index] << ' ';
    std::cout << '\n';
}
// Output: 8 9 10 0 1 2

5.3 std::list (doubly linked list) and std::forward_list (singly linked)

A doubly linked list where each node has prev, next, and the element value. std::forward_list is the singly linked variant introduced in C++11 (only next, more memory-efficient, only forward iteration).

Defining characteristics:

• No random access — no operator[], no at(). To reach element i you must walk the list (O(n)).
• O(1) insertion or removal anywhere, given an iterator to the spot
• Iterators stay valid after insertion/erasure elsewhere (vector iterators don't)

LearnCpp 21.2: "Lists only provide access to the start and end of the list — there is no random access provided. If you want to find a value in the middle, you have to start at one end and 'walk the list' until you reach the element you want to find."

Use list when you do a lot of middle-insertion/removal and don't need random access.

5.4 std::array (C++11, simple C-array wrapper)

A fixed-size array whose size is part of the type. Essentially a safer, STL-compatible replacement for C-style arrays.

std::array<int, 5> a{1, 2, 3, 4, 5};  // size 5 is part of the type

Defining characteristics:

• Size known at compile time, no dynamic allocation
• Random access in O(1)
• Has STL iterators (begin(), end()), so it works with std::sort, std::find, etc.
• Cannot grow or shrink

5.5 std::string as a sequence container

Although LearnCpp notes string isn't generally lumped with sequence containers, it essentially is one: it behaves like a vector<char> with extra string-specific helpers (+, substr, find, etc.). It exposes the same iterator interface, so STL algorithms work on strings unchanged.

std::string s = "world";
std::reverse(s.begin(), s.end());  // s == "dlrow"

6. Associative Containers

Corresponds to LearnCpp 21.2 (associative containers) + Topic 8 PPT slides 7–10

Associative containers sort (or hash) their elements automatically on insertion. You don't decide the position — the container does.

Default comparison: operator<. You can supply a custom comparator.

6.1 std::set and std::multiset

set — a collection of unique elements sorted by value. multiset — same, but duplicates are allowed.

Operations and complexity (all O(log n) for the balanced-BST versions):

• insert(x) — add x; for set, no-op if already present
• find(x) — returns an iterator to x, or end() if absent
• erase(x) or erase(iter) — remove
• iteration yields elements in sorted order

Klefstad PPT slide 8 example:

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<char> S;
    for (char c = 'A'; c <= 'Z'; ++c)   // fill S
        S.insert(c);
    for (char c = 'Z'; c >= 'A'; --c)   // fill S again
        S.insert(c);                    // duplicates are silently rejected
    for (auto E : S)
        cout << E << endl;              // each letter appears exactly once

    if (S.find('A') != S.end())
        cout << "A is in there" << endl;
}

If S were a multiset instead, you would see A A B B C C ... Z Z because each letter was inserted twice.

💡 Conceptual Note
std::set is not a Python set. Python's set is a hash table (unordered, O(1) lookup). C++'s std::set is a balanced binary search tree (sorted, O(log n) lookup). The hash version is std::unordered_set.

6.1.1 Implementation and Uniqueness Rule (cppreference)

💡 cppreference (paraphrased) — std::set contains a sorted set of unique objects of type Key. Search, removal, and insertion are logarithmic. Sets are usually implemented as red–black trees — a self-balancing binary search tree.

Uniqueness is defined via equivalence, not equality:

Two elements a and b are considered "the same" (and only one is kept in the set) when:

!comp(a, b) && !comp(b, a)

In plain English: neither is strictly less than the other under the comparison function. The default comp is std::less<Key>, which uses operator<.

⚠️ Subtle implication — std::set never calls operator==. It only calls operator<. So a type that has a weird < and a normal == can produce surprising "duplicates" or "non-duplicates" in a set.

⚠️ Elements are effectively const through iterators. Dereferencing a set<Key> iterator gives you const Key&, not Key&. You cannot modify an element in place — doing so could break the sort invariant and silently corrupt the tree. To "change" an element: erase the old one and insert the new one. (Same reason std::map's value_type is pair<const Key, T> — the key part is const for the same invariant.)

6.1.2 Member Function Map (cppreference)

💡 contains (C++20) is the modern idiomatic membership check:

if (s.contains(x))  { /* ... */ }   // C++20
if (s.find(x) != s.end()) { /* ... */ }   // pre-C++20 equivalent

💡 count on set returns 0 or 1 (because keys are unique). On multiset it can be larger. Either way, count(x) > 0 is a less efficient way to check membership than contains(x) — the latter can short-circuit on the first match.

6.1.3 Range Queries — lower_bound, upper_bound, equal_range

These three return iterators into the sorted set, useful for range queries:

In a multiset [1, 2, 2, 2, 3]:

• lower_bound(2) → iterator to the first 2
• upper_bound(2) → iterator to 3
• Iterating between them visits all the 2s.

6.1.4 cppreference Worked Example

#include <iostream>
#include <set>
#include <string_view>

int main() {
    std::set<int> set{1, 5, 3};
    // set: { 1, 3, 5 }  — automatically sorted on construction

    set.insert(2);
    // set: { 1, 2, 3, 5 }

    set.erase(1);
    // set: { 2, 3, 5 }

    // C++20 contains
    if (set.contains(3))
        std::cout << "set contains 3\n";

    // Range-constructor from any iterable
    std::string_view word = "element";
    std::set<char> characters(word.begin(), word.end());
    // characters: { e, l, m, n, t }   — 5 unique characters
}

💡 Range constructor idiom — every STL container accepts a (begin, end) iterator pair, so you can build a set<char> from a string, a set<int> from a vector<int>, etc.

6.2 std::map and std::multimap

map — a collection of key/value pairs, sorted by key, with unique keys. multimap — same, but multiple values per key are allowed.

Each element is a std::pair<const Key, Value>, accessed via .first (the key) and .second (the value).

Klefstad PPT slide 9 — "elements are pair<first, second> like pair<key, value> — behave like an array but indexed by any type (like Python Dictionary). Elements are sorted by their first (not second)."

Multimap as a dictionary: A real-world dictionary maps a word (key) to one or more meanings (values). That's a multimap, not a map.

LearnCpp 21.3 example:

#include <map>
#include <string>
#include <iostream>

int main() {
    std::map<int, std::string> mymap;
    mymap.insert(std::make_pair(4, "apple"));
    mymap.insert(std::make_pair(2, "orange"));
    mymap.insert(std::make_pair(1, "banana"));
    mymap.insert(std::make_pair(3, "grapes"));
    mymap.insert(std::make_pair(6, "mango"));
    mymap.insert(std::make_pair(5, "peach"));

    auto it{ mymap.cbegin() };
    while (it != mymap.cend()) {
        std::cout << it->first << '=' << it->second << ' ';
        ++it;
    }
    std::cout << '\n';
}
// Output: 1=banana 2=orange 3=grapes 4=apple 5=peach 6=mango

Klefstad PPT slide 10 — three ways to iterate:

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> A;
    A["Bill"]   = 33;
    A["George"] = 29;
    A["Al"]     = 27;

    // Way 1: classic for-each, E is a pair<string,int>
    for (auto E : A)
        cout << E.first << " is " << E.second << " ";

    // Way 2: C++17 "destructuring for loop" — by const reference (no copy)
    for (const auto& [name, age] : A)
        cout << name << " is " << age << " ";

    // Both print: Al is 27 Bill is 33 George is 29
}

💡 Key Insight — map is sorted on the first field, so iterating prints keys in ascending order: Al, Bill, George.

The bracket operator on map:

A["Bill"] = 33;   // insert or overwrite key "Bill" with value 33
int x = A["Al"];  // read the value at key "Al"

⚠️ Trap — A["NewKey"] on a non-existent key inserts a new entry with a default-constructed value (0 for int, "" for string) and returns a reference to it. To check existence without inserting, use A.find(key) != A.end() or (C++20) A.contains(key).

6.2.1 Implementation and Sort Order (cppreference)

💡 cppreference (paraphrased) — std::map is a sorted associative container that contains key-value pairs with unique keys. Search, removal, and insertion are logarithmic. Maps are usually implemented as red–black trees.

Iterators visit the elements in ascending order of keys (using the comparison function — std::less<Key> by default).

Uniqueness rule, like set, is equivalence-based: keys a and b are considered the same if !comp(a, b) && !comp(b, a).

6.2.2 value_type = std::pair<const Key, T> (cppreference)

A subtle but crucial detail: each element of a map<Key, T> is a

std::pair<const Key, T>

— note the const on Key. You cannot modify a key in place after insertion (modifying it would break the sort order). To "change" a key, you must erase the old entry and insert a new one.

Three useful type aliases you'll see:

6.2.3 Element Access: at() vs operator[]

⚠️ Three implications:

• You cannot use operator[] on a const map — it might insert!
• You cannot use operator[] if T has no default constructor.
• m[k] is a write even if you wrote int x = m[k]; — it creates an entry. Use m.find(k), m.contains(k) (C++20), or m.at(k) for read-only access.

6.2.4 Member Function Map (cppreference)

Three insert variants worth knowing (C++17):

💡 Why try_emplace? Suppose T is expensive to construct (e.g. a big std::string built from a function call). insert({k, expensive_construct()}) always constructs the value, even if it then throws it away because k already existed. try_emplace(k, args_for_construct...) only constructs when needed.

emplace_hint(hint, args...) — bypass the O(log n) search:

insert and emplace normally do an O(log n) tree search to find where the new element goes. emplace_hint lets you pass an iterator that says "start looking here":

std::map<int, std::string> m;
auto it = m.end();
for (int i = 0; i < 1000; ++i)
    it = m.emplace_hint(it, i, "v");   // amortized O(1) per insert, vs O(log n)

• If the hint points just past where the new element should go, insertion is amortized O(1) instead of O(log n).
• If the hint is wrong, the implementation falls back to a regular O(log n) search — so a bad hint costs you nothing extra, but doesn't help.
• Classic use: bulk-inserting already-sorted data (above pattern, or feeding m.end() repeatedly when keys arrive in increasing order). Same trick exists for set / multiset / multimap.

6.2.5 cppreference Worked Example

#include <iostream>
#include <map>
#include <string>

void print_map(std::string_view label, const std::map<std::string, int>& m) {
    std::cout << label;
    for (const auto& [key, value] : m)        // C++17 structured binding
        std::cout << '[' << key << "] = " << value << "; ";
    std::cout << '\n';
}

int main() {
    // List-initialization with brace-pair entries
    std::map<std::string, int> m{{"CPU", 10}, {"GPU", 15}, {"RAM", 20}};
    print_map("1) Initial:  ", m);
    // 1) Initial:  [CPU] = 10; [GPU] = 15; [RAM] = 20;

    m["CPU"] = 25;   // update existing
    m["SSD"] = 30;   // insert new
    print_map("2) Updated:  ", m);
    // 2) Updated:  [CPU] = 25; [GPU] = 15; [RAM] = 20; [SSD] = 30;

    // ⚠️ operator[] on a NON-EXISTENT key inserts default value (0 for int)
    std::cout << "3) m[UPS] = " << m["UPS"] << '\n';
    // 3) m[UPS] = 0
    // m now contains UPS=0 even though we only "read" it!

    m.erase("GPU");
    print_map("4) After erase: ", m);

    // C++20: erase_if free function
    std::erase_if(m, [](const auto& pair){ return pair.second > 25; });
    print_map("5) After erase_if (>25): ", m);

    std::cout << "size = " << m.size() << '\n';
    m.clear();
    std::cout << std::boolalpha << "empty? " << m.empty() << '\n';
}

💡 List initialization syntax — {{"CPU", 10}, {"GPU", 15}} is two brace-init-lists, each constructing a pair<string, int>, packaged in an outer initializer_list<pair> consumed by the map's constructor. You'll see this constantly.

6.2.6 Iterator Invalidation (set / multiset / map / multimap)

Ordered associative containers are tree-based, so their invalidation rules are much friendlier than vector's — this is one of their biggest practical advantages.

💡 Contrast with vector — vector::insert can invalidate everything past the insertion point (or everything if it reallocates). For set/map, even mid-iteration insertion is safe for the iterators you're already holding.

Safe erase-while-iterating idiom (because erase invalidates only the erased iterator, you must capture the return value):

for (auto it = m.begin(); it != m.end(); ) {
    if (should_remove(*it))
        it = m.erase(it);     // erase returns iterator to the NEXT element
    else
        ++it;
}

Or in C++20: std::erase_if(m, predicate) does this for you (see §6.2.5 worked example).

6.3 std::unordered_set and std::unordered_map

The hash-table versions, added in C++11.

• Average O(1) insert, find, erase (versus O(log n) for the ordered versions)
• Elements are not in any meaningful order
• Use when you don't need sorted iteration and want speed

6.4 Quick Comparison Table

7. Container Adapters

Corresponds to LearnCpp 21.2 (container adapters) + Topic 8 PPT slide 23

Container adapters are wrappers around an existing sequence container; they expose a restricted interface that matches a specific abstract data type. You can choose which underlying container to wrap (and there's a sensible default).

7.1 std::stack — LIFO

A stack is a Last-In, First-Out container.

#include <stack>
std::stack<int> s;
s.push(1);
s.push(2);
s.push(3);
int top = s.top();   // 3
s.pop();             // removes 3

Klefstad PPT slide 23 — backing container requirements:

Works with any container that supports empty, size, back, push_back, pop_back.
Compatible underlyings: vector, deque, list. Default: deque.

💡 PPT Note — "default is deque (which seems odd, since vector seems like a more natural fit)." This is a historical/efficiency choice — deque avoids the periodic reallocation cost of vector::push_back when capacity is exceeded.

7.2 std::queue — FIFO

A queue is First-In, First-Out: insert at the back, remove from the front.

#include <queue>
std::queue<int> q;
q.push(1);
q.push(2);
int front = q.front();   // 1
q.pop();                 // removes 1

Backing container requirements: supports empty, size, front, back, push_back, pop_front. Compatible underlyings: deque, list. Default: deque.

⚠️ Why not vector for queue? Because vector has no pop_front — removing from the front would be O(n).

7.3 std::priority_queue — sorted queue

A queue where elements are kept in sorted order (by operator< by default). Popping always returns the highest-priority element.

#include <queue>
std::priority_queue<int> pq;
pq.push(3); pq.push(1); pq.push(7); pq.push(4);
int big = pq.top();   // 7
pq.pop();

Compatible underlyings: vector, deque. Default: vector.

It is internally implemented as a binary heap, giving:

• push — O(log n)
• pop — O(log n)
• top — O(1)

8. Matching Tasks to Containers (Klefstad Activity)

Corresponds to Topic 8 PPT slide 5 (activity)

Klefstad's slide poses an exercise: pick the right STL container family (Set, Map, Vector) for each task. Here is one reasonable matching with justification — these are the kind of distinctions that the course wants you to be quick about:

⚠️ The general rule of thumb

• Vector when you mostly iterate, append, or index by position
• Map when you look things up by a key and want to associate a value
• Set when you only need membership (or sorted unique elements)
• Unordered_ versions when you don't need sorted iteration

9. STL Iterators

Corresponds to LearnCpp 21.3 + Topic 8 PPT slides 11–13

9.1 What is an Iterator?

An iterator is an object that traverses a container without exposing how the container is implemented. Think of it as a smart pointer that knows how to "move to the next element" in whatever data structure it lives in.

Why iterators matter — quoting LearnCpp 21.3 with course-relevant emphasis:

With many classes (particularly lists and the associative classes), iterators are the primary way elements are accessed.

You can't write myList[5] on a std::list. You can write *it on an iterator that points into the list. The same expression works for a vector iterator, a set iterator, or a map iterator.

💡 Key Insight
An iterator is best visualized as a pointer to an element in the container, with overloaded operators that mimic pointer arithmetic but actually do whatever traversal makes sense for that container.

9.2 Iterator Operations (the Five Big Ones)

From Topic 8 PPT slide 12 + LearnCpp 21.3:

⚠️ Subtle but critical — comparing two iterators with == checks whether they point to the same position, not whether the elements have the same value. To compare values, dereference first: *it1 == *it2.

9.3 begin(), end(), cbegin(), cend()

Every container exposes four basic member functions for getting iterators:

💡 Key Insight — The Half-Open Range [begin, end)
end() does not point at the last element; it points one past it. This is intentional:

for (auto it = c.begin(); it != c.end(); ++it) { ... }

The loop is cleanest when the termination test is it != end(). If end() pointed to the last element, you would need <= (which iterators don't support generically) and special-case the empty container.

9.4 Iterating Through Different Containers

The four examples from LearnCpp 21.3 demonstrate the uniformity of the iterator interface:

Vector:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vect;
    for (int count = 0; count < 6; ++count)
        vect.push_back(count);

    std::vector<int>::const_iterator it;
    it = vect.cbegin();
    while (it != vect.cend()) {
        std::cout << *it << ' ';
        ++it;
    }
    std::cout << '\n';
}
// 0 1 2 3 4 5

List — identical loop, different container:

#include <list>
std::list<int> li;
for (int count = 0; count < 6; ++count)
    li.push_back(count);

std::list<int>::const_iterator it;
it = li.cbegin();
while (it != li.cend()) {
    std::cout << *it << ' ';
    ++it;
}
// 0 1 2 3 4 5

💡 The whole point of iterators — "Note the code is almost identical to the vector case, even though vectors and lists have almost completely different internal implementations!" (LearnCpp 21.3)

Set — same loop again, but the output order is sorted, because sets sort on insertion:

#include <set>
std::set<int> myset;
myset.insert(7); myset.insert(2); myset.insert(-6);
myset.insert(8); myset.insert(1); myset.insert(-4);

auto it = myset.cbegin();
while (it != myset.cend()) {
    std::cout << *it << ' ';
    ++it;
}
// -6 -4 1 2 7 8   (sorted!)

Map — slight twist: each *it is a std::pair, so use it->first and it->second:

std::map<int, std::string> mymap;
mymap.insert(std::make_pair(4, "apple"));
// ...etc

auto it{ mymap.cbegin() };
while (it != mymap.cend()) {
    std::cout << it->first << '=' << it->second << ' ';
    ++it;
}
// 1=banana 2=orange 3=grapes 4=apple 5=peach 6=mango

9.5 Range-Based for Loop (the Modern Idiom)

The four loops above can all be written with the range-based for, which is iterator-driven under the hood:

for (auto e : V)           // copy each element
    std::cout << e;

for (const auto& E : V)    // reference (no copy) to each element
    std::cout << E;

Per Topic 8 PPT slide 12:

• auto e : V — e is a copy of each element
• auto const& E : V — E is a const reference (no copy, can't modify)
• auto& E : V — non-const reference (can modify)

⚠️ Best practice — for non-trivial element types (strings, structs, etc.), prefer const auto& to avoid silently copying every element of the container.

9.6 Custom Iterator: A Linked List Iterator (PPT slide 13)

Klefstad walks through what an iterator looks like for a linked list. This is the conceptual blueprint for writing your own iterators (relevant if HW7+ involves making a container iterable).

The PPT setup:

struct Node { char data; Node * next; };

struct List {
    Node *head;
    struct iterator { /* see below */ };
    iterator begin();
    iterator end();
    // ...
};

Three equivalent ways to walk the list:

List L;

// 1. Manual pointer walk (no STL)
for (Node *p = L.head; p != nullptr; p = p->next)
    std::cout << p->data;

// 2. STL iterator style
for (List::iterator it = L.begin(); it != L.end(); ++it)
    std::cout << (*it).data;

// 3. Range-based for (requires begin/end + iterator operators)
for (auto e : L)
    std::cout << e;

The iterator class itself holds a node pointer and overloads the right operators:

struct List::iterator {
    Node * ptr;
    auto operator*()  -> char&  { return ptr->data; }
    auto operator->() -> Node*  { return ptr; }
    auto operator++() -> iterator& { ptr = ptr->next; return *this; }
    bool operator==(const iterator& other) const { return ptr == other.ptr; }
    bool operator!=(const iterator& other) const { return ptr != other.ptr; }
};

And List::begin() returns iterator{head}; List::end() returns iterator{nullptr}.

💡 Key Insight
Iterators are per-class — every container has to write its own, because the iterator needs to know the data structure's traversal logic. The genius of STL is that algorithms don't have to know this; they only see the iterator interface.

10. Iterator Categories

Corresponds to Topic 8 PPT slide 21

STL iterators come in a hierarchy of capabilities. Each category supports a strict superset of the previous category's operations. Algorithms specify the minimum category they need, which determines which containers they can work with.

💡 PPT Note (slide 21) — "These perform well on modern architectures with cache." Contiguous iterators are the reason vector is so often faster than list in practice, even when complexity analysis says they should be equal: cache prefetching turns contiguous traversal into a near-free operation.

⚠️ Practical implications

• std::sort requires random-access iterators → works on vector, deque, array, string, but not on list or set. std::list provides its own member .sort() instead.
• std::binary_search requires forward iterators (and a sorted range)
• Algorithms that only need to walk once (std::find, std::accumulate, std::copy) work with input iterators — so they also work on streams

11. STL Algorithms

Corresponds to LearnCpp 21.4 + Topic 8 PPT slides 14–15

11.1 Overview

💡 The big idea (LearnCpp 21.4)
Algorithms are implemented as functions that operate using iterators. Each algorithm is written once and works for every container that provides matching iterators — including your own. This is what makes STL composable.

To use any STL algorithm, include <algorithm>. Numeric algorithms (std::accumulate, std::iota) live in <numeric>.

⚠️ Warning (LearnCpp 21.4) — Some combinations of algorithms and containers may not work, may infinite-loop, or may be wildly inefficient. Most notably:

• std::sort on a std::list is a compile error (list iterators aren't random-access)
• But list.sort() (a member function) exists and is efficient
• Don't pass invalid iterator pairs (end before begin) — undefined behavior

11.2 Searching and Min/Max

min_element / max_element / iota (PPT slide 15 + LearnCpp 21.4):

#include <algorithm>   // min_element, max_element
#include <iostream>
#include <list>
#include <numeric>     // iota

int main() {
    std::list<int> li(6);
    std::iota(li.begin(), li.end(), 0);   // fills with 0,1,2,3,4,5

    std::cout << *std::min_element(li.begin(), li.end()) << ' '
              << *std::max_element(li.begin(), li.end()) << '\n';
    return 0;
}
// Output: 0 5

💡 What iota does
iota(begin, end, start) fills a range with consecutive values starting from start: start, start+1, start+2, .... Named after the Greek letter ι (used in APL for the same operation).

find (LearnCpp 21.4 + PPT slide 15):

std::list<int> li(6);
std::iota(li.begin(), li.end(), 0);
auto it = std::find(li.begin(), li.end(), 3);   // returns iterator to 3
li.insert(it, 8);                               // insert 8 just before 3
for (int i : li) std::cout << i << ' ';
// Output: 0 1 2 8 3 4 5

⚠️ Critical idiom — checking find's return value:
When the searched value isn't found, find returns the end iterator. Always check before dereferencing:

if (it == li.end()) { std::cout << "not found\n"; }
else                { /* safe to use *it or it */ }

11.3 Sorting and Reversing

#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vect{ 7, -3, 6, 2, -5, 0, 4 };

    std::sort(vect.begin(), vect.end());
    // vect: -5 -3 0 2 4 6 7

    std::reverse(vect.begin(), vect.end());
    // vect: 7 6 4 2 0 -3 -5
}

Sorting in reverse with a comparator:

#include <functional>
std::sort(vect.begin(), vect.end(), std::greater<int>{});
// Or with a lambda:
std::sort(vect.begin(), vect.end(), [](int a, int b){ return a > b; });

⚠️ Klefstad warning — std::sort does NOT work on std::list. The list iterator is bidirectional, not random-access. Use myList.sort() (the member function) instead — it is also asymptotically faster on lists because it can rearrange links instead of moving elements.

11.4 Reverse Mid-Range, accumulate, transform (PPT slide 15)

Topic 8 PPT slide 15 shows a richer algorithm demo than LearnCpp 21.4. Worth memorizing:

#include <algorithm>
#include <numeric>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> V{2, 5, 4, 1, 6, 3};

    auto pos = min_element(V.begin(), V.end());
    cout << "Min = " << *pos << endl;        // returns iterator to V[3] (= 1)

    sort(V.begin(), V.end());                // V is {1, 2, 3, 4, 5, 6}

    pos = find(V.begin(), V.end(), 3);       // iterator to V[2]
    reverse(pos, V.end());                   // V is {1, 2, 6, 5, 4, 3}

    cout << "Total = " << accumulate(V.begin(), V.end(), 0) << endl;
    // prints Total = 21

    transform(V.begin(), V.end(), V.begin(),
              [](int i){ return i + 1; });
    // V is now {2, 3, 7, 6, 5, 4}
}

Three new algorithms here:

• accumulate(first, last, init) — sums the range starting from init (in <numeric>). The initial value's type determines the result type: accumulate(v.begin(), v.end(), 0) returns int; pass 0.0 for double.
• reverse(first, last) — reverses the range in place; can be applied to any subrange by passing iterators into the middle.
• transform(in_begin, in_end, out_begin, fn) — applies fn to each element of the input range, writing the result starting at out_begin. When out_begin == in_begin, the transform happens in place.

11.5 Other Common Algorithms (Reference)

11.6 Predicate Algorithms — all_of / any_of / none_of (C++11)

The three return bool — they sweep a range with a predicate and answer "all? any? none?":

#include <algorithm>
#include <vector>

std::vector<int> v{2, 4, 6, 8};

bool all_even  = std::all_of (v.begin(), v.end(), [](int x){ return x % 2 == 0; });   // true
bool any_neg   = std::any_of (v.begin(), v.end(), [](int x){ return x  <  0; });      // false
bool none_zero = std::none_of(v.begin(), v.end(), [](int x){ return x ==  0; });      // true

💡 Short-circuit evaluation — all three stop at the first counterexample (all_of / none_of) or first hit (any_of); they don't scan the whole range.

11.7 Erase-Remove Idiom

§11.5 noted that remove(b, e, val) doesn't actually delete — it shifts the elements not equal to val to the front and returns an iterator to the "new logical end." The container's size doesn't change; the tail is leftover junk:

std::vector<int> v{1, 2, 3, 2, 4, 2, 5};
auto new_end = std::remove(v.begin(), v.end(), 2);
// v is now {1, 3, 4, 5, ?, ?, ?}      ← last three are unspecified
// new_end points to the 5th slot (where ? begins)
// v.size() is still 7 — nothing was deleted!

The erase-remove idiom — chop off the leftover with erase(new_end, v.end()):

v.erase(std::remove(v.begin(), v.end(), 2), v.end());
// Now v is {1, 3, 4, 5}, size() == 4

Predicate version — remove_if:

v.erase(std::remove_if(v.begin(), v.end(),
                       [](int x){ return x % 2 == 0; }),
        v.end());
// Removes every even number

Modern C++20 form — std::erase / std::erase_if is a built-in one-liner version of the above:

std::erase(v, 2);                                  // ≡ erase-remove(v, 2)
std::erase_if(v, [](int x){ return x % 2 == 0; }); // ≡ erase-remove_if

⚠️ Don't use this on std::list — list has its own members myList.remove(val) and myList.remove_if(pred), which really delete in O(n) — don't pile on the erase-remove dance (it's pointless on a linked list since list erasure is O(1) node-unlink).

11.8 Range Comparison — equal / mismatch / lexicographical_compare

std::vector<int> a{1, 2, 3, 4};
std::vector<int> b{1, 2, 3, 4};
std::vector<int> c{1, 2, 9, 4};

bool eq = std::equal(a.begin(), a.end(), b.begin());   // true (element-wise ==)

auto [ita, itb] = std::mismatch(a.begin(), a.end(), c.begin());
// ita -> a[2] (= 3), itb -> c[2] (= 9) — first divergence

💡 Just use the container's == — for two standard containers of the same type, a == b already does the size check + element-wise compare and is usually more concise. std::equal is for cases where the types differ but the contents should be equivalent (e.g. a vector<int> against an int[], or comparing a sub-range of a vector<int>).

11.9 Set Algorithms on Sorted Ranges

⚠️ Precondition: both input ranges must be sorted! Same rule as binary_search / lower_bound. These algorithms are not specific to std::set — they apply to any sorted range (a vector, MapArray::keys(), a std::set, etc.).

#include <algorithm>
#include <vector>
#include <iterator>

std::vector<int> a{1, 2, 3, 4, 5};
std::vector<int> b{3, 4, 5, 6, 7};

std::vector<int> out;
std::set_union       (a.begin(), a.end(), b.begin(), b.end(),
                      std::back_inserter(out));   // {1,2,3,4,5,6,7}

out.clear();
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                      std::back_inserter(out));   // {3,4,5}

out.clear();
std::set_difference  (a.begin(), a.end(), b.begin(), b.end(),
                      std::back_inserter(out));   // {1,2}   (in a, not in b)

💡 Cross-week link: HW9 MapArray — it's internally a sorted vector<pair<K,V>>, so these algorithms drop right in — provided your comparator looks only at pair::first. See Week 9 §14.

11.10 Heap Algorithms — <algorithm>

<algorithm> ships heap operations that act on any random-access range — these are exactly what std::priority_queue (§7.3) uses internally, but you can also use them on your own vector to maintain a heap by hand:

#include <algorithm>
#include <vector>

std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6};

std::make_heap(v.begin(), v.end());          // rearrange into a max-heap, v.front() is largest
// v: 9 6 4 3 5 1 2 1   (exact order is implementation-defined, but the root is always max)

std::cout << v.front() << '\n';              // 9 — top of heap

v.push_back(10);                             // first push_back
std::push_heap(v.begin(), v.end());          // then sift the new element up

std::pop_heap(v.begin(), v.end());           // swap top to the back, then fix the heap
int top = v.back();
v.pop_back();                                // actually delete

std::sort_heap(v.begin(), v.end());          // turn the heap into a sorted range (O(n log n))

Default is max-heap (uses <); for min-heap pass std::greater<>{}:

std::make_heap(v.begin(), v.end(), std::greater<>{});

💡 vs. priority_queue — the adapter priority_queue (§7.3) is implemented with make_heap/push_heap/pop_heap — it just wraps a vector plus these functions. Why prefer the raw functions: you can access all elements of the range simultaneously (the adapter only exposes top()), and sort_heap lets you collapse a heap into a sorted range in one call.

11.11 The <numeric> Family

§11.2 already showed iota; §11.4 showed accumulate. <numeric> has a few more workhorses:

#include <numeric>
#include <vector>
#include <functional>

std::vector<int> v{1, 2, 3, 4, 5};

// 1. iota — fill with successive incrementing values (§11.2)
std::iota(v.begin(), v.end(), 0);                                   // {0, 1, 2, 3, 4}

// 2. accumulate — fold (§11.4), with an optional binary op
int sum  = std::accumulate(v.begin(), v.end(), 0);                  // 0+0+1+2+3+4 = 10
int prod = std::accumulate(v.begin(), v.end(), 1, std::multiplies<>{}); // 1*0*1*2*3*4 = 0

// 3. inner_product — dot product of two ranges
std::vector<int> a{1, 2, 3}, b{4, 5, 6};
int dot = std::inner_product(a.begin(), a.end(), b.begin(), 0);     // 1*4+2*5+3*6 = 32

// 4. partial_sum — prefix sums
std::vector<int> ps(v.size());
std::partial_sum(v.begin(), v.end(), ps.begin());                   // {0, 1, 3, 6, 10}

// 5. adjacent_difference — pairwise differences (inverse of partial_sum)
std::vector<int> diff(v.size());
std::adjacent_difference(v.begin(), v.end(), diff.begin());         // {0, 1, 1, 1, 1}

C++17 parallelism-friendly variants (just be aware):

⚠️ accumulate's init type determines the result type — accumulate(v.begin(), v.end(), 0) truncates everything to int even if v is a vector<double>. Pass 0.0 to get a double result.

12. Iterator Adapters

Corresponds to Topic 8 PPT slides 16–18, 22

An iterator adapter is an iterator that wraps something else (a container insertion operation, a stream, or a forward iterator) and exposes the iterator interface — so the wrapped thing can be used anywhere an iterator is expected.

12.1 Insert Iterators — back_inserter, front_inserter, inserter

A regular iterator overwrites elements. An insert iterator grows the container by calling push_back, push_front, or insert on each assignment.

Without insert iterators, copy would write off the end of an empty destination — undefined behavior. With them, the destination grows to fit.

PPT slide 16 — full example:

int main() {
    list<int> L;
    for (int i = 1; i <= 10; ++i)
        L.push_back(i);

    // back_inserter: each assignment calls V.push_back(...)
    vector<int> V;
    copy(L.begin(), L.end(),     // source
         back_inserter(V));       // destination

    // front_inserter: each assignment calls D.push_front(...)
    deque<int> D;
    copy(L.begin(), L.end(),
         front_inserter(D));

    // inserter: each assignment calls S.insert(hint, ...)
    // inserter works on associative containers too
    set<int> S;
    copy(begin(L), end(L),
         inserter(S, std::next(begin(S))));
}

⚠️ Pitfall — there is no back_inserter for set or map, because associative containers decide position automatically. Use inserter(s, s.end()) or simply s.insert(x).

12.2 Stream Iterators — istream_iterator and ostream_iterator

A stream iterator turns cin, cout, ifstream, ofstream into an STL iterator range. This is what lets you copy straight from a file into a container, or transform straight from input to output.

PPT slide 17 — read all words from cin into a vector, sort, print unique words:

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int main() {
    vector<string> V;
    copy(istream_iterator<string>(cin),   // start of source
         istream_iterator<string>(),       // end of source: default-ctor = EOF
         back_inserter(V));                // destination

    sort(begin(V), end(V));

    unique_copy(begin(V), end(V),
                ostream_iterator<string>(cout, "\n"));   // delimiter "\n" between writes
}

Key idioms:

• istream_iterator<T>(stream) — reads T values from stream via >>
• istream_iterator<T>() (default-constructed) — represents end-of-stream (EOF)
• ostream_iterator<T>(stream, "delim") — writes via <<, then writes "delim" after each value

PPT slide 18 — same idea, with files:

#include <iostream>
#include <fstream>
#include <iterator>

int main() {
    ifstream in {"input.data"};
    ofstream out{"output.data"};

    vector<string> V;
    copy(istream_iterator<string>(in),
         istream_iterator<string>(),
         back_inserter(V));

    sort(V.begin(), V.end());

    unique_copy(V.begin(), V.end(),
                ostream_iterator<string>(out, "\n"));
}

💡 Klefstad teaching point
The same algorithm (copy, sort, unique_copy) doesn't care that its iterators come from cin/cout vs. ifstream/ofstream vs. a vector. This is the entire payoff of the STL design.

Activities from PPT slides 19–20:

Fill a vector with integers from cin:

int main() {
    vector<int> V;
    copy(istream_iterator<int>(cin), istream_iterator<int>(),
         back_inserter(V));
}

Print integers from a vector to "out.txt" one per line:

int main() {
    vector<int> V = {0, 2, 4, 6, 8, 10};
    ofstream out{"out.txt"};
    copy(V.begin(), V.end(),
         ostream_iterator<int>(out, "\n"));
}

12.3 Reverse Iterators (PPT slide 22)

A reverse iterator swaps the meaning of ++ and --: incrementing actually moves you backwards through the container. Every container provides rbegin() and rend().

int main() {
    vector<int> V;
    for (int i = 1; i <= 10; ++i)
        V.push_back(i);

    // Print 10 9 8 ... 1
    copy(V.rbegin(), V.rend(),
         ostream_iterator<int>(cout, " "));
}

⚠️ Conceptual trap — rbegin() points to the last element (the start of the reverse traversal), not to end() - 1 directly. It is a different kind of iterator. To get the underlying forward iterator, use .base().

13. Function Objects in Algorithms

Corresponds to Topic 8 PPT slide 24

STL algorithms that need a "callable" — for_each, transform, sort, find_if, etc. — can take any of:

• a free function (passing its name decays to a function pointer)
• a function pointer explicitly
• a class with operator() (a functor)
• a lambda (Week 7)

The algorithm doesn't care which; it just calls fn(x) or fn(a, b). This is the function object abstraction.

PPT slide 24 — two examples:

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

void print(int i) {
    cout << i << ' ';
}

int main() {
    list<int> L;
    for (int i = 1; i <= 5; ++i)
        L.push_back(i);

    // print all ints in the list
    for_each(begin(L), end(L), print);   // 'print' is passed as a function pointer
}

int square(int i) {
    return i * i;
}

int main() {
    list<int> L1, L2;
    for (int i = 1; i <= 9; ++i)
        L1.push_back(i);

    // put squares of L1 into L2
    transform(begin(L1), end(L1),
              back_inserter(L2), square);
}

The same examples with lambdas (more idiomatic in modern C++):

for_each(begin(L), end(L), [](int i){ cout << i << ' '; });

transform(begin(L1), end(L1), back_inserter(L2),
          [](int i){ return i * i; });

💡 Why function objects matter
Without callable parameters, algorithms would need an explosion of overloads. sort(v.begin(), v.end()) uses <; sort(v.begin(), v.end(), greater<int>{}) uses >; sort(v.begin(), v.end(), [](X a, X b){ return a.name < b.name; }) uses an arbitrary custom rule. Same algorithm, different policy — chosen by the caller.

14. Ranges (C++20)

Corresponds to Topic 8 PPT slide 25

In all the examples so far, we've been passing pairs of iterators: sort(v.begin(), v.end()). This is verbose and error-prone — pass the wrong begin/end and you have UB.

C++20 ranges let you pass a range (typically the container itself) directly:

// Range-based for loop (works since C++11)
for (auto e : v)
    cout << e;

// Algorithm calls (the new C++20 way)
sort(v.begin(), v.end());   // old: still works
sort(v);                    // C++20 ranges: uses v's range = v.begin()..v.end()

The C++20 <ranges> library defines std::ranges::sort, std::ranges::find, etc., which all accept ranges. Beyond convenience, ranges also enable views — lazy, composable transformations:

auto evens_squared = v
                   | std::views::filter([](int x){ return x % 2 == 0; })
                   | std::views::transform([](int x){ return x * x; });

💡 PPT pointer
For more, see https://en.cppreference.com/w/cpp/ranges. In ICS 45C you mostly only need to know that ranges exist and accept the container directly; the classic two-iterator form is still ubiquitous and entirely correct.

15. I/O Streams — The iostream Library

Corresponds to LearnCpp 28.1

15.1 Why I/O Lives in the Library (not the language)

I/O functionality is not part of the core C++ language. It is provided by the standard library, in the std namespace. That's why every program needs #include <iostream> to use cin/cout.

When you include <iostream>, you gain access to a class hierarchy for I/O. Importantly, that hierarchy uses multiple inheritance (which was advised against in Week 7 / Week 6) — but the library has been carefully designed and tested to avoid the typical pitfalls, so you can use it without worry.

15.2 What is a Stream?

💡 Key Insight (LearnCpp 28.1)
A stream is just a sequence of bytes that can be accessed sequentially. Over time, a stream may produce or consume potentially unlimited amounts of data.

Two flavors:

• Input streams hold data from a producer (keyboard, file, network). When you press a key, the byte enters the input stream and waits there until your program is ready for it.
• Output streams hold data for a consumer (monitor, file, printer). When you write, the data sits in the output stream until the consumer is ready.

Some devices (files, networks) are both producers and consumers.

💡 The win — once you learn stream operations, the same operations work for keyboards, files, network sockets, and string buffers. The OS hides the difference.

15.3 The Class Hierarchy

The key classes you should be able to name:

A simplified diagram:

            ios
           /   \
     istream   ostream
           \   /
          iostream

(Yes, that's multiple inheritance — the dreaded diamond. But again, the library handles it carefully.)

15.4 Standard Streams

C++ ships four pre-connected standard stream objects that you can use immediately:

💡 cerr vs. clog — both go to standard error, but cerr is unbuffered (good for crash-time messages that must appear before the program dies) and clog is buffered (good for diagnostic logs where bulk efficiency matters). clog is rarely seen in practice.

💡 Buffering explained
Buffered output collects bytes in memory and writes them in chunks (faster). Unbuffered output writes each byte immediately (slower, but you see results right away — and you don't lose anything if the program crashes mid-buffer).

16. Input with istream

Corresponds to LearnCpp 28.2

16.1 The Extraction Operator >>

The extraction operator (>>) reads a value from an input stream. C++ has built-in extractions for every fundamental type. You can also overload >> for your own classes.

int n;
std::cin >> n;            // read an int

double d;
std::cin >> d;            // read a double

char c;
std::cin >> c;            // read a single non-whitespace char

std::string s;
std::cin >> s;            // read a non-whitespace word

16.2 Buffer Overflow Danger with C-Strings

char buf[10] {};
std::cin >> buf;          // ⚠ user could enter 18 characters → buffer overflow → UB

⚠️ Best Practice (LearnCpp 28.2)
Generally speaking, it's a bad idea to make any assumption about how many characters your user will enter.

Fix: setw() from <iomanip> limits the number of characters read:

#include <iomanip>
char buf[10] {};
std::cin >> std::setw(10) >> buf;   // reads at most 9 chars (room for '\0' terminator)

16.3 Extraction Skips Whitespace

Reminder (LearnCpp 28.2) — the extraction operator skips whitespace (spaces, tabs, newlines).

int main() {
    char ch{};
    while (std::cin >> ch)
        std::cout << ch;
}
// Input:  Hello my name is Alex
// Output: HellomynameisAlex      ← all spaces and newlines eaten

To keep the whitespace, use get().

16.4 get()

std::cin.get(ch) reads one character, including whitespace.

char ch{};
while (std::cin.get(ch))
    std::cout << ch;
// Input:  Hello my name is Alex
// Output: Hello my name is Alex   ← spaces preserved

There is also a string-buffer overload: cin.get(buf, n) reads up to n-1 characters into buf and adds the terminator.

char strBuf[11] {};
std::cin.get(strBuf, 11);     // reads up to 10 chars
std::cout << strBuf << '\n';
// Input:  Hello my name is Alex
// Output: Hello my n             ← only the first 10 chars

⚠️ get() does not consume the delimiter — usually the newline character.
So a second get() immediately sees the leftover \n and stops without reading anything new.

char strBuf[11]{};
std::cin.get(strBuf, 11);   // reads "Hello!"
std::cout << strBuf << '\n';

std::cin.get(strBuf, 11);   // sees leftover '\n', stops immediately!
std::cout << strBuf << '\n';
// Output:
// Hello!
//                          ← (empty)

16.5 getline() — Reads and Discards the Delimiter

std::cin.getline(buf, n) behaves like get, but consumes and discards the trailing newline. This is what you usually want for reading whole lines.

char strBuf[11]{};
std::cin.getline(strBuf, 11);
std::cout << strBuf << '\n';

std::cin.getline(strBuf, 11);   // works correctly this time
std::cout << strBuf << '\n';

16.6 gcount() — How Many Were Read

After a getline() (or get() with a buffer), cin.gcount() returns the number of characters extracted (including the discarded delimiter).

char strBuf[100]{};
std::cin.getline(strBuf, 100);
std::cout << strBuf << '\n';
std::cout << std::cin.gcount() << " characters were read\n";

16.7 std::getline for std::string (the Free Function)

There is a special non-member getline in <string> that reads a whole line into a std::string. Use this in modern C++ — don't deal with char[] buffers if you can avoid it.

#include <string>
#include <iostream>

int main() {
    std::string strBuf;
    std::getline(std::cin, strBuf);
    std::cout << strBuf << '\n';
}

⚠️ Classic mixed-mode bug

int n;
std::cin >> n;                    // reads number, leaves '\n' in buffer
std::string line;
std::getline(std::cin, line);     // reads empty line — eats the leftover '\n'

Fix: between the two, call std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');.

16.8 Other Useful istream Functions

From LearnCpp 28.2:

These are useful for hand-written parsers (look-ahead with peek(), error recovery with putback()).

For everything else, the reference is https://en.cppreference.com/w/cpp/io/basic_istream.

16.9 Stream State — Why while (std::cin >> x) Terminates

Every stream carries a small set of state bits that say whether it's still usable. After every operation (>>, getline(), read()), these bits get updated. Reading from std::cin doesn't throw on bad input — it sets a bit and silently moves on. You have to check.

The four state bits

How you check them

Why the read loop works

int x;
while (std::cin >> x) {           // tests stream's bool conversion → !fail()
    std::cout << x << '\n';
}
// Loop exits when extraction failed (bad input) OR end-of-stream reached.

std::cin >> x returns std::cin (by reference). Converting it to bool calls !fail(). So the loop runs as long as the last extraction succeeded. When you type done instead of a number, failbit is set, the loop ends.

Recovering from a failed extraction

After a failed read, the stream is "stuck" — failbit is set, so every subsequent read fails immediately, and the bad input is still sitting in the buffer. You need two steps:

int n;
while (!(std::cin >> n)) {
    std::cin.clear();                                                       // 1. reset state bits to goodbit
    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');     // 2. throw away the bad input
    std::cout << "Please enter a number: ";
}

• clear() resets all error bits (also takes an optional argument if you want to set specific bits).
• ignore(...) discards the offending characters so the next read sees fresh input.

Mnemonic: clear then ignore — clear the state, then clear the buffer. Forget one and your input loop spins forever.

17. Output with ostream and ios

Corresponds to LearnCpp 28.3

17.1 The Insertion Operator <<

The insertion operator puts data into an output stream. Predefined for every built-in type; you can overload it for your own classes.

std::cout << "Hello, " << name << ", age " << age << '\n';

The interesting Week 8 content here is formatting: controlling how the data is written (base, precision, width, etc.).

17.2 Two Ways to Format: Flags vs. Manipulators

Both istream and ostream derive from std::ios, which holds the formatting state. You can change that state in two ways:

• Flags — boolean state variables, turned on with setf() and off with unsetf()
• Manipulators — objects you stream into the output (e.g. std::hex, std::setw(10)); they toggle the relevant flags for you

17.3 Flags via setf / unsetf

std::cout.setf(std::ios::showpos);   // turn on the "show + before positive nums" flag
std::cout << 27 << '\n';             // prints +27
std::cout.unsetf(std::ios::showpos); // turn it off
std::cout << 28 << '\n';             // prints 28

Multiple flags at once using bitwise OR |:

std::cout.setf(std::ios::showpos | std::ios::uppercase);
std::cout << 1234567.89f << '\n';    // prints +1.23457E+06