Тезисы о std::set и std::multiset в C++

Приветствую всех читателей! Меня зовут Максим, и я хочу поделиться с вами своими знаниями о программировании. Я не являюсь профессиональным разработчиком, и программирование для меня — это хобби и способ автоматизации рутинных задач на работе. В этой статье я расскажу вам об ассоциативном контейнере std::set и std::multiset в C++. Надеюсь, что эта информация будет полезной и интересной для всех, кто хочет узнать что-то новое о программировании.

std::set

std::set — это ассоциативный контейнер, который содержит упорядоченный набор уникальных объектов типа Key.

Основные свойства:

• Элементы расположены в отсортированном порядке (по умолчанию по возрастанию);

• Все элементы уникальны (дубликаты не допускаются);

• Реализован как самобалансирующееся двоичное дерево поиска (обычно красно-черное дерево);

• Операции вставки, удаления и поиска выполняются за O(log n);

• Элементы нельзя изменять напрямую, чтобы не нарушить порядок.

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

#include <iostream> #include <set>  int main() {     std::set<int> numbers = {5, 3, 8, 1, 3, 7}; // дубликат 3 будет проигнорирован          // Вывод элементов (будут отсортированы)     for (int num : numbers) {         std::cout << num << " "; // 1 3 5 7 8     }          // Вставка элемента     numbers.insert(4);          // Поиск элемента     if (numbers.find(5) != numbers.end()) {         std::cout << "\n5 found in set";     }          // Удаление элемента     numbers.erase(3);          return 0; }

std::multiset

std::multiset очень похож на std::set, но с одним ключевым отличием — он может содержать несколько элементов с одинаковыми значениями.

Основные свойства:

• Элементы упорядочены;

• Допускаются дубликаты;

• Реализован как самобалансирующееся двоичное дерево поиска;

• Операции вставки, удаления и поиска выполняются за O(log n).

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

#include <iostream> #include <set>  int main() {     std::multiset<int> numbers = {5, 3, 8, 1, 3, 7}; // оба значения 3 будут сохранены          // Вывод элементов     for (int num : numbers) {         std::cout << num << " "; // 1 3 3 5 7 8     }          // Вставка дубликата     numbers.insert(3); // теперь три значения 3          // Подсчет количества определенных элементов     std::cout << "\nNumber of 3s: " << numbers.count(3); // 3          // Удаление всех элементов со значением 3     numbers.erase(3); // удалит все три значения          return 0; }

Общие методы для set и multiset

Оба контейнера поддерживают:

• insert() — добавление элемента;

• erase() — удаление элемента;

• find() — поиск элемента;

• count() — количество элементов с заданным ключом;

• size() — количество элементов;

• empty() — проверка на пустоту;

• clear() — очистка контейнера;

• lower_bound(), upper_bound(), equal_range() — для работы с диапазонами.

Когда использовать?

Используйте std::set, если:

• Нужны уникальные элементы;

• Важна сортировка;

• Требуется быстрый поиск.

Используйте std::multiset, если:

• Можно дубликаты;

• Нужно хранить элементы отсортированными;

• Требуется доступ к элементам с одинаковыми значениями.

Выводы о std::set и std::multiset

1. Ключевое различие:

   • std::set хранит только уникальные элементы;

   • std::multiset разрешает дубликаты.

2. Общие черты:

   • Оба контейнера отсортированы по умолчанию;

   • Операции выполняются за O(log n);

   • Поддерживают стандартные методы вставки, удаления и поиска.

3. Рекомендации по использованию:

   • std::set – если нужны уникальные элементы с автоматической сортировкой (например, список уникальных ID).

   • std::multiset – если допустимы повторы (например, хранение оценок студентов, где у нескольких может быть одинаковый балл).

4. Особенности работы

   • В set попытка вставить дубликат просто игнорируется (без ошибки).

   • В multiset метод erase(value) удаляет все элементы с таким значением (если нужно удалить один, используйте erase(iterator)).

   • count(key) в set возвращает 0 или 1, а в multiset – количество вхождений.

Примерное сравнение контейнеров

