C++ - Associative Containers (map/unordered_map)

Overview

Estimated time: 50–70 minutes

Work with key-value containers: ordered std::map and hash-based std::unordered_map. Learn lookup, insertion, iteration, and customization points.

Learning Objectives

• Choose between std::map and std::unordered_map based on ordering vs average O(1) lookup.
• Use insert, emplace, operator[], and find safely.
• Define custom comparators (map) and custom hash/equality (unordered_map).

Prerequisites

• C++ - Vectors & Lists (filter, trim)

std::map basics (ordered by key)

#include <map>
#include <iostream>
int main(){
  std::map<std::string, int> ages;
  ages["Ann"] = 30;            // inserts if not present
  ages.insert({"Ben", 25});    // no overwrite if exists
  ages.emplace("Cat", 28);     // constructs in-place
  if (auto it = ages.find("Ben"); it != ages.end()) std::cout << it->second << "\n"; // 25
  for (auto& [name, age] : ages) std::cout << name << ":" << age << "\n";
}

std::unordered_map basics (hash table)

#include <unordered_map>
#include <iostream>
int main(){
  std::unordered_map<std::string,int> counts{{"a",1},{"b",2}};
  counts["a"] += 1;  // 2
  counts["c"];       // inserts with default 0
  std::cout << counts["a"] << "," << counts["c"] << "\n";
}

Expected Output: 2,0

Custom comparator for map

#include <map>
#include <string>
#include <iostream>
struct ByLengthThenLex {
  bool operator()(const std::string& a, const std::string& b) const {
    if (a.size() != b.size()) return a.size() < b.size();
    return a < b;
  }
};
int main(){
  std::map<std::string,int,ByLengthThenLex> m;
  m["pear"]=1; m["fig"]=2; m["plum"]=3;
  for (auto& [k,v] : m) std::cout << k << ' ';
}

Expected Output (example): fig pear plum

Custom hash for unordered_map

#include <unordered_map>
#include <utility>
#include <functional>
#include <iostream>
struct PairHash {
  std::size_t operator()(const std::pair<int,int>& p) const noexcept {
    return std::hash<int>{}(p.first) ^ (std::hash<int>{}(p.second) << 1);
  }
};
int main(){
  std::unordered_map<std::pair<int,int>, int, PairHash> grid;
  grid[{1,2}] = 42;
  std::cout << grid[{1,2}] << "\n";
}

Expected Output: 42

Beginner Boosters

#include <map>
#include <iostream>
int main(){
  std::map<int,int> m;
  for (int i=3;i>=1;--i) m.emplace(i, i*i);
  for (auto& [k,v] : m) std::cout << k << ":" << v << ' ';
}

Expected Output: 1:1 2:4 3:9

Common Pitfalls

• operator[] on unordered_map or map will insert a default value if key absent; use find or at() if you do not want insertion.
• unordered_map does not guarantee iteration order.

Checks for Understanding

1. When would you prefer map over unordered_map?
2. How do you check if a key exists without inserting?

Exercises

1. Count word frequencies in a sentence with unordered_map; print the top 3 by count.
2. Create a map with custom comparator that orders strings case-insensitively.