Что такое std::unordered_map

1️⃣ Как кратко ответить

std::unordered_map — это контейнер в C++, который хранит пары ключ-значение и обеспечивает быстрый доступ к значениям по ключу. Он реализован на основе хеш-таблицы, что позволяет выполнять операции поиска, вставки и удаления за амортизированное постоянное время O(1).

2️⃣ Подробное объяснение темы

std::unordered_map — это часть стандартной библиотеки C++, представляющая собой ассоциативный контейнер, который хранит элементы в виде пар ключ-значение. В отличие от std::map, который реализован на основе сбалансированного дерева и хранит элементы в отсортированном порядке, std::unordered_map использует хеш-таблицу для хранения элементов, что позволяет обеспечить более быстрый доступ к данным.

Основные характеристики

• Хеш-таблица: std::unordered_map использует хеш-таблицу для хранения данных, что позволяет выполнять операции поиска, вставки и удаления за амортизированное постоянное время O(1). Это делает его особенно эффективным для задач, где требуется частый доступ к элементам по ключу.

• Неупорядоченность: Элементы в std::unordered_map не имеют определенного порядка. Это означает, что порядок, в котором элементы добавляются, не обязательно будет совпадать с порядком их хранения или извлечения.

• Уникальные ключи: Каждый ключ в std::unordered_map должен быть уникальным. Если попытаться вставить элемент с уже существующим ключом, то новый элемент не будет добавлен.

Пример использования

Рассмотрим пример использования std::unordered_map для хранения и доступа к элементам:

#include <iostream>
#include <unordered_map>
#include <string>
​
int main() {
    // Создаем unordered_map для хранения пар ключ-значение
    std::unordered_map<std::string, int> ageMap;
​
    // Вставляем элементы в контейнер
    ageMap["Alice"] = 30; // Добавляем пару "Alice" -> 30
    ageMap["Bob"] = 25;   // Добавляем пару "Bob" -> 25
    ageMap["Charlie"] = 35; // Добавляем пару "Charlie" -> 35
​
    // Доступ к элементам по ключу
    std::cout << "Alice's age: " << ageMap["Alice"] << std::endl; // Выводит: Alice's age: 30
​
    // Проверка наличия ключа
    if (ageMap.find("Bob") != ageMap.end()) {
        std::cout << "Bob is in the map." << std::endl; // Выводит: Bob is in the map.
    }
​
    // Удаление элемента по ключу
    ageMap.erase("Charlie"); // Удаляет элемент с ключом "Charlie"
​
    // Итерация по элементам unordered_map
    for (const auto& pair : ageMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    // Возможный вывод (порядок не гарантируется):
    // Alice: 30
    // Bob: 25
​
    return 0;
}

Объяснение кода

• Создание unordered_map: std::unordered_map<std::string, int> ageMap; — создается контейнер, где ключи — строки, а значения — целые числа.

• Вставка элементов: ageMap["Alice"] = 30; — добавляется пара ключ-значение. Если ключ уже существует, его значение будет обновлено.

• Доступ к элементам: ageMap["Alice"] — позволяет получить значение, связанное с ключом "Alice".

• Проверка наличия ключа: ageMap.find("Bob") != ageMap.end() — проверяет, существует ли ключ "Bob" в контейнере.

• Удаление элемента: ageMap.erase("Charlie"); — удаляет элемент с ключом "Charlie".

• Итерация по элементам: for (const auto& pair : ageMap) — позволяет пройтись по всем элементам контейнера. Порядок элементов не гарантируется.

Применение

std::unordered_map широко используется в случаях, когда требуется быстрый доступ к данным по ключу, например, в кэшах, индексах и других структурах данных, где важна скорость поиска.