C++: What is the difference between std::map and std::unordered_map?

map — sorted (red-black tree). unordered_map — hash table.

std::map:

• Sorted by key.
• O(log n) operations.
• Ordered iteration.
• Less memory.

1std::map<int, std::string> m;
2m[3] = "three";
3m[1] = "one";
4// Iterates: 1, 3

std::unordered_map:

• Unsorted (hash table).
• O(1) average.
• Unordered iteration.
• More memory.

1std::unordered_map<int, std::string> um;
2um[3] = "three";
3um[1] = "one";
4// Iterates: 3, 1 (or any order)

When to use:

• map — need sorted order, range queries.
• unordered_map — fast lookup, no order needed.