Тезисы о 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();
});