Quiz 14 — Answers¶
Q1 — C, std::map. It keeps keys sorted and offers O(log n) lookup. unordered_map
(B) is O(1) average but unordered; vector (A) is not a keyed container; list (D) has no
such lookup.
Q2 — False. erase(it) invalidates the iterator you are holding (and returns the next
one), so ++it then skips an element. Use it = v.erase(it); (without the ++), or the
remove_if + erase idiom.
Q3 — A, B, D. Append-and-iterate suits vector (A); unique values printed in order
suits set (B); lookup by integer id where order is irrelevant suits unordered_map (D).
list (C) is wrong for random access by index — that is O(n) in a list and O(1) in a
vector.
Q4 —
The comparator a > b sorts descending. In the sorted vector the even numbers are 4 and 2,
so count_if returns 2.
Q5 —
insert({"bolt", 999}) does not overwrite the existing key — only operator[] would —
so "bolt" stays 120. The map has 2 entries and iterates in sorted key order: bolt, then
nut.
Q6 — [&] captures count by reference. count is a local of makeCounter, so when
the function returns the lambda refers to a destroyed variable — undefined behaviour.
Fix: capture by value, and mark the lambda mutable so it can change its own copy:
Q7 — Use std::unordered_map<std::string, Record> for the name lookup — average O(1)
per search — and either a second structure or a sort for the alphabetical listing:
std::map<...> gives ordered iteration at O(log n) insertion, or sort a vector once when
the report is needed. Searching a vector linearly is O(n) per search, which is the cost
to avoid at 100 000 records.
Q8 — An iterator names a position in a container and lets algorithms move from one
element to the next without knowing the container's layout. std::sort is a template
over the iterator and element types, so the same algorithm is instantiated for int and for
std::string — one implementation, many element types.
Q9 — One std::unordered_map<CatalogueNumber, Item*> for lookup by number, and one
std::map<CatalogueNumber, Item*> (or a sorted view) for the ordered listing; keep a
running count as items are lent and returned. The invariant: both containers hold the same
items and are updated together in the one method that adds or removes an item — otherwise
they drift and the report disagrees with the lookup.
Q10 — Because "I prefer" is a habit, not a reason — the container must fit the access pattern, not the author's taste. Before changing one, collect evidence: which operations dominate (lookup, insertion, iteration), their sizes and frequencies, and the complexity each container gives for them. Measure or count, then decide. A change without that evidence is as likely to slow the program down as to speed it up.
Marking. One point per question (Q3 all-or-nothing). Then read Marking Yourself.