Map vs Unordered Map

std::map and std::unordered_map both store key-value pairs, but they differ in important ways. map uses a balanced tree (usually red-black tree) internally. Operations like insert, find, and erase take $O(\log n)$ time.

Keys stay sorted for iteration. unordered_map uses a hash table. Operations are $O(1)$ average case but $O(n)$ worst case if many keys hash to the same bucket.

Key order is unpredictable.