Бесплатный урок из курса «С++ без аллокаций памяти» на Stepik.
Ассоциативные контейнеры — это такие структуры данных, где каждый элемент хранится в отсортированном виде и доступ к нему осуществляется через ключ. Благодаря этому поиск элемента работает не за время, зависящее от размера массива, а очень быстро — примерно за O(log n) (логарифмическое время). В стандартной библиотеке C++ они обычно реализованы через сбалансированные деревья поиска (чаще всего красно-чёрные деревья).
Эти контейнеры бывают двух видов:
-
где ключи обязаны быть уникальными (нельзя вставить два одинаковых ключа),
-
где ключи могут повторяться (несколько элементов с одинаковым ключом).
set — множество уникальных значений
std::set хранит только ключи (без значений) и гарантирует, что каждый ключ встречается только один раз. Все элементы автоматически хранятся в отсортированном виде. Это удобно, если нужно работать с набором уникальных данных: числа, имена, id и т.п.
Например, если мы вставим числа в любом порядке, то set автоматически их отсортирует:
#include <set>
#include <iostream>
int main() {
std::set<int> s;
s.insert(5);
s.insert(1);
s.insert(3);
s.insert(5); // повторное значение игнорируется
for (int x : s) {
std::cout << x << " ";
}
// Вывод: 1 3 5
}map — cловарь (отражение зависимости ключ → значение)
std::map хранит данные в виде пар «ключ-значение». Ключи всегда уникальны и отсортированы, а значения могут быть любыми. Можно использовать map, например, для словаря: искать по слову перевод, по id — данные пользователя, по имени — телефон и т.д.
#include <map>
#include <iostream>
int main() {
std::map<std::string, int> ages;
ages["Alice"] = 25;
ages["Bob"] = 30;
ages["Alice"] = 26; // перезаписывает старое значение
for (auto& [name, age] : ages) {
std::cout << name << " -> " << age << "\n";
}
// Вывод:
// Alice -> 26
// Bob -> 30
}multiset — множество с повторяющимися элементами
В отличие от set, std::multiset разрешает хранить одинаковые ключи. Все элементы тоже хранятся в отсортированном виде, но теперь можно вставлять повторяющиеся значения. Это полезно, если, например, нужно хранить статистику встречаемости чисел или слов.
#include <set>
#include <iostream>
int main() {
std::multiset<int> ms;
ms.insert(5);
ms.insert(5);
ms.insert(1);
for (int x : ms) {
std::cout << x << " ";
}
// Вывод: 1 5 5
}multimap — словарь с повторяющимися ключами
std::multimap похож на map, но в нём можно хранить несколько значений для одного ключа. Это полезно, если, например, у одного человека несколько телефонов или у одного товара несколько отзывов.
#include <map>
#include <iostream>
int main() {
std::multimap<std::string, std::string> phones;
phones.insert({"Alice", "123"});
phones.insert({"Alice", "456"});
phones.insert({"Bob", "789"});
for (auto& [name, phone] : phones) {
std::cout << name << " -> " << phone << "\n";
}
// Вывод:
// Alice -> 123
// Alice -> 456
// Bob -> 789
}