C++, lesson 13
The collections lesson introduced std::map for lookups. This lesson looks at the patterns you
will use again and again, and at the other associative containers: std::unordered_map,
std::set and std::unordered_set.
| Container | Stores | Order | Typical cost |
|---|---|---|---|
std::map<K, V> | unique keys with values | sorted by key | O(log n) |
std::unordered_map<K, V> |
2 exercises to try what you just read.
| unique keys with values |
| none (unpredictable) |
| O(1) on average |
std::set<T> | unique values | sorted | O(log n) |
std::unordered_set<T> | unique values | none | O(1) on average |
The unordered versions are hash tables and are usually faster for pure lookups. The ordered versions are balanced trees and give you sorted iteration for free. If you are going to print the results in order anyway, an ordered container saves you a sort.
Because operator[] creates a missing key with a zero value, counting is a one-liner:
To print the counts sorted by frequency, copy the pairs into a vector and sort it, since a map can only be ordered by its key:
When the value is itself a container, operator[] gives you an empty one the first time a key
appears, ready to fill:
operator[] is convenient but changes the map, and it can't be used on a const map. For a pure
lookup use find (returns end() when absent), count (0 or 1), or at (throws
std::out_of_range when absent). erase(key) removes an entry. insert and C++17's
try_emplace add a key only if it isn't there yet, leaving an existing value alone.
A std::set keeps each value once, in sorted order. Inserting a duplicate does nothing, and
insert tells you whether it happened:
A set is the natural tool for removing duplicates, checking membership quickly, and keeping a sorted collection of unique items.
<algorithm> has functions that combine two sorted ranges, which is exactly what iterating a
std::set gives you. They write their output through an output iterator;
std::back_inserter(v) turns a vector into one that grows with push_back.
std::back_inserter lives in <iterator>. The inputs could just as well be sorted vectors; the
algorithms only need sorted ranges.
Two words are anagrams if they use exactly the same letters, like listen and silent. Their
letters sorted alphabetically give the same signature (eilnst). Read lowercase words until
the input ends. Group them by signature, ignoring repeated words. Print one line per group, in
order of signature: the signature, a colon, then the group's words in alphabetical order.
A std::map<std::string, std::set<std::string>> does all the sorting and de-duplicating for you.
Two clubs share a hall. The first input line lists the names in the chess club, the second line
the names in the drama club (single words separated by spaces; a line may be empty, and a name
may repeat). Print four lines, with names in alphabetical order separated by spaces and - for
an empty list:
Total is the number of different people in at least one club. Read each line with
std::getline, split it into a std::set<std::string>, and use the set algorithms.
std::unordered_map<std::string, int> counts;
std::string word;
while (std::cin >> word) {
++counts[word];
}std::vector<std::pair<std::string, int>> rows(counts.begin(), counts.end());
std::sort(rows.begin(), rows.end(), [](const auto& a, const auto& b) {
return a.second != b.second ? a.second > b.second : a.first < b.first;
});std::map<char, std::vector<std::string>> by_letter;
for (const auto& name : names) {
by_letter[name[0]].push_back(name);
}
for (const auto& [letter, group] : by_letter) {
std::cout << letter << ": " << group.size() << " names\n";
}std::set<std::string> seen;
if (auto [it, added] = seen.insert("ada"); !added) {
std::cout << "already seen\n";
}std::set<int> a{1, 2, 3, 4};
std::set<int> b{3, 4, 5};
std::vector<int> both, either, only_a;
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(both)); // 3 4
std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(either)); // 1 2 3 4 5
std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(only_a)); // 1 2Input:
listen tea silent eat enlist ate cat tea
Output:
act: cat
aet: ate eat tea
eilnst: enlist listen silentInput:
ana ben cara dev ben
dev eli ana
Output:
Both: ana dev
Chess only: ben cara
Drama only: eli
Total: 5