std::map and std::unordered_map

A map stores values under keys and answers "what is the value for this key?" without a search loop. std::map keeps the keys sorted, so iteration is in key order; std::unordered_map hashes them, so lookup is constant time and iteration order is unspecified.

The interface is the same for both: insert, find, count, erase and operator[]. The differences are the order, the complexity and the requirements on the key type, and this lesson shows them side by side on the same data.

The key type needs operator< for a map and a hash for an unordered_map, and both containers own their keys: copying the map copies every entry, which is the rule of zero of lesson 033 at work.

An unordered_map keeps a bucket array and chains the entries that hash to the same bucket; a key type with a poor hash degrades every lookup to a linear scan, which is why the standard library asks for std::hash rather than only for a comparison.

A sorted map

std::map<std::string, int> stores ints under string keys and keeps them in the order of <. insert returns a pair of an iterator and a bool, and the bool says whether the key was new.

The program inserts three entries, looks one up with find and iterates the map. The iteration is in alphabetical order, which is the property std::map guarantees.

find returns end() when the key is absent and an iterator to the pair otherwise. The pair's first member is the key and second is the value, and a structured binding from lesson 021 unpacks them.

#include <iostream> #include <map> #include <string> int main() { std::map<std::string, int> ages; ages.insert({"ada", 36}); ages.insert({"bob", 41}); ages.insert({"cyd", 29}); auto it = ages.find("bob"); if (it != ages.end()) { std::cout << it->first << " is " << it->second << '\n'; } for (const auto& [name, age] : ages) { std::cout << name << ':' << age << ' '; } std::cout << '\n'; }

g++ -std=c++23 -Wall -Wextra map.cpp -o map_demo
./map_demo

bob is 41
ada:36 bob:41 cyd:29

operator[] inserts

operator[] returns a reference to the value for a key, and if the key is absent it inserts a default-constructed value first. Reading a missing key therefore changes the map.

The program reads "zed" with operator[] and prints the size before and after. The value is 0, the default for int, and the map grew by one entry, which is the surprise this operator holds.

Use at() or find() when the key may be missing and the map must not change; use operator[] when the code is really building the entry. The counting idiom of the fourth section relies on the insert.

#include <iostream> #include <map> #include <string> int main() { std::map<std::string, int> ages{{"ada", 36}}; std::cout << ages.size() << ' '; std::cout << ages["zed"] << ' '; std::cout << ages.size() << '\n'; }

g++ -std=c++23 -Wall -Wextra bracket.cpp -o bracket
./bracket

1 0 2

An unordered map

std::unordered_map has the same interface and a different order. Lookup is average constant time, the keys are not sorted, and the iteration order depends on the hash function and the bucket count.

The program inserts the same three entries and iterates them. The order is not alphabetical, and it is not something a program should depend on: the output of this page is one implementation's order.

Hashing costs a function call per lookup and needs a hash for the key type; std::string and the arithmetic types have one. A custom key type needs std::hash specialised or a hasher passed as a template argument.

#include <iostream> #include <string> #include <unordered_map> int main() { std::unordered_map<std::string, int> ages; ages.insert({"ada", 36}); ages.insert({"bob", 41}); ages.insert({"cyd", 29}); for (const auto& [name, age] : ages) { std::cout << name << ':' << age << ' '; } std::cout << '\n'; std::cout << ages.count("bob") << '\n'; }

g++ -std=c++23 -Wall -Wextra unordered.cpp -o unordered_demo
./unordered_demo

cyd:29 bob:41 ada:36
1

Counting words

The counting idiom is ++counts[word]: operator[] inserts a zero for a new word and the increment makes it one, or increments the existing count. It is the shortest correct use of the operator.

The program splits a sentence into words and counts them. The result is printed in alphabetical order because std::map sorts the keys, and the two repeated words show as 2.

Splitting on spaces is enough here; lesson 065 shows the stream version and lesson 070 the one that reads a file.

#include <iostream> #include <map> #include <sstream> #include <string> int main() { std::istringstream input{"the cat and the dog"}; std::map<std::string, int> counts; std::string word; while (input >> word) { ++counts[word]; } for (const auto& [text, count] : counts) { std::cout << text << ':' << count << ' '; } std::cout << '\n'; }

g++ -std=c++23 -Wall -Wextra count.cpp -o count_words
./count_words

