Unordered Maps and Sets
A map and a set always keep their keys sorted. Keeping that order costs a little time on every insert and every lookup. Often you never need the order. You only want to store a value and find it again fast. For this, C++ has unordered_map and unordered_set. To use them, add #include <unordered_map> or #include <unordered_set> at the top.
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<string, int> stock;
stock["pens"] = 12;
stock["ink"] = 3;
stock["paper"] = 40;
stock["glue"] = 5;
cout << stock["ink"] << "\n";
for (auto& [name, count] : stock) {
cout << name << ": " << count << "\n";
}
return 0;
}
Output:
3
glue: 5
paper: 40
ink: 3
pens: 12
You use an unordered_map the same way as a map. Square brackets add, change and read a value, and the loop gives you each key with its value.
Now look at the order of the loop. It is not alphabetical, and it is not the order we added the keys either. An unordered map decides where each key goes by computing a number from the key, called a hash. This lets it jump almost straight to a key, which is why lookups are usually faster than in a map. The cost is that the loop order looks random. It can be different on another compiler, or after you add more keys. Never write code that depends on it.
unordered_set
An unordered_set is a set without the sorting. It keeps each value only once, and it has the same insert, count, erase and size:
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
unordered_set<int> seats = {12, 4, 9};
seats.insert(4);
cout << seats.size() << "\n";
cout << seats.count(9) << "\n";
seats.erase(9);
cout << seats.count(9) << "\n";
return 0;
}
Output:
3
1
0
Seat 4 was already in the set, so inserting it again changed nothing, and the size stayed 3.
Counting things
In the Maps lesson you saw that reading a missing key adds it with the value 0. That makes counting short: counts[c]++ starts each new key at 0 and adds 1. To print the counts in a fixed order, keep a vector of the keys in the order they first appear:
string text = "banana";
unordered_map<char, int> counts;
vector<char> order;
for (char c : text) {
if (counts.count(c) == 0) {
order.push_back(c);
}
counts[c]++;
}
for (char c : order) {
cout << c << " " << counts[c] << "\n";
}
Output:
b 1
a 3
n 2
The if runs before counts[c]++, so count(c) is 0 only the first time a letter appears. The order vector then gives the letters in a fixed order, b, a, n, no matter how the map stores them.
Which one to choose
| Use | When |
|---|---|
unordered_map, unordered_set | you only add, find and remove (counting, "have I seen this before?") |
map, set | you need the keys in sorted order |
In coding interviews, the unordered versions are the usual first choice.
In the exercise, count how many times each word appears, and print each word with its count in the order the words first appear.