Каква е разликата между контейнерите map и unordered_map в C++?

Основната разлика е в начина, по който се съхраняват и извличат елементите:

• std::map: Съхранява елементите в сортиран ред по ключ. Обикновено се реализира на базата на червено-черно дърво. Търсенето, вмъкването и изтриването имат логаритмична сложност O(log N), където N е броят на елементите.
• std::unordered_map: Съхранява елементите в хеш таблица. Порядъкът на елементите е произволен. Средната сложност за търсене, вмъкване и изтриване е константна O(1). В най-лошия случай, при колизии, сложността може да достигне O(N).

Характеристика	std::map	std::unordered_map
Подредба	По ключ (нарастваща)	Не
Основна структура	Червено-черно дърво	Хеш таблица
Средна сложност	O(log N)	O(1)
Най-лош случай	O(log N)	O(N)
Изисквания към ключа	Оператор <	Хеш функция и ==

Пример за използване:

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

int main() {
    // std::map: елементите са сортирани по ключ
    std::map<std::string, int> sorted_map;
    sorted_map["banana"] = 3;
    sorted_map["apple"] = 1;
    sorted_map["cherry"] = 2;

    // Изход: apple 1, banana 3, cherry 2 (редът е важен)
    for (const auto& pair : sorted_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

    std::cout << "---" << std::endl;

    // std::unordered_map: редът на елементите не е гарантиран
    std::unordered_map<std::string, int> unordered_map;
    unordered_map["banana"] = 3;
    unordered_map["apple"] = 1;
    unordered_map["cherry"] = 2;

    // Изходът може да варира (например, cherry 2, apple 1, banana 3)
    for (const auto& pair : unordered_map) {
        std::cout << pair.first << " " << pair.second << std::endl;
    }

    return 0;
}