Learn/C++/13. Maps and sets in depth
Lesson 13 of 15
Sign in

C++, lesson 13

Maps and sets in depth

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.

Ordered or unordered?

ContainerStoresOrderTypical cost
std::map<K, V>unique keys with valuessorted by keyO(log n)
std::unordered_map<K, V>

2 exercises to try what you just read.

Exercise 1

Anagram groups

Press Ctrl Enter or Check to test your code.

Exercise 2

Club members

Press Ctrl Enter or Check to test your code.

unique keys with values
none (unpredictable)
O(1) on average
std::set<T>unique valuessortedO(log n)
std::unordered_set<T>unique valuesnoneO(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.

Counting

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:

Grouping

When the value is itself a container, operator[] gives you an empty one the first time a key appears, ready to fill:

Looking up without inserting

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.

Sets

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.

Set algorithms

<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.

Further reading

  • cppreference: std::unordered_map
  • cppreference: std::set
  • cppreference: std::set_intersection
  • cppreference: std::set_union
  • cppreference: std::set_difference
  • cppreference: std::back_inserter

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 2
Input:
listen tea silent eat enlist ate cat tea
Output:
act: cat
aet: ate eat tea
eilnst: enlist listen silent
Input:
ana ben cara dev ben
dev eli ana
Output:
Both: ana dev
Chess only: ben cara
Drama only: eli
Total: 5