C++ map and multimap

In this page:

What is a map?
Accessing and Updating Values
map vs multimap
Iterating over a map
Searching and Erasing

What is a map?

std::map is an associative container that stores key-value pairs in sorted order by key, implemented internally as a balanced binary search tree (typically red-black tree). Keys are unique and lookups, insertions, and deletions run in O(log n) time.

Example: What is a map?

cpp

#include <iostream>
#include <map>
#include <string>

int main() {
	std::map<std::string, int> ages;
	ages["Alex"] = 30;
	std::cout << ages["Alex"] << std::endl;
	return 0;
}

Accessing and Updating Values

You can access values with operator[] (which inserts a default value if the key is missing) or with at() (which throws out_of_range for a missing key). Assigning to an existing key updates its value.

Example: Accessing and Updating Values

cpp

#include <iostream>
#include <map>
#include <string>

int main() {
	std::map<std::string, int> ages;
	ages["Alex"] = 30;
	ages["Alex"] = 31;
	std::cout << ages.at("Alex") << std::endl;
	return 0;
}

map vs multimap

std::map requires unique keys -- inserting a duplicate key overwrites the existing value via operator[]. std::multimap allows multiple entries with the same key, storing them adjacently in sorted order.

Example: map vs multimap

cpp

#include <iostream>
#include <map>

int main() {
	std::map<int, int> m;
	m[1] = 10;
	m[1] = 20;
	std::cout << m[1] << std::endl;
	return 0;
}

Iterating over a map

Iterating a map visits key-value pairs in ascending key order. Each element is a std::pair, accessed via .first (key) and .second (value), or with structured bindings in C++17.

Example: Iterating over a map

cpp

#include <iostream>
#include <map>
#include <string>

int main() {
	std::map<std::string, int> ages = {{"Alex", 30}, {"Sam", 25}};
	for (const auto &[name, age] : ages) {
		std::cout << name << ":" << age << " ";
	}
	std::cout << std::endl;
	return 0;
}

Searching and Erasing

find() returns an iterator to the element or end() if the key is missing. count() returns 1 (map) or the number of matches (multimap). erase() removes an entry by key or iterator.

Example: Searching and Erasing

cpp

#include <iostream>
#include <map>
#include <string>

int main() {
	std::map<std::string, int> ages = {{"Alex", 30}};
	auto it = ages.find("Alex");
	if (it != ages.end()) std::cout << "Found: " << it->second << std::endl;
	ages.erase("Alex");
	std::cout << ages.size() << std::endl;
	return 0;
}

🔒

Chapter Quiz — Complete all 15 topics to unlock

0/15 topics done

Complete these topics first:

← Previous Lesson C++ STL String Next Lesson → C++ unordered_map