Map Structures
Map data structures store key-value pairs and provide efficient lookup, insertion, and deletion operations. They are crucial for solving problems involving frequency counting, lookups, and associations.
What are Maps?
A map is a data structure that stores key-value pairs. Each key is unique and maps to exactly one value. Maps are essential for:
Common Map Use Cases:
- Counting frequency of elements
- Creating lookup tables and dictionaries
- Caching computed results
- Implementing graphs with adjacency lists
STL map
The STL map stores key-value pairs sorted by key using a balanced binary search tree:
#include <map>
#include <iostream>
#include <string>
int main() {
map<string, int> ages;
// Insert key-value pairs
ages["Alice"] = 25;
ages["Bob"] = 30;
ages["Carol"] = 22;
ages.insert({"David", 28});
// Access values
cout << "Alice's age: " << ages["Alice"] << endl;
// Check if key exists
if (ages.find("Bob") != ages.end()) {
cout << "Bob found with age: " << ages["Bob"] << endl;
}
// Alternative existence check
if (ages.count("Eve") == 0) {
cout << "Eve not found" << endl;
}
// Iterate (keys are in sorted order)
for (const auto& pair : ages) {
cout << pair.first << ": " << pair.second << endl;
}
// Output: Alice: 25, Bob: 30, Carol: 22, David: 28
// Remove element
ages.erase("Alice");
return 0;
}
Frequency Counting
One of the most common uses of maps is counting element frequencies:
#include <map>
#include <vector>
#include <string>
// Count character frequencies in a string
map<char, int> countChars(const string& text) {
map<char, int> frequency;
for (char c : text) {
frequency[c]++; // Automatically creates entry if not exists
}
return frequency;
}
// Count word frequencies
map<string, int> countWords(const vector<string>& words) {
map<string, int> frequency;
for (const string& word : words) {
frequency[word]++;
}
return frequency;
}
int main() {
string text = "hello world";
auto charCount = countChars(text);
for (const auto& pair : charCount) {
cout << "'" << pair.first << "': " << pair.second << endl;
}
return 0;
}
STL multimap
Multimap allows multiple values for the same key:
#include <map>
int main() {
multimap<string, int> scores;
// Multiple values for same key
scores.insert({"Alice", 85});
scores.insert({"Alice", 92});
scores.insert({"Alice", 78});
scores.insert({"Bob", 88});
scores.insert({"Bob", 95});
cout << "Alice has " << scores.count("Alice") << " scores" << endl;
// Find all values for a key
auto range = scores.equal_range("Alice");
cout << "Alice's scores: ";
for (auto it = range.first; it != range.second; ++it) {
cout << it->second << " ";
}
cout << endl;
return 0;
}
Unordered Map
For faster average operations, use unordered_map (hash table based):
#include <unordered_map>
#include <string>
int main() {
unordered_map<string, int> phoneBook;
// Insert elements (O(1) average)
phoneBook["John"] = 123456789;
phoneBook["Jane"] = 987654321;
phoneBook["Alice"] = 555123456;
// Fast lookup (O(1) average)
if (phoneBook.find("John") != phoneBook.end()) {
cout << "John's number: " << phoneBook["John"] << endl;
}
// Keys are not sorted (hash table order)
for (const auto& pair : phoneBook) {
cout << pair.first << ": " << pair.second << endl;
}
return 0;
}
Custom Key Types
You can use custom types as keys with appropriate comparison or hash functions:
#include <map>
#include <unordered_map>
struct Point {
int x, y;
// For map (requires comparison)
bool operator<(const Point& other) const {
if (x != other.x) return x < other.x;
return y < other.y;
}
bool operator==(const Point& other) const {
return x == other.x && y == other.y;
}
};
// Hash function for unordered_map
struct PointHash {
size_t operator()(const Point& p) const {
return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
}
};
int main() {
// Using custom type with map
map<Point, string> locations;
locations[{0, 0}] = "Origin";
locations[{1, 1}] = "Point A";
// Using custom type with unordered_map
unordered_map<Point, string, PointHash> fastLocations;
fastLocations[{0, 0}] = "Origin";
fastLocations[{2, 3}] = "Point B";
return 0;
}
Advanced Map Operations
Some useful techniques for working with maps:
#include <map>
#include <algorithm>
int main() {
map<string, int> inventory = {
{"apples", 50},
{"bananas", 30},
{"oranges", 25},
{"grapes", 40}
};
// Find item with minimum value
auto minItem = min_element(inventory.begin(), inventory.end(),
[](const auto& a, const auto& b) {
return a.second < b.second;
});
cout << "Least stock: " << minItem->first << " ("
<< minItem->second << ")" << endl;
// Update all values
for (auto& pair : inventory) {
pair.second += 10; // Restock everything by 10
}
// Conditional update
for (auto& [item, quantity] : inventory) { // C++17 structured binding
if (quantity < 35) {
quantity = 50; // Restock low items
}
}
return 0;
}
Performance Comparison
Time Complexities:
- map/multimap: O(log n) for insert, find, erase
- unordered_map: O(1) average, O(n) worst case
- When to use map: Need sorted keys, stable performance
- When to use unordered_map: Don't need order, want faster operations
Practical Examples
Two Sum Problem
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> seen;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (seen.find(complement) != seen.end()) {
return {seen[complement], i};
}
seen[nums[i]] = i;
}
return {}; // No solution found
}
Group Anagrams
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> groups;
for (string& s : strs) {
string key = s;
sort(key.begin(), key.end());
groups[key].push_back(s);
}
vector<vector<string>> result;
for (auto& [key, group] : groups) {
result.push_back(group);
}
return result;
}
Common Pitfalls
Watch Out For
- Default initialization: map[key] creates entry with default value if key doesn't exist
- Use find() vs []: find() doesn't create entries, [] does
- Iterator invalidation: Modifying map while iterating can be dangerous
- Hash collisions: unordered_map can degrade to O(n) performance