Операции над множествами фундаментальны для программирования, и объединение множеств — одна из важнейших. В C++ алгоритмом std::set_union два отсортированных диапазона эффективно объединяются в один, где все элементы уникальные.
Расскажем о таком же эффективном применении этого алгоритма в проектах на C++.
Объединение множеств на C++
В ходе этой операции объединяются два множества, в том числе все имеющиеся в них элементы. В C++ это реализуется алгоритмом std::set_union с отсортированными диапазонами элементов.
Вот базовый синтаксис:
std::set_union(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first);
Этой функцией принимается два входных диапазона и выходной итератор. А уникальные элементы обоих диапазонов объединяются в выходной.
Базовый std::set_union
Начнем с простого примера:
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {4, 5, 6, 7, 8};
std::vector<int> result;
std::set_union(v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter(result));
for (int num : result) {
std::cout << num << " ";
}
// Вывод: 1 2 3 4 5 6 7 8
}
В этом примере объединяется два отсортированных вектора. Результат содержит все уникальные элементы обоих векторов с сохранением порядка сортировки.
Объединение множеств пользовательскими типами данных
Эта операция не ограничивается встроенными типами, она применяется с пользовательскими классами. Но необходимо убедиться в корректности сортировки.
Вот пример с пользовательским классом Person:
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
struct Person {
std::string name;
int age;
bool operator<(const Person& other) const {
return name < other.name;
}
};
int main() {
std::vector<Person> team1 = {{"Alice", 25}, {"Bob", 30}, {"Charlie", 35}};
std::vector<Person> team2 = {{"Bob", 30}, {"David", 28}, {"Eve", 32}};
std::vector<Person> merged_team;
std::set_union(team1.begin(), team1.end(),
team2.begin(), team2.end(),
std::back_inserter(merged_team));
for (const auto& person : merged_team) {
std::cout << person.name << " (" << person.age << ") ";
}
// Вывод: Alice (25) Bob (30) Charlie (35) David (28) Eve (32)
}
Здесь мы определили пользовательское сравнение по именам Person. В ходе этой операции объединяются две команды, причем дубли удаляются — в примере это Bob.
Реальный сценарий: объединение списков пользователей
Задача: для разработки приложения соцсети предложить пользователю друзей из числа его школьных приятелей и коллег по работе.
Вот как при комбинировании этих списков применяется объединение множеств:
#include <algorithm>
#include <set>
#include <vector>
#include <iostream>
#include <string>
struct User {
std::string name;
int id;
bool operator<(const User& other) const {
return id < other.id;
}
};
std::vector<User> get_school_connections(int user_id) {
// Смоделированный запрос в базу данных
return {{{"Alice", 101}, {"Bob", 102}, {"Charlie", 103}}};
}
std::vector<User> get_work_connections(int user_id) {
// Смоделированный запрос в базу данных
return {{{"Bob", 102}, {"David", 104}, {"Eve", 105}}};
}
int main() {
int current_user_id = 100;
auto school_connections = get_school_connections(current_user_id);
auto work_connections = get_work_connections(current_user_id);
std::vector<User> all_connections;
std::set_union(school_connections.begin(), school_connections.end(),
work_connections.begin(), work_connections.end(),
std::back_inserter(all_connections));
std::cout << "Friend suggestions:" << std::endl;
for (const auto& user : all_connections) {
std::cout << user.name << " (ID: " << user.id << ")" << std::endl;
}
}
В примере показано, как используется объединение множеств при слиянии двух списков. Дубли при этом удаляются — тот же Bob, который появляется в обоих списках.
Оптимизация операций объединения множеств
Хотя std::set_union в целом эффективен, возможна его оптимизация:
1. Предварительная сортировка и резервирование места
Если входные диапазоны не отсортированы, сортируем их. Если известен максимально возможный размер результата, резервируем место в выходном контейнере:
std::vector<int> v1 = {3, 1, 4, 1, 5};
std::vector<int> v2 = {2, 7, 1, 8, 2};
std::vector<int> result;
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
result.reserve(v1.size() + v2.size()); // Максимально возможный размер
std::set_union(v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter(result));
2. Использование контейнеров set
Часто выполняете операции над множествами? Тогда вместо std::vector используйте std::set:
#include <set>
std::set<int> s1 = {1, 2, 3, 4, 5};
std::set<int> s2 = {4, 5, 6, 7, 8};
std::set<int> result;
std::set_union(s1.begin(), s1.end(),
s2.begin(), s2.end(),
std::inserter(result, result.end()));
Множества всегда отсортированы, поэтому предварительная сортировка не нужна.
Большие наборы данных
Здесь использование памяти становится проблемой. Вот как выполняется объединение множеств на больших наборах данных без сохранения всего результата в памяти:
#include <algorithm>
#include <vector>
#include <iostream>
class SetUnionIterator {
std::vector<int>::const_iterator it1, end1, it2, end2;
public:
SetUnionIterator(const std::vector<int>& v1, const std::vector<int>& v2)
: it1(v1.begin()), end1(v1.end()), it2(v2.begin()), end2(v2.end()) {}
int operator*() const {
if (it1 == end1) return *it2;
if (it2 == end2) return *it1;
return std::min(*it1, *it2);
}
SetUnionIterator& operator++() {
if (it1 == end1) ++it2;
else if (it2 == end2) ++it1;
else if (*it1 < *it2) ++it1;
else if (*it2 < *it1) ++it2;
else { ++it1; ++it2; }
return *this;
}
bool operator!=(const SetUnionIterator&) const {
return it1 != end1 || it2 != end2;
}
};
int main() {
std::vector<int> v1 = {1, 3, 5, 7, 9};
std::vector<int> v2 = {2, 3, 5, 7, 11};
SetUnionIterator begin(v1, v2);
SetUnionIterator end(v1, v2);
// Моделируется обработка без сохранения всего результата
for (auto it = begin; it != end; ++it) {
std::cout << *it << " ";
}
// Вывод: 1 2 3 5 7 9 11
}
При таком подходе обрабатывается объединение двух больших отсортированных диапазонов без сохранения всего результата. Это важно при работе с наборами данных, которые не помещаются в памяти.
Заключение: использование объединения множеств на C++
В C++ алгоритм std::set_union — это ценный инструмент для объединения отсортированных диапазонов. Эффективный и универсальный, он применяется со встроенными и пользовательскими типами. Поняв, как эффективно использовать объединение множеств, вы напишете более эффективный код для задач дедупликации, объединения данных, комбинирования списков.
Обобщим ключевые моменты:
- Прежде чем использовать
std::set_union, сортируем входные диапазоны. - Если операций над множествами выполняются часто, применяем
std::set. - В больших наборах данных пользовательскими итераторами обрабатываем объединение, не сохраняя результат целиком.
Освоив эти приемы, вы подготовитесь к самым разным задачам программирования C++, связанным с операциями над множествами.
Читайте также:
- Как проходится ассоциативный массив на C++
- C++: практическое руководство по инициализированию вектора размером
- C++: подробное руководство по разыменованию указателя
Читайте нас в Telegram, VK и Дзен
Перевод статьи ryan: C++ Set Union: Practical Guide with Real-World Examples
