C++ ordered maps and frequencies
Count keys and traverse them in sorted order.
C++
#include <iostream>
#include <map>
#include <string>
#include <cassert>
int main() {
std::map<std::string, int> counts;
for (const std::string word : {"red", "blue", "red"}) ++counts[word];
for (const auto& entry : counts) {
std::cout << entry.first << ' ' << entry.second << '\n';
}
assert(counts.find("green") == counts.end());
}Output
blue 1 red 2
Explanation
std::map stores unique keys in comparator order. Access with operator[] inserts a missing key with a value-initialized mapped value, which is zero for int.
Use find for a lookup that should not insert. Iteration is ordered by key, so this sample's output is deterministic without a separate sort.
Explore the dry run
Guided walkthroughReady
1
#include <iostream>2
#include <map>3
#include <string>4
#include <cassert>5
int main() {6
std::map<std::string, int> counts;7
for (const std::string word : {"red", "blue", "red"}) ++counts[word];8
for (const auto& entry : counts) {9
std::cout << entry.first << ' ' << entry.second << '\n';10
}11
assert(counts.find("green") == counts.end());12
}Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Start empty. | counts = {} | — | |
| Insert red at zero and increment, insert blue and increment, then increment red again. | counts = {blue: 1, red: 2} | — | |
| Visit blue before red under the default comparator. | counts = {blue: 1, red: 2} | blue 1 red 2 | |
| Confirm a missing key without inserting it. | counts = {blue: 1, red: 2} | blue 1 red 2 |
Cost and common mistakes
O(log k) map lookup/update comparisons for k keys; O(n log k) counting for bounded-size words; O(k) storage.
- Using counts['missing'] with an appropriate string key changes the map by inserting that key.
- std::unordered_map has different ordering and complexity guarantees.
Try it yourself
Add green once to the input.
Reveal answer and reasoning
Output becomes blue 1, green 1, red 2 in key order.