What is the difference between map and unordered_map…

std::map is an associative container that stores elements as key-value pairs, sorted by keys. It is based on a balanced binary search tree (usually a red-black tree).

std::unordered_map is also an associative container that stores key-value pairs but without a specific order. It is based on a hash table.

Main differences:

Order of elements:
- std::map: Elements are sorted by keys.
- std::unordered_map: Elements are not sorted; order depends on the hash function and the state of the hash table.
Performance:
- std::map:
  - Search, insert, and delete: average O(log N), where N is the number of elements.
  - Access time does not depend on content.
- std::unordered_map:
  - Search, insert, and delete: average O(1).
  - In the worst case (with collisions) O(N). Access time depends on the quality of the hash function and load factor.
Memory usage:
- std::map: Requires slightly more memory to store tree nodes.
- std::unordered_map: May require more memory at low load factors (to reduce collisions). Depends on implementation.
Key requirements:
- std::map: Keys must support comparison (operator<).
- std::unordered_map: Keys must support:
  - Equality (operator==).
  - Hashing (specialization of std::hash or providing a hash function).
Iterators:
- std::map: Bidirectional iterators, traverse elements in sorted order.
- std::unordered_map: Forward iterators, traverse elements in arbitrary order (dependent on hash table structure).

Characteristic	`std::map`	`std::unordered_map`
Internal structure	Balanced tree	Hash table
Order of elements	Sorted by key	Unsorted
Average performance	O(log N)	O(1)
Worst-case performance	O(log N)	O(N) (with collisions)
Key requirements	Comparison (`<`)	Equality (`==`), hashing
Iterators	Bidirectional, ordered	Forward, unordered

Example usage:

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

// std::map
std::map<int, std::string> sorted_map;
sorted_map[3] = "three";
sorted_map[1] = "one";
sorted_map[2] = "two";

// Iterating over map will output elements in sorted order of keys (1, 2, 3)
for (const auto& pair : sorted_map) {
    // std::cout << pair.first << ": " << pair.second << std::endl;
}

// std::unordered_map
std::unordered_map<int, std::string> unsorted_map;
unsorted_map[3] = "three";
unsorted_map[1] = "one";
unsorted_map[2] = "two";

// Iterating over unordered_map will output elements in arbitrary order
for (const auto& pair : unsorted_map) {
    // std::cout << pair.first << ": " << pair.second << std::endl;
}

The choice between std::map and std::unordered_map depends on the required functionality: if a sorted order of elements is important or keys cannot be hashed/effectively compared for equality, std::map is used. If maximum performance for search/insert/delete is needed and element order does not matter, std::unordered_map is preferable (assuming a good hash function).

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