Для работы с коллекциями на C++ имеется немало алгоритмов, среди которых особенно выделяется set_intersection.
Умение эффективно находить общие элементы двух множеств пригодится в запросах к базе данных, расчетах для анализа данных или сложных задачах программирования. Рассмотрим нюансы set_intersection и способы совершенствования кода и проектов на C++.
set_intersection
set_intersection — это алгоритм из библиотеки стандартных шаблонов C++, которым вычисляется пересечение двух отсортированных диапазонов. Все элементы, которые имеются в обоих входных диапазонах, им выявляются и помещаются в целевой диапазон.
set_intersection(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first);
С помощью first1 и last1 определяется первый входной диапазон, с помощью first2 и last2 — второй. d_first является началом целевого диапазона.
Принцип работы set_intersection
Предполагается, что оба входных диапазона отсортированы в порядке возрастания. Алгоритмом set_intersection сравниваются элементы обоих диапазонов при одновременном перемещении по ним.
Совпадающие элементы копируются в выходной диапазон. Вот простой пример:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {3, 4, 5, 6, 7};
std::vector<int> result;
std::set_intersection(v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter(result));
for (int n : result) {
std::cout << n << ' ';
}
std::cout << '\n';
return 0;
}
Этим кодом выводится: 3 4 5.
Эффективность и сложность
Ключевое преимущество set_intersection — эффективность. Линейная временна́я сложность алгоритма равна O(n + m), где n и m — размеры входных диапазонов. То есть большие наборы данных им обрабатываются быстро, поэтому алгоритм пригодится там, где важна производительность.
Реальное применение: рекомендации в друзья
Вот как при помощи set_intersection в соцсети предлагаются общие друзья:
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct User {
std::string name;
std::vector<std::string> friends;
};
std::vector<std::string> find_mutual_friends(const User& user1, const User& user2) {
std::vector<std::string> mutual_friends;
std::set_intersection(user1.friends.begin(), user1.friends.end(),
user2.friends.begin(), user2.friends.end(),
std::back_inserter(mutual_friends));
return mutual_friends;
}
int main() {
User alice {"Alice", {"Bob", "Charlie", "David"}};
User bob {"Bob", {"Alice", "Charlie", "Eve"}};
std::vector<std::string> mutual = find_mutual_friends(alice, bob);
std::cout << "Mutual friends of Alice and Bob: ";
for (const auto& friend_name : mutual) {
std::cout << friend_name << " ";
}
std::cout << '\n';
return 0;
}
Этим кодом выводится: Mutual friends of Alice and Bob: Charlie, то есть общие друзья Алисы и Боба: Чарли.
set_intersection с пользовательскими объектами
set_intersection не ограничивается встроенными типами. Он применяется с пользовательскими объектами, если определить способ их сравнения. Как пример возьмем пользовательскую структуру Book:
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Book {
std::string title;
std::string author;
bool operator<(const Book& other) const {
return title < other.title;
}
};
int main() {
std::vector<Book> library1 = {
{"1984", "George Orwell"},
{"To Kill a Mockingbird", "Harper Lee"},
{"Pride and Prejudice", "Jane Austen"}
};
std::vector<Book> library2 = {
{"1984", "George Orwell"},
{"The Great Gatsby", "F. Scott Fitzgerald"},
{"Pride and Prejudice", "Jane Austen"}
};
std::vector<Book> common_books;
std::set_intersection(library1.begin(), library1.end(),
library2.begin(), library2.end(),
std::back_inserter(common_books));
std::cout << "Books in both libraries:\n";
for (const auto& book : common_books) {
std::cout << book.title << " by " << book.author << '\n';
}
return 0;
}
Этим кодом выводится:
```
Books in both libraries:
1984 by George Orwell
Pride and Prejudice by Jane Austen
```
Работа с дублями
По умолчанию в set_intersection включаются все дубли обоих диапазонов. Чтобы удалить дубли, set_intersection используется вместе с std::unique:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v1 = {1, 2, 2, 3, 3, 4, 5};
std::vector<int> v2 = {2, 2, 3, 4, 4, 5, 6};
std::vector<int> result;
std::set_intersection(v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter(result));
auto last = std::unique(result.begin(), result.end());
result.erase(last, result.end());
for (int n : result) {
std::cout << n << ' ';
}
std::cout << '\n';
return 0;
}
Этим кодом выводится: 2 3 4 5.
set_intersection и множества
set_intersection хорош для любых отсортированных диапазонов, но особенно для контейнеров std::set — здесь элементы автоматически сохраняются в отсортированном порядке:
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
int main() {
std::set<int> set1 = {1, 2, 3, 4, 5};
std::set<int> set2 = {3, 4, 5, 6, 7};
std::vector<int> result;
std::set_intersection(set1.begin(), set1.end(),
set2.begin(), set2.end(),
std::back_inserter(result));
for (int n : result) {
std::cout << n << ' ';
}
std::cout << '\n';
return 0;
}
Этим кодом выводится: 3 4 5.
Рекомендации по производительности
Чтобы задействовать весь потенциал set_intersection, не забывайте о:
- Размерах входных диапазонов: производительность алгоритма определяется размерами обоих входных диапазонов. Если один диапазон значительно меньше другого, используйте его как первый диапазон — для потенциального сокращения сравнений.
- Выходной контейнер: использовать
std::back_inserterс вектором удобно, но это чревато многократными перераспределениями. Если максимально возможный размер пересечения известен, резервируйте место заранее:
std::vector<int> result;
result.reserve(std::min(v1.size(), v2.size()));
std::set_intersection(v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter(result));
3. Функция сравнения: для пользовательских объектов убедитесь, что функция сравнения эффективна, в процессе пересечения она будет вызываться многократно.
Заключение
set_intersection — это ценное дополнение к инструментарию любого программиста C++. Благодаря эффективному нахождению общих элементов отсортированных диапазонов set_intersection применяется в различных сценариях — от обработки данных до проектирования алгоритмов.
Эффективно используя set_intersection, вы сможете писать более эффективный и выразительный код, четко и точно решая сложные задачи.
Читайте также:
- C++: полное руководство по параметризованным классам
- C++: подробное руководство по циклам for с векторами
- C++: практическое руководство по проверке наличия файла
Читайте нас в Telegram, VK и Дзен
Перевод статьи ryan: Set Intersection in C++: A Practical Guide
