set и map в C++

set хранит различные значения, map — пары «ключ — значение». Оба контейнера автоматически упорядочивают элементы. Для работы с ними нужны заголовки <set> и <map>.

Множество: set

#include <iostream>
#include <set>
using namespace std;

set<int> s;
s.insert(5);
s.insert(2);
s.insert(5);         // повторное значение не добавится

cout << s.size();    // 2
cout << s.count(2);  // 1
s.erase(5);

Метод	Что делает
`s.insert(x)`	добавляет `x`, если его ещё нет
`s.erase(x)`	удаляет `x`, если он есть
`s.count(x)`	возвращает `0` или `1`
`s.find(x)`	возвращает итератор на `x` или `s.end()`
`s.size()`, `s.empty()`, `s.clear()`	размер, проверка пустоты, очистка

По умолчанию числа хранятся по возрастанию, строки — в лексикографическом порядке. Проверка наличия элемента:

auto it = s.find(2);
if (it != s.end()) {
    cout << *it;
}

Справка: std::set.

Итераторы и поиск по порядку

Итератор похож на указатель на элемент. begin() указывает на первый элемент, а end() — на позицию после последнего. end() нельзя разыменовывать.

set<int> s = {3, 7, 12};

for (auto it = s.begin(); it != s.end(); ++it) {
    cout << *it << ' ';  // 3 7 12
}

for (int x : s) {
    cout << x << ' ';
}

++it переходит к следующему элементу, --it — к предыдущему, если он существует. Обращение по индексу s[i] и выражение it + 1 у set не работают. Для обхода справа налево используются rbegin() и rend().

Метод	Какой элемент находит
`s.lower_bound(x)`	первый, не меньший `x` (≥ x)
`s.upper_bound(x)`	первый, больший `x` (> x)

auto it = s.lower_bound(8);
if (it != s.end()) {
    cout << *it;  // 12
}

lower_bound и upper_bound могут вернуть end(). Перед --it нужно убедиться, что it != begin(). После удаления элемента итератор на него использовать нельзя.

Справка: lower_bound, upper_bound.

Пары: pair

pair содержит два значения: first и second. Пары сравниваются сначала по первому полю, а при равенстве — по второму.

#include <utility>

pair<int, int> p = {4, 9};
cout << p.first << ' ' << p.second;

set<pair<int, int>> pairs;
pairs.insert({5, 2});
pairs.insert({5, 1});  // эта пара будет раньше {5, 2}

Справка: std::pair.

Словарь: map

map<K, V> сопоставляет каждому уникальному ключу типа K значение типа V. Ключи отсортированы.

#include <map>
#include <string>

map<string, int> m;
m["apple"] = 3;
m["banana"] = 2;
++m["apple"];

cout << m["apple"];  // 4

Важно: m[key] при отсутствии ключа создаёт новый элемент. Значение для int будет 0, для string — пустой строкой. Если нужно только проверить наличие ключа, используйте count или find.

if (m.count("banana")) {
    cout << m["banana"];
}

m.erase("banana");

При обходе словаря элементы идут в порядке возрастания ключей:

for (const auto& [key, value] : m) {  // C++17
    cout << key << ' ' << value << '\n';
}

Итератор словаря указывает на пару. Её поля доступны через it->first (ключ) и it->second (значение). Методы find, erase, size, empty работают по тому же принципу, что и у set.

Справка: std::map.

Сложность операций

У set и map поиск, вставка и удаление по ключу работают за O(log n), где n — количество элементов. Перебор всех элементов занимает O(n). У этих контейнеров нет доступа по номеру элемента, как у vector.

Ввод данных и числовые типы

Для чтения слов до конца ввода достаточно цикла:

string word;
while (cin >> word) {
    // очередное слово
}

Если строки могут содержать пробелы, используется getline(cin, s). После чтения числа оператором >> перед getline нужно пропустить остаток текущей строки.

#include <limits>

cin.ignore(numeric_limits<streamsize>::max(), '\n');
getline(cin, s);

Для целых чисел порядка 10¹⁸ используют long long. Беззнаковые 32-битные значения (uint32_t из <cstdint>) при переполнении вычисляются по модулю 2³².

Мемоизация — сохранение уже вычисленных результатов, чтобы не считать их повторно. Для этого можно хранить соответствия «аргумент — результат» в map.

Дополнительная справка: getline, целочисленные типы.