std::unordered_map vs std::map

std::unordered_map and std::map are both associative containers in C++ that store key-value pairs, but they have some key differences:

Ordering:

• std::unordered_map does not maintain any particular order of elements. The elements are organized into buckets based on their hash values.
• std::map is an ordered associative container. It stores elements in sorted order based on the keys. By default, the keys are sorted in ascending order.

Underlying Data Structure:

• std::unordered_map is implemented using a hash table. It uses a hash function to compute the hash value of the keys and distributes the elements into buckets accordingly.
• std::map is typically implemented as a self-balancing binary search tree, such as a red-black tree. The elements are arranged in a hierarchical structure based on the key values.

Lookup and Insertion Complexity:

• std::unordered_map provides average constant-time O(1) complexity for lookup, insertion, and deletion operations. However, in the worst case (e.g., when all elements have the same hash value), the complexity can degrade to linear time O(n).
• std::map guarantees logarithmic time O(log n) complexity for lookup, insertion, and deletion operations. The self-balancing property of the underlying binary search tree ensures efficient operations.

Key Requirements:

• In std::unordered_map, the key type must have a hash function and an equality comparison operator. The hash function is used to distribute the elements into buckets, and the equality operator is used to resolve collisions.
• In std::map, the key type must have a strict weak ordering (e.g., operator< or a custom comparator). The keys are compared using the operator< or the provided comparator function.

Here's an example to illustrate the differences:

1#include <iostream>
2#include <map>
3#include <unordered_map>
4
5int main() {
6  std::unordered_map<std::string, int> umap = {
7      {"apple", 5}, {"banana", 3}, {"orange", 2}};
8
9  std::map<std::string, int> map = {
10    {"apple", 5}, {"banana", 3}, {"orange", 2}};
11
12  // Iterating over unordered_map
13  // (no specific order)
14  std::cout << "Unordered Map:" << '\n';
15  for (const auto& pair : umap) {
16    std::cout << pair.first << ": "
17      << pair.second << '\n';
18  }
19
20  // Iterating over map (sorted order)
21  std::cout << "\nMap:" << '\n';
22  for (const auto& pair : map) {
23    std::cout << pair.first << ": "
24      << pair.second << '\n';
25  }
26}

1Unordered Map:
2orange: 2
3apple: 5
4banana: 3
5
6Map:
7apple: 5
8banana: 3
9orange: 2

In general, if you need fast lookup, insertion, and deletion operations and don't care about the order of elements, std::unordered_map is a good choice. If you require the elements to be sorted based on keys or need logarithmic time complexity guarantees, std::map is a suitable option.