Looking Things Up by Key
A vector is great when you index by position - element 0, element 1, and so on. But often you don't have a position; you have a name and you want the thing attached to it: a username and their score, a word and its count, a country code and its capital. Scanning a vector to find a match is O(n) and gets slow fast.
std::map solves this. It stores key-value pairs, keeps them sorted by key, and lets you look up a value by its key in O(log n) time. Include <map> to use it:
map<string, int> reads as "a map from string keys to int values." Keys are unique - assign to the same key twice and the second value wins. Internally a map is a balanced binary search tree, which is why everything stays sorted and lookups are logarithmic rather than constant.
Inserting Elements
There are a few ways to put entries in, and the difference between them matters. The most common is operator[], which creates the key if it doesn't exist and returns a reference you can assign to:
If you want insertion that refuses to overwrite an existing key, use insert or emplace. Both return a pair whose .second is a bool telling you whether the insert actually happened:
Use [] when "last write wins" is what you want, and insert/emplace when an existing key should be left alone.
The operator[] Gotcha: It Inserts on Read
This is the single most common map bug. operator[] is not a pure read - if the key is missing, it silently inserts it with a default-constructed value (0 for int, "" for string, etc.) and returns a reference to that. So merely checking a key with [] mutates the map:
map<string, int> m;
if (m["maybe"] == 0) { // BUG: this just created "maybe" -> 0
// ...
}
cout << m.size(); // 1, not 0 - you inserted a key by accident
This also bites you with a const map, where operator[] won't even compile because it might need to insert. To read without inserting, use find, count/contains, or at (which throws an exception instead of inserting when the key is absent):
Rule of thumb: if you mean to read, never reach for []. Use at when the key must exist, and find/contains when it might not.
Iterating in Sorted Order
Because a map is tree-backed, iterating it visits keys in ascending sorted order - always, for free. Each element is a pair<const Key, Value>, so use a structured binding to unpack the key and value cleanly:
Notice the key in the binding is const - you can change a value through the loop with auto&, but you can never change a key in place (that would break the sort order). The output comes out alphabetically (blue, sea, sky) without any sorting step, which is exactly why people pick map over a hash table when ordered traversal matters.
That wordCount[w]++ idiom is also the canonical use of the insert-on-access behavior: here you want a missing key to start at 0, so [] is the right tool.
Removing Elements and Sizing
Delete by key with erase, which returns how many elements were removed (0 or 1 for a map). You can also erase via an iterator from find. Check the container's state with size() and empty():
One gotcha when erasing inside a loop: m.erase(it) invalidates the iterator it, so you can't ++it afterward. The safe pattern since C++11 is it = m.erase(it), which returns an iterator to the next element. For a one-shot conditional removal across the whole map, std::erase_if(m, predicate) (C++20) is cleaner.
Next: unordered_map
std::map gives you sorted keys and predictable O(log n) operations, but you pay for that ordering with every lookup. When you don't care about key order and just want the fastest possible lookups, unordered_map trades the sorted tree for a hash table - average O(1) access. Next we'll see how it works, when its constant-time average beats map's logarithm, and the hashing pitfalls (custom key types, worst-case collisions) that come with it.
Frequently Asked Questions
What is a std::map in C++?
A std::map is an associative container that stores key-value pairs sorted by key. Lookups, insertions, and deletions are all O(log n) because it is backed by a balanced binary search tree. Each key is unique - inserting a duplicate key does nothing to the existing value.
What is the difference between map operator[] and at() in C++?
map[key] returns a reference to the value, and if the key is missing it silently inserts it with a default-constructed value. map.at(key) returns a reference too but throws std::out_of_range if the key is absent instead of inserting. Use at() (or find()) when you only mean to read.
How do I check if a key exists in a C++ map?
Use m.contains(key) (C++20), m.count(key) which returns 0 or 1, or m.find(key) != m.end(). Avoid testing with m[key] - that inserts the key if it is missing, which is rarely what you want.
