The set — a collection of unique things with instant membership tests — and then the payoff: one flowchart to pick the right container for any access pattern.
🎯 The whole point: grab the right container, fastA set is a map with keys and no values — a collection of unique elements answering "is this in here?" fast. Once you know sets, you've met every container family — so this lesson ends with the selection rule: choose by access pattern, not by habit.
When you only care whether something is present (not a value attached to it), use a set. Like maps, there's an ordered tree version and a hashed version — same trade-off as Lesson 4.
#include <unordered_set> std::unordered_set<std::string> seen; seen.insert("ada"); seen.insert("ada"); // no-op — sets hold UNIQUE elements seen.size(); // 1 if (seen.contains("ada")) { } // C++20; O(1) average membership test if (seen.count("bob")) { } // 0 or 1 — works pre-C++20 seen.erase("ada");
Drop a range into a set and the duplicates vanish: std::unordered_set<int> u(v.begin(), v.end()); gives the unique values.
The canonical use: track visited nodes, processed IDs, seen tokens. if (!seen.insert(x).second) continue; — insert returns whether it was new.
set bonusstd::set keeps elements sorted and supports range queries (lower_bound/upper_bound) — a sorted unique collection for free.
Source: cppreference — std::unordered_set · std::set.
You now know all the families. The skill the mission is after is choosing among them without thinking hard. Ask one question first — "how do I need to reach my data?" — and follow the tree:
Source: synthesized from cppreference — Containers & Core Guidelines SL.con.2. The same chart lives in the cheat sheet.
| What you need | Container | Why |
|---|---|---|
| A growable list, index access | vector | contiguous, O(1) index, the default |
| Fixed size known at compile time | array | no heap, no growth, zero overhead |
| Fast push/pop at both ends | deque | O(1) at front and back |
| Look up a value by key | unordered_map / map | O(1) avg / O(log n) sorted |
| Unique items, "is it in here?" | unordered_set / set | fast membership; set is sorted |
| Last-in-first-out | stack | LIFO discipline (Lesson 6) |
| First-in-first-out | queue | FIFO discipline (Lesson 6) |
| Always pull the largest/smallest next | priority_queue | a heap (Lesson 6) |
vector and unordered_map cover the large majority of needs. Knowing precisely when to leave them — that's the expertise this chart encodes.unordered_map<string,string> — lookup by key, order irrelevant.
priority_queue (or a sorted vector) — always want the max.
unordered_set<long> — membership + automatic dedup.
stack — last action undone first (LIFO).
vector — sequence, index access, iterate fast.
map<time,Event> — need sorted keys + ranges.
set is best described as:set?set is sorted (tree); unordered_set is hashed.unordered_set<T> u(v.begin(), v.end()); — duplicates collapse automatically.vector (sequences) and unordered_map (key lookup). Leave them only when an access pattern demands it.insert tell you if an element was new?pair<iterator,bool>; the .second bool is true if it was inserted, false if it was already present.Best drill for this lesson: throw me a scenario — "I need to map URLs to hit counts and print the top 10" — and I'll walk the flowchart with you and name the container(s). Then we move from data structures to operating on them.