📘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

map<KeyType, ValueType> mp;

Example:

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

Stored as:

"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

---

🔹 Example

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

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

---

🔹 Iteration

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

---

🔹 Typical LeetCode Use Cases

• Counting frequency

    map<int,int> freq;
    for (int x : nums) freq[x]++;
  

• Checking existence

    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.

---