---

Добавление и удаление элементов в std::set и std::multiset

Добавление элементов

1. insert(): вставка элемента или диапазона

2. emplace(): создание элемента на месте (без копирования)

3. emplace_hint(): вставка с подсказкой позиции

Вставка в std::set (уникальные элементы)

std::set<int> unique_numbers;  // 1. Простая вставка (возвращает pair<iterator, bool>) auto result = unique_numbers.insert(42); if (result.second) {     std::cout << "Insert successful\n"; }  // 2. Вставка с подсказкой позиции auto hint = unique_numbers.lower_bound(40); unique_numbers.insert(hint, 41);  // Более эффективная вставка  // 3. Emplace - создание на месте unique_numbers.emplace(43);  // 4. Вставка диапазона std::vector<int> numbers_to_add = {44, 45, 46}; unique_numbers.insert(numbers_to_add.begin(), numbers_to_add.end());

Вставка в std::multiset (с дубликатами)

std::multiset<int> multi_numbers;  // 1. Вставка дубликатов разрешена multi_numbers.insert(10); multi_numbers.insert(10);  // ОК - дубликат  // 2. Emplace multi_numbers.emplace(11); multi_numbers.emplace(11);  // Дубликат разрешен  // 3. Вставка диапазона int values[] = {12, 12, 13}; multi_numbers.insert(std::begin(values), std::end(values));

Удаление элементов

1. erase(): по значению, итератору или диапазону

2. clear(): полная очистка контейнера

3. extract(): (C++17) — извлечение узла без удаления

Удаление из std::set

std::set<std::string> names = {"Alice", "Bob", "Charlie"};  // 1. Удаление по значению (возвращает количество удаленных - 0 или 1) size_t count = names.erase("Bob");  // count = 1  // 2. Удаление по итератору auto it = names.find("Alice"); if (it != names.end()) {     names.erase(it); }  // 3. Удаление диапазона names.erase(names.begin(), names.end());  // Очистка всего контейнера  // 4. Извлечение узла (C++17) if (auto node = names.extract("Charlie"); !node.empty()) {     // Можно модифицировать и вставить в другой set     node.value() = "Charles";     names.insert(std::move(node)); }

Особенности операций

Для std::set:

• insert возвращает pair<iterator, bool> (итератор и флаг успеха)

• При попытке вставить дубликат, insert не изменяет контейнер

• erase по значению возвращает 0 или 1

Для std::multiset:

• insert всегда успешен и возвращает итератор

• erase по значению удаляет все совпадения и возвращает их количество

• find возвращает первый найденный элемент

Производительность операций

Полезные советы

Эффективная вставка

auto hint = my_set.lower_bound(value); my_set.insert(hint, new_value);  // Оптимизированная вставка

Безопасное удаление во время итерации

