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

std::map:

• Stores elements in sorted order by keys.
• Implemented based on a red-black tree.
• Average access, insertion, and deletion time is logarithmic: O(log n).
• Keys must have the < operator.
• Suitable when ordered traversal of elements or frequent range search operations are important.

std::unordered_map:

• Does not store elements in any specific order.
• Implemented based on a hash table.
• Average access, insertion, and deletion time is O(1). In the worst case (with poor hashing and many collisions): O(n).
• Keys must be hashable (provide a hash function) and have the == operator.
• Suitable when the main priority is fast lookup of elements by key and order is not important.

Comparison table:

Attribute	std::map	std::unordered_map
Order	Sorted	Unordered
Data structure	Red-black tree	Hash table
Average complexity	O(log n)	O(1)
Key requirements	< operator	Hashable, ==
Usage	Ordered access, ranges	Fast key lookup

Example of using std::map:

#include <map>
#include <string>
#include <iostream>

// Example of using std::map
std::map<int, std::string> my_map;
my_map[5] = "five";
my_map[2] = "two";
my_map[8] = "eight";

// Elements will be output in sorted order by key
for (const auto& pair : my_map) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

Example of using std::unordered_map:

#include <unordered_map>
#include <string>
#include <iostream>

// Example of using std::unordered_map
std::unordered_map<int, std::string> my_unordered_map;
my_unordered_map[5] = "five";
my_unordered_map[2] = "two";
my_unordered_map[8] = "eight";

// The order of output is not guaranteed
for (const auto& pair : my_unordered_map) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}