Словари и хеш-таблицы в C++17: подробное руководство

Словари и хеш-таблицы в C++

Что это и зачем?

Представь, что у тебя есть волшебная записная книжка. В ней ты можешь записать имя друга и рядом его номер телефона. А потом, когда захочешь позвонить, ты просто смотришь на имя и сразу видишь номер! Тебе не нужно листать все страницы и искать номер, а потом вспоминать, чей он. Имя — это ключ, а номер — это значение.

В программировании такая «записная книжка» называется словарь (или ассоциативный массив). В C++ для этого используется контейнер std::map (он же «отображение») или std::unordered_map (неупорядоченное отображение, работает быстрее, но не хранит порядок).

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

Основной синтаксис

Чтобы использовать словарь, нужно подключить библиотеку <unordered_map> (или <map>).

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

int main() {
    // Объявляем словарь: ключ - строка (string), значение - строка (string)
    std::unordered_map<std::string, std::string> phonebook;

    // Добавляем записи
    phonebook["Анна"] = "+7-999-123-45-67";
    phonebook["Борис"] = "+7-888-765-43-21";
    phonebook["Вика"] = "+7-777-555-33-11";

    // Получаем значение по ключу
    std::cout << "Номер Анны: " << phonebook["Анна"] << std::endl;

    // Проверяем, есть ли ключ в словаре
    if (phonebook.find("Борис") != phonebook.end()) {
        std::cout << "Борис есть в справочнике!" << std::endl;
    }

    // Удаляем запись
    phonebook.erase("Вика");

    // Выводим все записи (перебираем словарь)
    for (auto& pair : phonebook) {
        // pair.first - это ключ (имя)
        // pair.second - это значение (номер)
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

Разбор типичных задач

Задача 1. Приветствие на разных языках

У нас есть словарь: страна → приветствие. Пользователь вводит страну, программа выводит приветствие.

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

int main() {
    std::unordered_map<std::string, std::string> greetings;
    greetings["Россия"] = "Здравствуйте!";
    greetings["Англия"] = "Hello!";
    greetings["Франция"] = "Bonjour!";
    greetings["Италия"] = "Ciao!";

    std::string country;
    std::cout << "Введите страну: ";
    std::getline(std::cin, country);

    // Ищем страну в словаре
    if (greetings.find(country) != greetings.end()) {
        std::cout << "Приветствие: " << greetings[country] << std::endl;
    } else {
        std::cout << "Приветствие для этой страны не найдено." << std::endl;
    }

    return 0;
}

Задача 2. Телефонный справочник (поиск)

Справочник уже есть. Нужно найти номер по имени.

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

int main() {
    std::unordered_map<std::string, std::string> phonebook;
    phonebook["Иван"] = "111-22-33";
    phonebook["Мария"] = "444-55-66";
    phonebook["Петр"] = "777-88-99";

    std::string name;
    std::cout << "Введите имя для поиска: ";
    std::getline(std::cin, name);

    if (phonebook.find(name) != phonebook.end()) {
        std::cout << "Номер телефона: " << phonebook[name] << std::endl;
    } else {
        std::cout << "Контакт не найден." << std::endl;
    }

    return 0;
}

Задача 3. Книжная карточка (список дел на неделю)

Ключ — день недели, значение — список дел (строка).

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

int main() {
    std::unordered_map<std::string, std::string> weekPlan;

    weekPlan["Понедельник"] = "Пойти в школу, сделать уроки";
    weekPlan["Вторник"] = "Тренировка по футболу";
    weekPlan["Среда"] = "Убраться в комнате";
    weekPlan["Четверг"] = "Помочь маме с ужином";
    weekPlan["Пятница"] = "Встретиться с друзьями";

    std::string day;
    std::cout << "Введите день недели: ";
    std::getline(std::cin, day);

    if (weekPlan.find(day) != weekPlan.end()) {
        std::cout << "Планы на " << day << ": " << weekPlan[day] << std::endl;
    } else {
        std::cout << "На этот день планов нет." << std::endl;
    }

    return 0;
}

Задача 4. Цифровой блокнот (удаление контакта)

Удаляем контакт, который больше не нужен.

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

int main() {
    std::unordered_map<std::string, std::string> contacts;
    contacts["Алиса"] = "123-45-67";
    contacts["Боб"] = "234-56-78";
    contacts["Чарли"] = "345-67-89";

    std::string name;
    std::cout << "Введите имя контакта для удаления: ";
    std::getline(std::cin, name);

    if (contacts.find(name) != contacts.end()) {
        contacts.erase(name);
        std::cout << "Контакт \"" << name << "\" удален." << std::endl;
    } else {
        std::cout << "Контакт не найден." << std::endl;
    }

    // Выводим оставшиеся контакты
    std::cout << "Оставшиеся контакты:" << std::endl;
    for (auto& pair : contacts) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

Задача 5. Ключи словаря (список товаров)

Выводим все названия товаров (ключи) из словаря.

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

int main() {
    std::unordered_map<std::string, double> products;
    products["Хлеб"] = 45.50;
    products["Молоко"] = 89.90;
    products["Яблоки"] = 120.00;
    products["Сыр"] = 250.00;

    std::cout << "Список доступных товаров:" << std::endl;
    for (auto& pair : products) {
        // Выводим только ключ (название товара)
        std::cout << pair.first << std::endl;
    }

    return 0;
}

Частые ошибки новичков

• Ошибка 1: Обращение к несуществующему ключу через квадратные скобки.
  Если написать phonebook["Вася"], а ключа "Вася" нет, то C++ создаст этот ключ с пустым значением. Это может испортить данные. Всегда используй find() для проверки.
• Ошибка 2: Забыли проверить, что ключ существует.
  Если использовать phonebook.at("Вася"), а ключа нет, программа вылетит с ошибкой. Используй find() перед тем, как брать значение.
• Ошибка 3: Путаница между ключом и значением.
  В цикле for (auto& pair : dict) — pair.first это всегда ключ, pair.second это всегда значение.
• Ошибка 4: Неправильный тип данных.
  Если ключи — строки, то тип должен быть std::string, а не int. Если значения — числа, то int или double.

Итоговый пример: Сборник рецептов

Представь, что ты собираешь рецепты. Ключ — название блюда, значение — список ингредиентов. Пользователь может добавить рецепт, найти его или удалить.

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

int main() {
    std::unordered_map<std::string, std::string> recipes;

    // Добавляем несколько рецептов
    recipes["Омлет"] = "Яйца, молоко, соль, масло";
    recipes["Салат"] = "Помидоры, огурцы, сметана, зелень";

    int choice;
    std::string name, ingredients;

    do {
        std::cout << "\n--- Меню ---" << std::endl;
        std::cout << "1. Добавить рецепт" << std::endl;
        std::cout << "2. Найти рецепт" << std::endl;
        std::cout << "3. Удалить рецепт" << std::endl;
        std::cout << "4. Показать все рецепты" << std::endl;
        std::cout << "0. Выход" << std::endl;
        std::cout << "Ваш выбор: ";
        std::cin >> choice;
        std::cin.ignore(); // очищаем буфер ввода

        if (choice == 1) {
            std::cout << "Название блюда: ";
            std::getline(std::cin, name);
            std::cout << "Ингредиенты: ";
            std::getline(std::cin, ingredients);
            recipes[name] = ingredients;
            std::cout << "Рецепт добавлен!" << std::endl;
        }
        else if (choice == 2) {
            std::cout << "Название блюда: ";
            std::getline(std::cin, name);
            if (recipes.find(name) != recipes.end()) {
                std::cout << "Ингредиенты: " << recipes[name] << std::endl;
            } else {
                std::cout << "Рецепт не найден." << std::endl;
            }
        }
        else if (choice == 3) {
            std::cout << "Название блюда: ";
            std::getline(std::cin, name);
            if (recipes.find(name) != recipes.end()) {
                recipes.erase(name);
                std::cout << "Рецепт удален." << std::endl;
            } else {
                std::cout << "Рецепт не найден." << std::endl;
            }
        }
        else if (choice == 4) {
            std::cout << "Все рецепты:" << std::endl;
            for (auto& pair : recipes) {
                std::cout << pair.first << ": " << pair.second << std::endl;
            }
        }
    } while (choice != 0);

    std::cout << "До свидания!" << std::endl;
    return 0;
}

Запомни: Словари — это как волшебные книжки, где ты по одному слову (ключу) можешь мгновенно найти то, что нужно (значение). Они очень помогают, когда нужно хранить пары «что-то → что-то другое»!