map and set
GOALCount things with a map, and remove duplicates with a set.
"How many times did each word appear?" is awkward with an array. A map stores a value for each key — word to count. A set only remembers whether something is present, dropping duplicates by itself. Both keep their keys in SORTED order.
ON THIS PAGE
//THE EXAMPLE
#include <iostream>
#include <map>
#include <set>
#include <string>
using namespace std;
int main() {
map<string, int> count;
count["cat"]++;
count["dog"]++;
count["cat"]++;
for (auto& pair : count) {
cout << pair.first << "=" << pair.second << " ";
}
cout << endl;
set<int> seen;
seen.insert(5);
seen.insert(2);
seen.insert(5);
cout << seen.size() << endl;
cout << (seen.count(2) ? "yes" : "no") << endl;
return 0;
}cat=2 dog=1 2 yes
//LINE BY LINE
Watch it run
The map starts empty. Not a single key in it.
Which container to reach for
Three questions decide it: does order matter, are duplicates allowed, and are you looking things up by a key?
| What you need | Container |
|---|---|
| Дараалал хэвээр, давхардал зөвшөөрнө / Keep the order, allow duplicates | vector |
| Давхардалгүй, эрэмбэтэй / No duplicates, kept sorted | set |
| Түлхүүр → утга / Key to value | map |
| Зөвхөн байгаа эсэхийг мэдэх / Only membership | set |
Searching a vector is O(n), a set is O(log n). But on small data a vector is actually faster — at 20 elements you will not notice.
The counting idiom
"How many times did each thing appear?" is a very common problem. One line in both languages — but not the same line.
map<string, int> count;
for (const string& w : words) {
count[w]++; // missing keys start at 0
}Even READING count["x"] creates the entry. To test without creating, use count.count("x") or count.find("x").