std::map

std::map

---

Prerequisites

---

1. What is std::map?

std::map is an associative container that stores elements in key-value pairs.

std::map<Key, Value>

• Keys are unique (no duplicates allowed)
• Automatically sorted by key
• Implemented using a Red-Black Tree (self-balancing BST)

std::map is implemented using a Red-Black Tree

Use it when:

• You need sorted data
• You need logarithmic lookup
• You need range queries (lower_bound, upper_bound)

Characteristics:

• Self-balancing
• Guarantees O(log N) operations
• Maintains sorted order

✔️ Declaration

#include <map>

std::map<std::string, int> m;

✔️ Insertion

m["apple"] = 10;
m["banana"] = 20;

m.insert({"orange", 30});

m["new_key"];

If the key does not exist, it will be created automatically with a default value.

✔️ Access

std::cout << m["apple"];  // 10

2. Functions

✔️ find

auto it = m.find("apple");

if (it != m.end())
    std::cout << it->second;

Returns m.end() if not found

erase

m.erase("apple");

size

m.size();

clear

m.clear();

Iteration

for (const auto& pair : m)
    std::cout << pair.first << " : " << pair.second << "\n";

Order

std::map<int, std::string, std::greater<int>> m;

Sorts keys in descending order

Always iterates in sorted order (by key)

Operation	Complexity
Insert	O(log N)
Search	O(log N)
Delete	O(log N)

3. std::map vs std::unordered_map

Feature	map	unordered_map
Structure	Red-Black Tree	Hash Table
Ordering	Sorted	Not sorted
Speed	O(log N)	Avg O(1)
Key Order	Maintained	Not maintained

Use map when ordering matters
Use unordered_map when performance is critical

4. Common Mistakes

❌ Overusing operator[]

if (m["key"] == 0)  // ❌ Dangerous

This creates the key if it doesn’t exist

✔️ Correct way:

if (m.find("key") != m.end())

❌ Unnecessary Copy

for (auto pair : m)  // ❌ Copy occurs

✔️ Better:

for (const auto& pair : m)