Skip to content

Quiz 14 — The STL with OOP

Ten questions on using the standard containers and algorithms as the vocabulary of a designed program, and on choosing a container for a stated reason.

Attempt all of them closed-book, then mark yourself against the answers.

Concepts: containers · iterators · algorithms · lambdas · iterator invalidation · complexity · container choice.

Q1. (MCQ) Which container keeps keys sorted with O(log n) lookup?

  • A. std::vector
  • B. std::unordered_map
  • C. std::map
  • D. std::list

Q2. (true/false) It is safe to write for (auto it = v.begin(); it != v.end(); ++it) if (bad(*it)) v.erase(it);.

Q3. (multiple-select) Which container choices are appropriate? Select all that apply.

  • A. vector for append-and-iterate
  • B. set for unique values printed in order
  • C. list for random access by index
  • D. unordered_map for lookup by integer id where order is irrelevant

Q4. (predict) Write the two output lines.

#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';
}

Q5. (predict) Write the three output lines.

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

int main() {
    std::map<std::string, int> stock;
    stock["nut"] = 300;
    stock["bolt"] = 120;
    stock.insert({"bolt", 999});
    std::cout << stock["bolt"] << '\n';
    std::cout << stock.size() << '\n';
    for (const auto& [name, count] : stock) std::cout << name << ':' << count << '\n';
}

Q6. (debug) This returns a lambda that refers to memory that no longer exists. Explain and fix the capture.

#include <functional>

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

Q7. (analysis) A program repeatedly searches a collection of 100 000 records by name, and also prints them in alphabetical order. Choose two containers for the two jobs and justify each with a complexity claim.

Q8. (short answer) What is an iterator, and why does it let std::sort work for both vector<int> and vector<string>?

Q9. (design) A lending desk must (a) find an item by catalogue number, (b) list items in number order, and (c) count how many are on loan. Sketch the containers you would use, and state the invariant that keeps them consistent.

Q10. (analysis) Why is "I prefer std::list" not a design justification, and what would you collect instead before changing a container?

Scoring: mark yourself with the answers, then read the self-assessment guide.