std::map is an associative container that stores elements as key-value pairs in a sorted order (typically implemented using a self-balancing binary search tree like a Red-Black Tree).

Use std::map when you need to store data associated with a unique key and require the keys to be always sorted.

• Insertion: $O(\log N)$
• Search: $O(\log N)$
• Deletion: $O(\log N)$

cpp Standard
#include <map>
#include <string>

std::map<int, std::string> m;
m[1] = "Apple";
m[2] = "Banana";

if (m.find(1) != m.end()) {
    std::cout << "Key 1 found!";
}

• Using m[key] to check for existence—this actually inserts the key with a default value if it doesn't exist. Use m.find() or m.count() instead.
• Forgetting that keys are kept in sorted order, which adds overhead compared to unordered_map.
• Not realizing that keys must have a defined comparison operator override if using custom types.