Sets and Maps

set and map: fast membership tests, counting distinct values and frequencies in O(log n).

Checking "have we seen this number before" by scanning an array costs O(n) per check. The set and map structures do it in O(log n), because internally they keep elements in a balanced tree. • std::set — a set of unique elements: insert, count, erase. Keeps elements sorted. • std::map — a "key → value" dictionary: count[x]++ creates the key with a zero on first access all by itself. There are also hash versions, unordered_set / unordered_map, with average O(1) — faster, but unordered. The classic: find the first repeated element of a stream.

Try it yourself — the code is editable

Input (sample — feel free to edit)

The first repeat. Enter: 6, then 3 1 4 1 5 9

map is indispensable for frequency analysis: in one pass we count how many times each word occurs. Iterating a map yields the keys in sorted order — often that is a bonus to exploit, not a coincidence.

Try it yourself — the code is editable

Input (sample — feel free to edit)

Word frequencies. Enter: 5, then: apple banana apple cherry banana

Guidelines for choosing: • need sorted order or "the nearest element" — set/map; • need only speed — the unordered versions; • need duplicates — multiset. Task: given n numbers, print those that occur exactly once, in increasing order (a map solves this in six lines). Mark the lesson as completed and move on to recursion.