Can you explain the differences between std::map and std::unordered_map containers, and in which situations it is preferable to use each of them?

std::map and std::unordered_map are containers from the C++ standard library that store key-value pairs but are implemented differently and have different characteristics.

• std::map is implemented as a balanced binary tree (usually a red-black tree). Keys are ordered in ascending order (or according to a specified comparator). Insertion, search, and deletion have logarithmic complexity O(log n).

• std::unordered_map is implemented based on a hash table. Keys are unordered, and insertion, search, and deletion operations have an average amortized complexity of O(1), but in the worst case, they can be O(n).

When to use:

• If the order of elements is important (for example, iterating over keys in sorted order), choose std::map.
• If order is not important and high-speed access by key is needed, std::unordered_map is better.

Example:

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

int main() {
    std::map<int, std::string> ordered_map;
    ordered_map[2] = "two";
    ordered_map[1] = "one";

    for (const auto& [key, value] : ordered_map) {
        std::cout << key << ": " << value << "\n"; // Will output 1: one, then 2: two
    }

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

    for (const auto& [key, value] : unordered_map) {
        std::cout << key << ": " << value << "\n"; // Order is not guaranteed
    }
}