C++. Сборник рецептов

Смотри также

Рецепт 7.9.

7.8. Выполнение для последовательностей операций над множествами

Проблема

Имеются последовательности, которые требуется реорганизовать с помощью операций над множествами, таких как объединение (union), различие (difference) или пересечение (intersection).

Решение

Для этой цели используйте специальные функции стандартной библиотеки. set_union, set_difference и set_intersection. Каждая из них выполняет соответствующую операцию над множеством и помещает результат в выходной диапазон. Их использование показано в примере 7.8.

Пример 7.8. Использование операций над множествами

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <iterator>
#include "utils.h" // Для printContainer: см. 7.10

using namespace std;

int main {
 cout << "Введите несколько строк: ";
 istream_iterator<string> start(cin);
 istream_iterator<string> end;
 set<string> s1(start, end);
 cin.clear;
 cout << "Введите еще несколько строк: ";
 set<string> s2(++start, end);
 set<string> setUnion;
 set<string> setInter;
 set<string> setDiff;
 set_union(s1.begin, s1.end, s2.begin, s2.end,
 inserter(setUnion, setUnion.begin));
 set_difference(s1.begin, s1.end, s2.begin, s2.end,
 inserter(setDiff, setDiff.begin));
 set_intersection(s1.begin, s1.end, s2.begin, s2.end,
 inserter(setInter,setInter.begin));
 cout << "Объединение:\n";
 printContainer(setUnion);
 cout << "Различие:\n";
 printContainer(setDiff);
 cout << "Пересечение:\n";
 printContainer(setInter);
}

Вывод этой программы выглядит примерно так (printContainer просто печатает содержимое контейнера).

Введите несколько строк: a b c d
^Z
Введите еще несколько строк: d е f g
^Z
Объединение: a b с d e f g
Различие: a b c
Пересечение: d

Обсуждение

Операции с множествами в стандартной библиотеке выглядят и работают сходным образом. Каждая принимает два диапазона, выполняет свою операцию с ними и помешает результаты в выходной итератор. Вы должны убедиться, что для выходной последовательности имеется достаточно места, или использовать inserter или back_inserter (как использовать back_inserter, рассказывается в рецепте 7.5).

Объявление set_union выглядит вот так.

Out set_union(In first1, In last1, In first2, In last2, Out result);

Объявления set_difference, set_intersection и set_symmetric_difference выглядят точно так же.

Чтобы использовать эти функции, сделайте так, как показано в примере 7.8. Например, чтобы найти пересечение двух множеств, вызовите set_intersection вот так.

set_intersection(s1.begin, s1.end, s2.begin, s2.end,
 inserter(setInter, setInter.begin));

Последний аргумент set_intersection требует некоторых пояснений, inserter — это шаблон функции, определенный в <iterator>, который принимает контейнер и итератор и возвращает выходной итератор, который при записи в него значения вызывает для первого аргумента inserter метод insert. При его использовании для последовательного контейнера он вставляет значения перед iterator, переданным в качестве второго аргумента. При его использовании для ассоциативного контейнера, как это делается в показанном выше фрагменте кода, этот итератор игнорируется, и элементы вставляются в соответствии с критерием сортировки контейнера.

set — это удобный пример для наших целей, но операции над множествами работают для любых последовательностей, а не только для set. Например, операции над множествами можно выполнить для list:

list<string> lst1, lst2, lst3;
// Заполняем их данными
lst1.sort; // Элементы должны быть отсортированы
lst2.sort;
set_symmetric_difference(lst1 begin, lst1.end,
lst2.begin, lst2.end, back_inserter(lst3));

Однако так как list хранит данные в неотсортированном виде, его вначале требуется отсортировать иначе результаты операций над множествами будут неверными. Также обратите внимание, что в этом примере вместо inserter используется back_inserter. back_inserter работает аналогично inserter, за исключением того, что для добавления элементов в контейнер он использует push_back. Вы не обязаны действовать точно так же. Например, можно изменить размер выходного контейнера так, чтобы он стал достаточно большим

lst3.resize(lst1.size + lst2.size),
set_symmetric_difference(lst1.begin, lst1.end,

 lst2.begin, lst2.end, lst3.begin);

Если выходная последовательность будет достаточно большой, то можно просто передать итератор, указывающий на первый элемент последовательности, используя begin.

Если вы не знаете, что такое set_symmetric_difference, я вам расскажу. Это объединение разностей двух множеств, определенных в прямом и обратном порядке. Это значит, что если а и b — это множества, то симметричная разность — это а - b b - а. Другими словами, симметричная разность — это множество всех элементов, которые присутствуют в одном из множеств, но отсутствуют в другом.