Bank 12 — The STL with OOP¶

Eleven exercises on using the standard containers and algorithms as the vocabulary of a designed program, and on choosing a container with reasons. Module 14. Levels L1–L6.

Solutions are in Solutions and answers; nudges are in Hints. Attempt first.

Exercises¶

E128 — Three parts `L1` `concept`¶

Task. In one sentence each: what are the roles of a container, an iterator and an algorithm in the STL, and how do they fit together? Then answer: why can std::sort sort a std::vector<int> and a std::vector<std::string> without being written twice?

E129 — Sort with a rule `L2` `predict`¶

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{ 5, 1, 4, 2, 3 };
    std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';

    auto isEven = [](int n) { return n % 2 == 0; };
    std::cout << std::count_if(v.begin(), v.end(), isEven) << '\n';
}

Task. Write both output lines. What does a > b as the comparison do to the ordering compared with the default? And what does the lambda capture here — anything, or nothing?

E130 — Sum and filter `L2` `complete`¶

#include <iostream>
#include <numeric>
#include <string>
#include <vector>

struct Order {
    std::string id;
    double      amount;
};

int main() {
    std::vector<Order> orders{
        { "A-1", 120.0 },
        { "A-2",  40.0 },
        { "A-3", 250.0 },
    };

    // TODO (1): total, using std::accumulate and a lambda that adds each amount
    // TODO (2): count of orders over 100, using std::count_if

    std::cout << "total " << total << '\n';
    std::cout << "large " << large << '\n';
}

Task. Write the two expressions so the program prints total 410 and large 2. In the accumulate lambda, what should the initial value be, and why does its type matter?

E131 — The parts bin `L2` `trace` `scenario`¶

A workshop looks up parts by name and, separately, keeps them sorted for a price report.

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

int main() {
    std::map<std::string, int> stock;
    stock["bolt"]  = 120;
    stock["nut"]   = 300;
    stock["washer"] = 80;
    stock.insert({ "bolt", 999 });     // duplicate key

    std::cout << stock["bolt"] << '\n';
    std::cout << stock.size() << '\n';

    for (const auto& [name, count] : stock)
        std::cout << name << ':' << count << ' ';
    std::cout << '\n';
}

Task. Write all three output lines. Why did the duplicate insert not change the count for "bolt", and in what order are the three keys printed?

E132 — Replace the loop `L3` `modify`¶

#include <iostream>
#include <vector>

int main() {
    std::vector<int> readings{ 12, -3, 7, -8, 5, -1 };

    int negatives = 0;
    for (int r : readings) {
        if (r < 0) ++negatives;
    }

    std::vector<int> positives;
    for (int r : readings) {
        if (r > 0) positives.push_back(r);
    }

    std::cout << negatives << ' ' << positives.size() << '\n';
}

Task. Rewrite both loops using standard algorithms (std::count_if, std::copy_if with std::back_inserter). Keep the output identical (3 3). Then say, honestly, which version you find more readable and why — the answer is not always "the algorithm".

E133 — Erasing while looping `L3` `debug` `scenario`¶

An inventory tool removes expired items.

#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> items{ "ok", "expired", "ok", "expired", "expired" };

    for (auto it = items.begin(); it != items.end(); ++it) {
        if (*it == "expired") {
            items.erase(it);          // line E
        }
    }

    std::cout << items.size() << '\n';
    for (const std::string& s : items) std::cout << s << ' ';
}

Task. Explain why line E is wrong (what does erase do to the iterator?), predict the wrong result you get on a typical implementation, and give the correct idiom for removing elements during iteration. (std::remove_if with erase is the idiomatic answer; the erase-returns-the-next-iterator form is also acceptable.)

E134 — Ordered by key `L2` `predict`¶

#include <iostream>
#include <set>
#include <string>

int main() {
    std::set<std::string> tags;
    tags.insert("zebra");
    tags.insert("apple");
    tags.insert("mango");
    tags.insert("apple");        // again

    std::cout << tags.size() << '\n';
    for (const std::string& t : tags) std::cout << t << ' ';
    std::cout << '\n';
}

Task. Write both output lines. In what order are the tags iterated, and why? What would you need to change to iterate them in insertion order instead?

E135 — Pick the container `L4` `analyze`¶

For each job, choose one of std::vector, std::list, std::map, std::unordered_map, std::set, and justify in one sentence (give a complexity where it is the deciding factor):

a list you only ever append to and then iterate from front to back;
a phone book searched by name;
a cache searched by an integer id where order does not matter;
a queue of jobs where you insert and remove in the middle often;
a set of unique usernames you must print in alphabetical order.

Task. Then answer: why is std::vector the right default until a measurement says otherwise?

E136 — A lambda that outlives its data `L4` `debug` `scenario`¶

#include <functional>
#include <iostream>

std::function<int()> makeCounter() {
    int count = 0;
    return [&]() { return ++count; };      // capture by reference
}

int main() {
    auto counter = makeCounter();
    std::cout << counter() << '\n';
    std::cout << counter() << '\n';
}

Task. Explain what the returned lambda captured and why count no longer exists by the time the lambda runs. Say whether the output is defined, then fix the capture so the counter works correctly forever. Which capture (by value, and mutable?) is needed?

E137 — Design an indexed lookup `L5` `design` `stl` `scenario`¶

A lending desk must (a) find an item by its catalogue number quickly, (b) list items in catalogue-number order for the shelf report, and (c) count how many items are on loan. Items are added and removed as the collection changes.

Task. Design the lookup. Give:

the containers you chose and what each one holds;
why a single container is a poor fit for all three jobs at once;
the operations you expose, and which container each uses;
the invariant that keeps the containers consistent when an item is added or removed;
one complexity you can now state with a reason (lookup, order-listing or count).

How you will be judged. On whether your containers stay consistent, and on whether each choice has a stated reason rather than a habit.

E138 — Measure, then decide `L6` `refactor` `stl` `scenario`¶

A reporting module does three things with hand-written loops: finds the highest value, counts items matching a predicate, and builds a sorted list of names. The loops are correct but the code is long, and a reviewer asked whether a different container would be faster.

Task. Write a plan that both simplifies and measures. It must:

name the standard algorithm that replaces each loop;
say what evidence you would collect before changing any container (not a guess — what would you count or time?);
state which container you would try first and why, and what result would make you keep the original;
name one place where you would not replace the loop, and why.

Success. You replaced the loops and justified the container with measurement, not intuition.

Previous topic: Exceptions · Next topic: SOLID and design patterns · Hints: hints.md · Solutions: solutions.md

Bank 12 — The STL with OOP¶

Exercises¶

E128 — Three parts L1 concept¶

E129 — Sort with a rule L2 predict¶

E130 — Sum and filter L2 complete¶

E131 — The parts bin L2 trace scenario¶

E132 — Replace the loop L3 modify¶

E133 — Erasing while looping L3 debug scenario¶

E134 — Ordered by key L2 predict¶

E135 — Pick the container L4 analyze¶

E136 — A lambda that outlives its data L4 debug scenario¶

E137 — Design an indexed lookup L5 design stl scenario¶

E138 — Measure, then decide L6 refactor stl scenario¶