Что хотят услышать интервьюеры:

std::map — это ассоциативный контейнер, который хранит пары ключ–значение и автоматически упорядочивает элементы по ключу. Внутри это обычно сбалансированное дерево, поэтому основные операции выполняются за логарифмическое время. Важно понимать, что ключи уникальны, а итерация идёт в отсортированном порядке.

Определение:

std::map — стандартный контейнер C++, предназначенный для хранения отображения key -> value. Элементы в нём отсортированы по ключу согласно сравнению, заданному компаратором. Ключи в std::map уникальны, а доступ к элементу по ключу, вставка и удаление обычно имеют сложность O(log n).

Чаще всего std::map реализован как сбалансированное дерево поиска, например красно-чёрное дерево. Это обеспечивает предсказуемую производительность и упорядоченный обход.

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

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

int main() {
    std::map<std::string, int> ages;

    ages["Alice"] = 30;
    ages["Bob"] = 25;
    ages["Charlie"] = 35;

    for (const auto& [name, age] : ages) {
        std::cout << name << " -> " << age << '\n';
    }

    auto it = ages.find("Bob");
    if (it != ages.end()) {
        std::cout << "Bob age: " << it->second << '\n';
    }
}

Пояснение кода:

std::map<std::string, int> ages; — создаётся контейнер, где ключом является строка, а значением — целое число.
ages["Alice"] = 30; — если ключа "Alice" ещё нет, он будет создан, а значение присвоено.
При использовании operator[] для отсутствующего ключа он вставляется в контейнер со значением по умолчанию.
Цикл for (const auto& [name, age] : ages) проходит по элементам в порядке возрастания ключей.
find("Bob") ищет элемент по ключу; если элемент не найден, возвращается ages.end().

Ключевые моменты:

std::map хранит пары ключ -> значение с уникальными ключами.
Элементы всегда отсортированы по ключу.
Типичная сложность find, insert, erase — O(log n).
Внутренняя структура обычно основана на сбалансированном дереве.
operator[] может создавать новый элемент, если ключ отсутствует.
Если нужен неупорядоченный доступ по хешу, используют std::unordered_map, а не std::map.

Как устроен контейнер std::map в C++?