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

map — sorted tree. unordered_map — hash table.

std::map:

• Red-black tree.
• O(log n).
• Sorted.

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

std::unordered_map:

• Hash table.
• O(1) average.
• Unsorted.

1std::unordered_map<int, std::string> um;
2um[3] = "three";
3um[1] = "one";
4// Unordered: 3, 1

• map — need sorted order.
• unordered_map — need fast lookup.