# 📘map in C++

---

## 🔹 What is `map`?

* A **container** in C++ (from STL) that stores **key → value** pairs.
    
* Each **key is unique**.
    
* Keys are stored in **sorted order** (ascending by default).
    
* Internally implemented as a **balanced binary search tree (Red-Black Tree)**.
    

👉 Think of it as a **dictionary**: word (key) → meaning (value).

---

## 🔹 Syntax

```cpp
map<KeyType, ValueType> mp;
```

Example:

```cpp
map<string, int> age;
age["Alice"] = 20;
age["Bob"] = 25;
```

Stored as:

```plaintext
"Alice" → 20
"Bob"   → 25
```

---

## 🔹 Key vs Value

* **Key** = used for searching/ordering.
    
* **Value** = information linked to that key.
    
* In `map<string,int>`,
    
    * `string` = key,
        
    * `int` = value.
        

---

## 🔹 Common Operations & Complexity

| Operation | Code Example | Time Complexity |
| --- | --- | --- |
| Insert | `mp[key] = value;` or `mp.insert({key,value});` | O(log n) |
| Access (by key) | `mp[key]` | O(log n) |
| Search | `mp.find(key)` | O(log n) |
| Erase | `mp.erase(key)` | O(log n) |
| Size | `mp.size()` | O(1) |
| Iterate | `for (auto &p: mp) ...` | O(n) |

---

## 🔹 Example

```cpp
map<int, string> mp;
mp[30] = "X";
mp[10] = "Y";
mp[20] = "Z";

// Stored as sorted by key:
10 → "Y"
20 → "Z"
30 → "X"
```

---

## 🔹 Checking Existence

```cpp
if (mp.find(20) != mp.end()) {
    cout << "Key 20 found, value = " << mp[20];
}
else {
    cout << "Key 20 not found";
}
```

---

## 🔹 Iteration

```cpp
for (auto it = mp.begin(); it != mp.end(); it++) {
    cout << it->first << " → " << it->second << endl;
}
// or
for (auto &p : mp) {
    cout << p.first << " → " << p.second << endl;
}
```

---

## 🔹 Characteristics

1. **Sorted order**
    
    * Integers sorted numerically.
        
    * Strings sorted lexicographically.
        
    * Custom keys sorted using comparator.
        
2. **Unique keys only**
    
    * If you insert the same key again, it updates the value.
        
3. **Underlying data structure**
    
    * Red-Black Tree (balanced BST).
        
    * This is why all operations are O(log n).
        

---

## 🔹 Advantages (Pros)

✅ Keeps keys **sorted automatically**  
✅ Fast lookup, insert, erase → **O(log n)**  
✅ Works with any data type as key (numbers, strings, pairs, custom structs with comparator)

---

## 🔹 Disadvantages (Cons)

❌ Slower than `unordered_map` (O(1) average)  
❌ More memory overhead (tree structure)  
❌ If you don’t need sorting, it’s wasteful

---

## 🔹 `map` vs `unordered_map`

| Feature | `map` | `unordered_map` |
| --- | --- | --- |
| Order of keys | Sorted | No order |
| Complexity | O(log n) | O(1) avg, O(n) worst |
| Use case | Need order / ranges | Just fast lookups |
| Internal structure | Red-Black Tree | Hash Table |

---

## 🔹 Typical LeetCode Use Cases

* **Counting frequency**
    
    ```cpp
    map<int,int> freq;
    for (int x : nums) freq[x]++;
    ```
    
* **Checking existence**
    
    ```cpp
    if (mp.find(target) != mp.end()) ...
    ```
    
* **Two Sum problem** (using number → index mapping).
    
* **Tracking smallest/largest key** (since ordered).
    

---

## ✅ Summary

* `map` = ordered key-value container (Red-Black Tree).
    
* Operations = O(log n).
    
* Keys always sorted.
    
* Use when order matters or you need range queries.
    
* Prefer `unordered_map` for faster average lookups when order doesn’t matter.
    

---