Home / C++ / Maps, sets, and unordered containers

C++ PROGRAMMING · 13 MIN STUDY

Maps, sets, and unordered containers

Choose associative containers for ordered lookup or hash-based lookup with map, set, and unordered_map.

Learning objectives

  • Choose a map for key-value data and a set for unique values.
  • Distinguish ordered and unordered associative containers.
  • Use find and insert safely.
  • Compare typical lookup complexity.

Prerequisites: vectors, loops, key/value pairs, and basic Big-O notation. This lesson introduces ordered and unordered associative containers before the deeper container-selection comparison.

Associative containers

Sequence containers such as vector store elements in a sequence. Associative containers organize data around keys. A set stores unique keys; a map stores unique keys associated with values.

std::map: ordered key-value data

C++17
#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> scores;
    scores["Asha"] = 92;
    scores["Ravi"] = 85;
    auto found = scores.find("Asha");
    if (found != scores.end()) {
        std::cout << found->second << '\n';
    }
}

map stores key-value pairs ordered by key. Its lookup, insertion, and removal operations are logarithmic in the number of elements for the usual balanced-tree implementation required by the standard's complexity guarantees.

std::set: unique ordered values

std::set<int> ids{4, 2, 4, 7};
// contains the unique values 2, 4, 7

A set stores each key at most once and keeps keys ordered. It is useful when membership and uniqueness matter more than insertion order.

Unordered containers

std::unordered_map and std::unordered_set use hashing. They do not keep elements sorted. Lookup and insertion are average constant time, but can be linear in the worst case. Use them when ordering is not needed and hash-based lookup suits the key type.

Do not accidentally insert while reading

For map, scores[key] inserts a new key with a default-initialized mapped value if the key is absent. Use find or contains (C++20) when you only want to check whether a key exists.

Common mistakes

  • Assuming unordered_map iteration is sorted.
  • Using operator[] when you only wanted to inspect an existing key.
  • Expecting duplicate keys in map or set.
  • Using a custom key type without providing a valid ordering or hash/equality rule.

Practice

  1. Count word frequencies with unordered_map.
  2. Store unique student IDs in a set.
  3. Print the entries of a map and observe key order.
  4. Replace operator[] lookup with find and explain the difference.

Practice solutions

Show worked solutions
  1. Use std::unordered_map<std::string, int> frequency; and increment frequency[word] for each word. This inserts a new key with a value-initialized count when the word is first seen.
  2. Insert each ID into std::set<int>. Duplicate values are ignored and iteration visits the IDs in sorted order.
  3. Iterate with for (const auto& [key, value] : scores) in C++17. A std::map visits keys in ascending key order according to its comparator.
  4. Use auto it = scores.find(key); and compare it with scores.end(). Unlike operator[], find does not insert a missing key.

Check your understanding

Which container should you choose when you need unique values in sorted order?

Answer: std::set.

Summary

Use map for ordered key-value pairs, set for unique ordered keys, and unordered variants for hash-based lookup when ordering is not required. Understand average versus worst-case complexity.

References