and:1 cat:1 dog:1 the:2

operator[] on a const map

operator[] may insert, so it cannot be const. A const map, or a map passed by const reference, has no operator[] and the compiler says the object discards its const qualifier.

The program looks a value up in a const map with operator[]. The message names the function and the const object, and the fix is find() or at(), both of which have const overloads.

This is the const correctness of lesson 029 at work: the non-const operator[] is a modifying function, and a read-only view of the map cannot call it.

#include <map> #include <string> int main() { const std::map<std::string, int> ages{{"ada", 36}}; return ages["ada"]; }

g++ -std=c++23 -Wall -Wextra const_map.cpp -o const_map

const_map.cpp: In function 'int main()':
const_map.cpp:7:22: error: passing 'const std::map<std::__cxx11::basic_string<char>, int>' as 'this' argument discards qualifiers [-fpermissive]
7 | return ages["ada"];
| ^
In file included from /usr/include/c++/15.2.0/map:65,
from const_map.cpp:1:
/usr/include/c++/15.2.0/bits/stl_map.h:547:7: note: in call to 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](key_type&&) [with _Key = std::__cxx11::basic_string<char>; _Tp = int; _Compare = std::less<std::__cxx11::basic_string<char> >; _Alloc = std::allocator<std::pair<const std::__cxx11::basic_string<char>, int> >; mapped_type = int; key_type = std::__cxx11::basic_string<char>]'
547 | operator[](key_type&& __k)
| ^~~~~~~~

Exercises

  1. Insert the same key twice into a std::map and check the size. Which insert won?
  2. Count how many distinct words a sentence has and print the most frequent one.
  3. Change the word counter to std::unordered_map and compare the output order with the sorted version.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What order does std::map keep?

    Answer

    Sorted by key

    The map is a balanced tree ordered by the key comparator.

  2. What does map[key] do when the key is absent?

    Answer

    It inserts the key with a default value

    The operator is an insert-or-find, which is why it needs a non-const map.

  3. Why does operator[] not work on a const map?

    Answer

    It may insert, so it needs a non-const map

    The lookup that may insert cannot be part of a const interface; at is the const version.

  4. What does count(key) return for a map?

    Answer

    0 or 1

    A map has one value per key, so the count is a membership test.

  5. What does this program print? #include <iostream> #include <map> #include <string> int main() { std::map<std::string, int> ages{{"bob", 41}, {"ada", 36}}; std::cout << "bob is " << ages["bob"] << '\n'; for (const auto& [name, age] : ages) std::cout << name << ':' << age << ' '; }

    Answer

    bob is 41 / ada:36 bob:41

    The lookup returns 41, and the iteration follows the key order.

  6. What does this program print? #include <iostream> #include <map> int main() { std::map<int, int> values{{1, 10}}; std::cout << values.size() << ' '; values[2]; std::cout << values.size() << ' '; values[1] = 20; std::cout << values.size(); }

    Answer

    1 2 2

    The second lookup inserts the default zero, and assigning to an existing key does not change the size.

  7. What does this program print? #include <iostream> #include <string> #include <unordered_map> int main() { std::unordered_map<std::string, int> ages{{"ada", 36}, {"bob", 41}}; std::cout << ages.size() << ' ' << (ages.find("ada") != ages.end()) << ' ' << ages.at("bob"); }

    Answer

    2 1 41

    Both keys are stored, the find succeeds, and the value under bob is 41.

  8. What does this program print? #include <iostream> #include <map> #include <string> int main() { std::map<std::string, int> counts; for (const std::string& word : {"the", "cat", "the", "dog"}) ++counts[word]; for (const auto& [word, n] : counts) std::cout << word << ':' << n << ' '; }

    Answer

    cat:1 dog:1 the:2

    The lookup inserts on the first sighting and increments on the second, and the map prints in key order.

  9. What does the compiler say about this line? #include <map> int lookup(const std::map<int, int>& values) { return values[1]; }

    Answer

    passing 'const std::map<int, int>' as 'this' argument discards qualifiers

    operator[] may insert, so the const overload does not exist; at() is the const read.

  10. When is unordered_map the better choice?

    Answer

    When only lookup matters and key order does not

    The hash map gives average constant-time lookup and gives up the order.

The code on this page was built with g++ 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container. The programs whose section shows a compiler error were compiled until that error and were not run.

Article author: Arthur Isaev