map, set и unordered_map

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

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

int main() {
    std::map<std::string, int> stock;
    stock["pear"] = 4;
    stock["apple"] = 7;
    stock["pear"] = 2;
    std::cout << stock.size() << ' ' << stock["pear"] << '\n';  // 2 2
    for (const auto& item : stock) {
        std::cout << item.first << '=' << item.second << ' ';  // apple=7 pear=2
    }
}

В std::map<std::string, int> первый тип — тип ключа, второй — тип значения. Запись stock["pear"] = 4 кладёт в контейнер пару с ключом "pear". Ключи не повторяются: второе присваивание по ключу "pear" заменило значение, и элементов по-прежнему два.

Элементы std::map упорядочены по ключу, поэтому apple выводится раньше pear, хотя добавлен позже. Каждый элемент — пара: item.first — ключ, item.second — значение. Переменная item объявлена как const auto&: элементы не копируются, а тип выводит компилятор (compiler).

Поиск без вставки

Оператор [] возвращает значение по ключу, а если ключа нет, сначала добавляет его. Новое значение инициализируется как int x{}: для int это 0, для std::string — пустая строка. Поэтому даже чтение по отсутствующему ключу увеличивает размер. Проверить ключ, ничего не добавляя, можно функциями contains (C++20) и count:

std::map<std::string, int> stock{{"apple", 7}};
std::cout << stock.contains("kiwi") << ' ' << stock.count("apple") << '\n';  // 0 1
std::cout << stock["kiwi"] << '\n';  // 0
std::cout << stock.size() << '\n';  // 2

Начальные пары записывают в фигурных скобках: {{"apple", 7}}. Функция count возвращает число элементов с таким ключом, у std::map это 0 или 1.

set и unordered_map

std::set из заголовка (header) <set> хранит только ключи, без значений. Ключи в нём уникальны и упорядочены, а повторный insert того же ключа ничего не меняет:

std::set<int> seen;
seen.insert(3);
seen.insert(1);
seen.insert(3);
std::cout << seen.size() << ' ' << seen.contains(1) << '\n';  // 2 1

std::unordered_map из заголовка <unordered_map> устроен как хеш-таблица (hash table): по ключу он вычисляет, где лежит элемент. В среднем поиск в нём быстрее, чем в std::map, а функции те же: [], contains, count. Но ключи в нём не упорядочены, и порядок обхода стандарт не задаёт.

Частая ошибка

Функция принимает std::map по константной ссылке (const reference) и читает значение через []:

#include <map>
#include <string>

int price(const std::map<std::string, int>& stock) {
    return stock["apple"];  // ✗
}

error: no viable overloaded operator[] for type 'const std::map<std::string, int>' (aka 'const map<basic_string<char>, int>')

Оператор [] может добавить ключ, то есть изменить контейнер, поэтому у константного std::map его нет. Внутри такой функции проверьте ключ через contains, а значение прочитайте через at: stock.at("apple") ничего не добавляет. Для отсутствующего ключа at останавливает программу с ошибкой, поэтому сначала нужна проверка.