for (auto it = my_set.begin(); it != my_set.end(); ) {     if (condition(*it)) {         it = my_set.erase(it);  // erase возвращает следующий валидный итератор     } else {         ++it;     } }

Работа с дубликатами в multiset

auto [first, last] = multi_set.equal_range(value); multi_set.erase(first, last);  // Удалить все элементы с value

Использование extract для модификации ключей (C++17+):

if (auto node = my_set.extract(key); !node.empty()) {     node.value() = modified_value;  // Изменяем значение     my_set.insert(std::move(node)); }

---

Поиск элементов в std::set и std::multiset

Основные методы поиска

Оба контейнера предоставляют следующие методы для поиска элементов:

1. find(key)

• Возвращает итератор на найденный элемент

• Если элемент не найден, возвращает end()

• Время работы: O(log n)

auto it = my_set.find(42); if (it != my_set.end()) {     std::cout << "Element found: " << *it << "\n"; } else {     std::cout << "Element not found\n"; }

2. count(key)

• Возвращает количество элементов с заданным значением

• Для set: всегда 0 или 1

• Для multiset: может быть больше 1

• Время работы: O(log n) для set, O(log n + k) для multiset (где k — количество найденных элементов)

std::set<int> s = {1, 2, 3}; std::cout << s.count(2); // 1 std::cout << s.count(4); // 0  std::multiset<int> ms = {1, 2, 2, 3}; std::cout << ms.count(2); // 2

3. contains(key) (C++20)

• Возвращает bool — существует ли элемент с таким значением

• Более выразительная альтернатива count()

• Время работы: O(log n)

if (my_set.contains(42)) {     std::cout << "Element exists\n"; }

Поиск в диапазонах

Для работы с диапазонами значений используются:

1. lower_bound(key)

• Возвращает итератор на первый элемент ≥ key.

• Полезен для поиска начальной границы диапазона.

2. upper_bound(key)

• Возвращает итератор на первый элемент > key.

• Полезен для поиска конечной границы диапазона.

3. equal_range(key)

• Возвращает пару итераторов (lower_bound, upper_bound).

• Эффективнее, чем два отдельных вызова.

std::set nums = {10, 20, 30, 40, 50};  // Найти все элементы в диапазоне [20, 40) auto low = nums.lower_bound(20);  // 20 auto high = nums.upper_bound(40); // 50  for (auto it = low; it != high; ++it) {     std::cout << *it << " "; // 20 30 40 }  // Эквивалентно с equal_range auto [first, last] = nums.equal_range(30); for (auto it = first; it != last; ++it) {     std::cout << *it << " "; // 30 }

Особенности поиска в std::set

1. Уникальные элементы:

   • find() возвращает максимум один элемент.

   • count() возвращает 0 или 1.

   • equal_range() возвращает диапазон из 0 или 1 элемента.

std::set<std::string> names = {"Alice", "Bob"};  auto it = names.find("Alice"); if (it != names.end()) {     std::cout << "Found: " << *it << "\n"; }  auto [first, last] = names.equal_range("Bob"); if (first != last) {     std::cout << "Found Bob\n"; }

Особенности поиска в std::multiset

1. Дубликаты элементов:

   • find() возвращает итератор на первый найденный элемент.

   • count() возвращает количество всех найденных элементов.

   • equal_range() возвращает все элементы с заданным значением.

std::multiset<int> grades = {85, 90, 90, 95, 100};  // Найти первый элемент 90 auto it = grades.find(90);  // указывает на первый 90  // Количество элементов 90 size_t n = grades.count(90); // 2  // Получить все элементы 90 auto [first, last] = grades.equal_range(90); for (auto it = first; it != last; ++it) {     std::cout << *it << " "; // 90 90 }

Сравнение методов поиска

Практические рекомендации

1. Для проверки существования элемента:

   • В C++20+ предпочитайте contains() как наиболее выразительный вариант

   • В более ранних стандартах используйте count() или find() != end()

2. Для работы с диапазонами:

   • Используйте lower_bound()/upper_bound() для поиска границ

   • Для точного поиска всех совпадений в multiset используйте equal_range()

3. Для multiset:

   • Помните, что find() возвращает только первый элемент

   • Для обработки всех дубликатов используйте equal_range() или комбинацию lower_bound()/upper_bound()

4. Оптимизация:

   • Если нужно часто проверять существование без доступа к значению, contains() эффективнее find()

   • Для поиска диапазонов сначала определяйте границы, затем обрабатывайте элементы

// Эффективный поиск диапазона std::set<int> large_set = {...}; auto low = large_set.lower_bound(100); auto high = large_set.upper_bound(200);  // Обработка диапазона std::vector<int> result(low, high);

---

Работа с диапазонами в std::set и std::multiset

Основные методы для работы с диапазонами

Оба контейнера предоставляют специальные методы для эффективной работы с диапазонами элементов:

1. equal_range(key)

Возвращает пару итераторов, представляющих диапазон элементов с заданным значением.

auto [first, last] = my_set.equal_range(value); // first - начало диапазона // last - конец диапазона 

2. lower_bound(key)

Возвращает итератор на первый элемент, который не меньше заданного значения.

3. upper_bound(key)

Возвращает итератор на первый элемент, который больше заданного значения.

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

Для std::set (уникальные элементы)

std::set numbers = {10, 20, 30, 40, 50};  // Поиск диапазона [20, 40] auto low = numbers.lower_bound(20);  // Указывает на 20 auto high = numbers.upper_bound(40); // Указывает на 50  for (auto it = low; it != high; ++it) {     std::cout << *it << " "; // Выведет: 20 30 40 }  // Использование equal_range (для set возвращает 0 или 1 элемент) auto range = numbers.equal_range(30); if (range.first != range.second) {     std::cout << "\nFound: " << *range.first; // 30 }

Для std::multiset (с дубликатами)

std::multiset scores = {65, 70, 70, 75, 80, 80, 80};  // Получение всех оценок 70 auto range = scores.equal_range(70); std::cout << "Scores 70: "; for (auto it = range.first; it != range.second; ++it) {     std::cout << *it << " "; // 70 70 }  // Поиск диапазона [70, 80) auto low = scores.lower_bound(70);  // Первый 70 auto high = scores.upper_bound(80); // Элемент после последнего 80  std::cout << "\nRange 70-80: "; for (auto it = low; it != high; ++it) {     std::cout << *it << " "; // 70 70 75 80 80 80 }

Практические сценарии использования

1. Поиск всех элементов в диапазоне значений

std::set names = {"Alice", "Bob", "Charlie", "David", "Eve"};  // Найти все имена между "B" и "D" включительно auto begin = names.lower_bound("B"); auto end = names.upper_bound("D");  for (auto it = begin; it != end; ++it) {     std::cout << *it << "\n"; // Bob, Charlie, David }

2. Удаление диапазона элементов

std::multiset temps = {15, 18, 18, 20, 22, 23, 25};  // Удалить все температуры от 18 до 23 (не включая 23) auto first = temps.lower_bound(18); auto last = temps.lower_bound(23); temps.erase(first, last);  // temps теперь содержит: 15, 23, 25

3. Подсчет элементов в диапазоне

std::multiset data = {1, 2, 2, 3, 3, 3, 4, 5};  auto low = data.lower_bound(2); auto high = data.upper_bound(4); size_t count = std::distance(low, high); // 6 элементов (2,2,3,3,3,4)

Особенности работы с диапазонами

1. Для std::set:

   • equal_range(key) всегда возвращает диапазон из 0 или 1 элемента

   • lower_bound(key) и upper_bound(key) будут равны, если значение отсутствует

2. Для std::multiset:

   • equal_range(key) возвращает все элементы с заданным значением

   • lower_bound(key) указывает на первый элемент ≥ заданного значения

   • upper_bound(key) указывает на первый элемент > заданного значения

3. Все операции работают за O(log n) времени, так как используют бинарный поиск

Продвинутые техники

1. Использование пользовательских компараторов

struct CaseInsensitiveCompare {     bool operator()(const std::string& a, const std::string& b) const {         return std::lexicographical_compare(             a.begin(), a.end(), b.begin(), b.end(),             [](char c1, char c2) { return tolower(c1) < tolower(c2); }         );     } };  std::set<std::string, CaseInsensitiveCompare> words = {"Apple", "banana", "Cherry"};  // Поиск будет регистронезависимым auto range = words.equal_range("apple"); // Найдет "Apple"

2. Работа с временными диапазонами (C++20)

std::set numbers = {1, 2, 3, 4, 5};  // Получить view диапазона [2, 4] auto view = std::ranges::subrange(     numbers.lower_bound(2),     numbers.upper_bound(4) );  for (int n : view) {     std::cout << n << " "; // 2 3 4 } 

Оптимизация производительности

1. Для частых операций с диапазонами:

   • Сохраняйте итераторы, если возможно

   • Используйте equal_range вместо отдельных вызовов lower_bound/upper_bound

2. При массовой обработке:

   • Сначала определите границы диапазона

   • Затем обрабатывайте элементы за один проход

std::multiset<Employee> employees;  // Эффективная обработка всех сотрудников отдела "IT" auto [first, last] = employees.equal_range("IT"); std::for_each(first, last, [](const Employee& emp) {     emp.process_salary(); });