C++ ordered maps and frequencies
Count keys and traverse them in sorted order.
On this page
Strings, loops, and key-value pairs.
- Count keys and traverse them in sorted order.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
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.
Code example
#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());
}blue 1 red 2
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
#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());}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 |
Behind the scenes
How C++ processes this code
The C++ compiler produces a native executable. Execution enters main, where objects and function calls perform the work.
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.